recursion - 使用 Java 8 Streams 求和树节点

Question

是否可以使用 Java 8 流来汇总一棵树的节点(如果可能的话)？

这是一个节点类

public class Node
{   
private int nodeNum;    
ArrayList<Node> children = new ArrayList<>();

public Node(int num)
{
    this.nodeNum = num;
}

public int getNodeNum()
{
    return nodeNum;
}

public boolean addNode(Node node)
{
    return children.add(node);
}

public ArrayList<Node> getNodes()
{
    return this.children;
}
}

解决此问题的正常方法是使用递归并对节点求和，如下面的代码。

int getNodeSum(Node node)
{
    int total = 0;

    if(node.children.isEmpty())
        return node.getNodeNum();
    else
    {
        for(Node tempNode:node.children)
        {
            total+= getNodeSum(tempNode);
        }
        return total+node.getNodeNum();
    }
}

我们可以使用流来总结直接子节点，但我不知道如何深入并使用流递归地进行。 这段代码只解决了一个层面的问题。有什么想法吗？

total = list.stream().filter(Node -> node.children.isEmpty()).map(Node:: getNodeNum).reduce(node.getNodeNum(), (a,b) -> a+b);

Answer 1

解决您问题的一种方法是使用递归和 Stream.flatMap 。

首先，您需要将以下辅助方法添加到您的 Node 中类:

public Stream<Node> allChildren() {
    return Stream.concat(
        Stream.of(this), 
        this.children.stream().flatMap(Node::allChildren)); // recursion here
}

这将返回 Stream<Node>其元素是该节点及其所有后代节点。

然后，你可以重写你的 getNodeSum方法如下:

int getNodeSum(Node node) {
    return node.allChildren()
        .mapToInt(Node::getNodeNum)
        .sum();
}

这使用上面定义的Node.allChildren方法以及 Stream.mapToInt 和 IntStream.sum 计算总和的方法。

---

或者，您可以有 Function<Node, Stream<Node>> descendants Node 中的属性就地执行递归的类:

private Function<Node, Stream<Node>> descendants =
    node -> Stream.concat(
        Stream.of(node),
        node.children.stream()
            .flatMap(this.descendants)); // recursion here: function invoked again

这是一个递归 lambda 表达式，因为您定义的函数位于 = 的两侧符号。这种 lambda 表达式只能作为类的属性，即您不能将递归 lambda 表达式分配给局部变量。

使用该递归函数后，您可以重写 allChildren方法如下:

public Stream<Node> allChildren() {
    return descendants.apply(this);
}

最后，您的 getNodeSum 的代码方法与以前的版本相同:

int getNodeSum(Node node) {
    return node.allChildren()
        .mapToInt(Node::getNodeNum)
        .sum();
}

注意:虽然这种方法可能对某些人有吸引力，但它可能有一些缺点，即现在 Node 的每个实例。类有descendants属性，尽管根本不需要。你可以绕过这个，即通过 Tree将此递归函数作为属性的类，并且 Node是一个内部类(删除了 descendants 属性)。