能否使用Java 8 Streams构建Tree数据模型？

Question

我正在研究Java 8流。

目前，我正试图通过流式处理文件来构建经典的树形结构，其中每个记录描述了父子关系。

我希望我的解决方案能够从类似以下示例的输入数据记录中构建树：

Parent A - Child B
Parent A - Child C
Parent A - Child D
Parent A - Child E
Parent B - Child F
Parent B - Child G
Parent C - Child H
Parent D - Child I
Parent G - Child J

我想要构建一个LinkedHashMap<String, List<String>>，例如最终结果为：

A - B, C, D, E
B - F, G
C - H
D - I
G - J

我最接近的尝试失败了，出现了重复的键。

Map<String, List<String>> map = stream.sorted().map(line -> line.split("-")).flatMap(line -> Arrays.stream(line)).collect(Collectors.toMap(Function.identity(), Arrays::asList));

或者使用以下的Node值对象。

public class Node {

    private final String name;
    private Node parent;
    private List<Node> children = new LinkedList<>();

}

从我的输入文件中直接构建所有树节点，同时填充完整的子节点列表。

- Hector

---

你的第一个例子更像是一个多值映射而不是一棵树。您的目标是什么？是一个类似于第二个例子的多重映射还是一种树结构？如果您的目标是树结构，那么您的输入数据是否确保了类似树状结构（例如单一根节点、连接、无环）？ - Nándor Előd Fekete

@NándorElődFekete，无论是多值映射还是树都能满足我的需求。我的文件输入数据保证了一个经典的多节点映射，具有单个根节点和动态数量的子节点。 - Hector

Answer 1

添加一个合并lambda函数来聚合子节点：

Map<String, List<String>> map = list.stream().sorted()
        .map(line -> line.split("\\s*-\\s*"))
        .collect(toMap(a -> a[0], 
                       a -> new ArrayList<>(Arrays.asList(a[1])),
                      (a, b) -> {a.addAll(b); return a;}));

如果你的Node没有"parent"字段，你仍然可以更直接地获取节点：

List<Node> nodes = ist.stream().sorted()
    .map(line -> line.split("\\s*-\\s*"))
    .collect(groupingBy(a -> a[0]))
    .entrySet()
    .stream()
    .map(e -> new Node(e.getKey()[0], e.getValue().stream()
        .map(a -> new Node(a[1], null))
        .collect(toList())))
    .collect(toList());

最初的分组更加简单，因为没有将对话转换为列表 - 分割后的原始数组保持不变。

_{声明：代码可能无法编译或者无法按照我的手机输入（但是有很大的概率能够正常工作）}

- Bohemian

---

在你的Node类中拥有parent字段会使从地图创建节点变得困难和丑陋。如果没有它，你可以轻松地将地图流式传输以创建Node列表。 - Bohemian

如何在没有父节点字段的情况下链接节点以构建树形结构？ - Hector

@Hector，孩子们已经通过在孩子列表中的存在而“链接”起来了。除非您需要从任意子节点导航到其父节点（这将是不寻常的 - 我从未见过有人使用），否则您不需要父字段。也许您正在将情况与具有外键的数据库元组进行比较，但这在应用程序世界中并不适用。 - Bohemian

我已经添加了一些代码，直接从输入到节点。 - Bohemian

Answer 2

这是一个适用于 groupingBy 收集器的任务:

import static java.util.stream.Collectors.*;

Pattern ptrn = Pattern.compile("Parent (.*) - Child (.*)");

Map<String, List<String>> map = data.stream()
        .sorted()
        .map(ptrn::matcher)
        .filter(Matcher::find)
        .collect(groupingBy(
                m -> m.group(1), 
                LinkedHashMap::new ,
                mapping(m -> m.group(2), toList())
        ));

- Misha

Answer 3

如果您想要制作一个多地图，可以使用以下方法：

Map<String, Collection<String>> result = stream //stream of lines
    .sorted()
    .map(line -> line.split("\\s*-\\s*"))
    .collect(
        Collectors.toMap(
            (String[] arr) -> arr[0],
            (String[] arr) -> Collections.singleton(arr[1]),
            (u, v) -> {
                Collection<String> merged = new LinkedHashSet<>(u);
                merged.addAll(v);
                return merged;
            },
            LinkedHashMap::new
        )
    );

关键在于自定义的地图收集器，它使用集合作为值，并使用合并函数来处理重复键的情况，即具有多个值的键。如果您不关心元素的顺序，可以使用简单的HashMap和HashSet代替LinkedHashMap和LinkedHashSet，在这种情况下，您也可以删除sorted()操作。

- Nándor Előd Fekete