遍历任意树形结构的每个唯一路径（从根到叶）

我有几个列表：遍历任意树形结构的每个唯一路径（从根到叶）

A = ["a0", "a1"]  // the number of lists varies 
B = ["b0", "b1", "b2"] // such as the number of elements in a list. 
C = ["c1"] 
D = ["d0", "d1"]

我转换这个结构成一树：

   _____ROOT______ 
      /    \ 
     ___a0____  ____a1____ 
    / | \ / | \ 
    b0 b1 b2 b0 b1 b2 
    |  |  |  |  |  | 
    c1 c1 c1 c1 c1 c1 
/| /| /| /| /| /| 
    d0 d1 d0 d1 d0 d1 d0 d1 d0 d1 d0 d1

我打印的每一个树中的独特路径（省略根）：

a0 -> b0 -> c1 -> d0 
a0 -> b0 -> c1 -> d1 
a0 -> b1 -> c1 -> d0 
... 
a1 -> b2 -> c1 -> d1

我正在通过“销毁”树本身来遍历它n中的下列方式：

traverse(Node)始终打印树（叶从根部），而已经被traverse(Node)参观了树的delete(Node)切叶的第一个可用路径。

这可以按预期工作，但我很想找到一种解决方案，以前面描述的方式遍历树而不会破坏它。如果有办法做到这一点，那么我会有兴趣遍历这个相同的结构，但以图形的形式来减少冗余。

来源

2011-04-17 Kohányi Róbert

好的。我认为你的意思是你想找到从根到叶的每条路径。

然后（一个未优化的版本）

void traverse (Node root) { 
    // assume root != NULL 
    traverse (root, new LinkedList<Node>()); 
} 

private void traverse (Node root, LinkedList<Node> path) { 
    path.add(root); 
    if (root.isLeaf()) { 
    print path; 
    } 
    else { 
    for each node of root { 
     traverse (node, new LinkedList<Node>(path)); 
    } 
    } 
}

来源

2011-04-17 06:27:54

简单和工作，谢谢！ – 2011-04-17 07:30:43

你怎么用javascript做到这一点？ – 2014-10-18 14:05:24

添加少量代码以使该函数返回所有路径。不管怎么说，多谢拉。 :) – 2014-11-08 20:16:14

所以基本上你正在做一个深度优先搜索，而不是跟踪节点的访问明确以非破坏性的方式，或维持足够的上下文搜索没有跟踪，你正在销毁树来做这个跟踪。

传统的方式将其转换为一个普通的DFS将在你的递归条件循环，基本上孩子递归调用更改为类似：

} else { 
    for (Node child = node.firstChild(); node != null; node = node.nextChild()) { 
     traverse(child); 
    } 
}

这将遍历所有你的孩子，你可以几乎删除了node.isLeaf的情况，因为回溯是为你自动完成的。请注意，我编写了nextChild函数，因为我看不到你的代码中调用了什么，但是你必须有类似的东西，或者某种方式来遍历子代。

保留更多现有代码结构的另一种方法是维护一个包含一组“被访问”节点的单独数据结构，如果所有节点名称都与一组字符串一样简单是唯一的 - 不是删除节点，而是将其添加到“访问”集合中，并且在递归条件中，不检查null，而是查找第一个未访问节点。这可能比上面的建议更复杂，但可能更类似于现在的设置 - 并且如果您需要在循环图而不是树上执行此操作，则会避免循环。

public void rootToLeaves() { 
    HashMap<Integer, TrieNode> hashMap = new HashMap<Integer, TrieNode>(); 
    for(TrieNode trieNode : root.getChildren()) 
     rootToLeaves(trieNode, hashMap, 0); 
} 

private void rootToLeaves(TrieNode trieNode, HashMap<Integer, TrieNode> hashMap, int heightIndex) { 
    hashMap.put(heightIndex, trieNode); 

    if(trieNode.isLeaf()) 
     printValues(hashMap, heightIndex); 
    else 
     for(TrieNode childNode : trieNode.getChildren()) 
      rootToLeaves(childNode, hashMap, heightIndex + 1); 
} 

private void printValues(HashMap<Integer, TrieNode> hashMap, int heightIndex) { 
    for(int index = 0; index <= heightIndex; index++) 
     System.out.print(hashMap.get(index).getValue()); 
    System.out.println(); 
}

这个解决方案做了很好的工作，在内存管理方面：我想出了上打印在TrieTree的话，可以很容易地适用于其他种类的树木或不同需求的工作

来源

2011-04-17 06:36:17 BeeOnRope

除此之外，您可能希望一般阅读广度优先搜索和深度优先搜索。 – 2011-04-17 06:54:23

如果我正在销毁我的树（或其副本），则代码段中的解决方案有效，但那不是我的目的。第二个想法确实是我现在看到的最好的解决方案，但Dante Jiang提出了一个优雅的解决方案，这就是为什么我不能接受你的答案。不管怎么说，还是要谢谢你！ – 2011-04-17 07:35:08

FWIW，该代码片段中的解决方案并不打算用于树破坏，因为解释后立即发表评论 - 实际上与Dante Jiang提出的解决方案相同。 – BeeOnRope 2011-04-17 07:49:36

东西（它使用一个单一的HashMap，其大小永远不会超过树的高度），它提供了很大的灵活性（只需将printValues替换为您需要的任何东西）。

注：事先知道树的高度将允许您使用简单的Array而不是Map。

来源

2012-01-23 00:09:12 Gevorg

1，查找叶节点
2中，从叶节点

public void printPath(N n) { 
     if (n == null) 
      return; 
     if (n.left == null && n.right == null) { 
      do { 
       System.out.print(n.value); 
       System.out.print(" "); 
      } while ((n = n.parent) != null); 
      System.out.println(""); 
      return; 
     } 
     printPath(n.left); 
     printPath(n.right); 
    }

printPath（根）最多遍历;

来源

2013-03-22 05:15:46 boiledwater

遍历任意树形结构的每个唯一路径（从根到叶）

回答

相关问题