リストのあるツリー上のBFS

Question

だから、私はこのツリーを構築しています。*各ノードはそれ自身で1 .. *ノードを持つことができるノードを持っています。

ツリーの最初の3つのレベルはうまく構築できますが、私がすべてのレベルをコード化していないともっとうまく動作しません。このソリューションはもちろん、何らかの種類の再帰的メソッドとBFSを使用しています。

基本的に私のTreeBuilderクラスでは、tree.getNodesAtDepth(depth))を呼び出し、その深さにあるすべてのノードのリストを取得できるようにしたいと考えています。問題は、私がgetNodesAtDepth(depth)メソッドを実装する方法を理解できないことです。

私が見つけたすべての例は、バイナリツリーです。別の方法として、addChildメソッドに深さ引数を設定して、子を挿入する深さを指定できるようにする方法があります。

最後に、これは私が欲しいものです。 私はルートを持つツリーを持っています。ルートには4つの子ノードを持つリストがあります。私は4人の子供を手に入れたいです。各子は3つのノードを生成します。子供0は3人の子供を、子供1は3人の子供を、子供3は3人の子供を、子供4は3人の子供を有する。等々

おそらく、各ノードにレベル属性を付け、そのノードを検索して親を返すことが考えられます。それが親であれば、検索されたノードのすべてのノードのリストを持つ必要があります。

Answer 1

この方法試してみてください。それを使用する方法

static void getNodesAtDepth(Node root, int currentLevel, int level, List<Node> nodes) { 
    if(root == null) return; 
    if(level == 0) { 
     nodes.add(root); 
     return; 
    } 

    if(currentLevel + 1 == level) { 
     if(root.getNodeList() != null) { 
      nodes.addAll(root.getNodeList()); 
     } 
    } 

    if(currentLevel < level) { 
     if(root.getNodeList() != null) { 
      for(Node node : root.getNodeList()) { 
       getNodesAtDepth(node, currentLevel + 1, level , nodes); 
      } 
     } 
    } 
} 

：もちろん

List<Node> nodeList = new LinkedList<>(); 
getNodesAtDepth(root, 0, 2, nodeList); 

rootは、あなたのツリーのルートです。 nodeListはあなたのすべてのノードを希望のレベル（私の場合は2です）に保存します。あなたが予想される深さを見つけるまで

class Tree { 
    List<Tree> children 
    ... 
} 

は、その後、あなたは再帰的にツリーを反復処理することができます：私はあなたのクラスのツリー構造があると仮定した場合は2番目のパラメータは常に0で、

Answer 2

（つまり、現在のレベルを追跡するためです） ：

void recursivelyCollectNodesAtDepth(int depth, 
            List<Tree> nodesAtDepth, 
            Tree tree, 
            int currentDepth) { 

    if (tree == null) { 
     return; 
    } 

    if (depth == 0) { 
     nodesAtDepth.add(tree); 
    } else if (currentDepth + 1 == depth) { 
     // add children to the node list when expected depth is reached 
     if (tree.getChildren() != null) { 
      nodesAtDepth.addAll(tree.getChildren()); 
     } 
    } else if (currentDepth < depth) { 
     // iterate and recursively travers through child nodes 
     for (Tree childTree : tree.getChildren()) { 
      recursivelyCollectNodesAtDepth(depth, 
        nodesAtDepth, 
        childTree, 
        currentDepth + 1); 
     } 
    } 
} 

ここツリーは、あなたが期待を見つけるまで再帰的にツリーを反復処理を再帰的に期待されるレベル