Java 8ストリームを使用してツリーノードを集計

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; 
} 
} 

通常の方法です。

ストリームを使用して直接の子ノードを集計することはできますが、Streamsを使用して再帰的に移動する方法はわかりません。 このコードは、問題を1つのレベルに解決するだけです。何か案は？

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

Answer 1

問題の解決方法の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(); 
} 

これは、総合計を計算するためにStream.mapToIntとIntStream.sum方法と共に上記で定義されNode.allChildren方法を使用しています。

---

また、あなたが所定の位置に再帰を行い、あなたのNodeクラスでFunction<Node, Stream<Node>> descendants属性を持つことができます：

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

あなたが定義している関数がでているので、これは、再帰的なラムダ式です=サインの両側。この種類のラムダ式は、というクラスの属性としてのみ許可されます。つまり、ローカル変数に再帰的ラムダ式を割り当てることはできません。

次のような場所でその再帰関数を使用すると、allChildrenメソッドを書き換えることができは：

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

：

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

最後に、あなたのgetNodeSumメソッドのコードは、以前のバージョンと同じになります注：このアプローチは人によって魅力的になるかもしれませんが、いくつかの欠点があるかもしれません。すなわち、今度はNodeクラスのすべてのインスタンスが、descendants属性を持っています。 ll。これを回避するには、この再帰関数を属性としてTreeクラスを持ち、Nodeを内部クラス（descendants属性を削除したクラス）にすることで回避できます。

Answer 2

あなたは子供が次に行う

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

ストリームに参加することがウィルNodeクラスのためのrecusive方法、追加する必要がある -

root.recusiveConcat().mapToInt(Node::getNodeNum).sum() 

コード全体を

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; 
    } 

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


Node root = new Node(1); 
Node node1 = new Node(2); 
Node node2 = new Node(3); 
Node node3 = new Node(4); 
node2.addNode(node3); 
node1.addNode(node2); 
root.addNode(node1); 
System.out.println(root.recursiveConcat().mapToInt(Node::getNodeNum).sum());