在列表樹上使用BFS

所以我正在構建這個樹，它有1個*節點，其中每個節點都有一個列表，它們本身可以有1 *個節點。在列表樹上使用BFS

我可以構建的樹的前三個級別很好，但如果我不編碼所有級別都很簡單，那麼它不會工作更多。解決方案當然是使用某種遞歸方法和BFS。

基本上，在我的TreeBuilder類中，我希望能夠調用tree.getNodesAtDepth(depth))並獲取所有處於該深度的節點的列表。問題是我不明白我如何實施getNodesAtDepth(depth)方法。

我發現的所有例子都是二叉樹。另一種方法是讓addChild方法獲取深度參數，以便我可以指定插入子級的深度。

最後，這就是我想要的：我有一棵有根的樹。根有一個有4個子節點的列表。我想得到4個孩子。爲每個孩子生成三個節點。所以對於孩子0有3個孩子，孩子1有3個孩子，孩子3有3個孩子，孩子4有3個孩子。等等

也許一個可能的靈魂是在每個節點上有一個級別屬性並搜索該節點，然後返回它的父級。因爲它的父節點應該有一個搜索節點上所有節點的列表。

來源

2017-09-07 snackerMaker

遞歸遍歷樹的遍歷，直到找到預期深度（實際上是「預計深度-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）。第二個參數是始終0，（這對跟蹤當前水平）

來源

2017-09-07 08:20:01

什麼是零+1？ – snackerMaker

@snackarMaker，ups，它是''currentLevel''，我已經更新了答案 –

哇，這真的有效！非常感謝！一直在抓我的頭髮！ :) – snackerMaker

如果我假設你的分類結構爲：

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

然後你就可以遞歸遍歷樹，直到找到預期的深度：

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

這裏的樹節點遞歸遍歷到預期的水平

來源

2017-09-07 08:36:25

在列表樹上使用BFS

回答

相關問題