遍历任意树形结构中从根到叶子的每条唯一路径。

Question

我有几个列表：

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

我正在通过以下方式遍历树，同时“销毁”树本身：

public static void delete(Node node) {
  if (node.isLeaf() && !node.isRoot()) {
    Node parent = node.getParent();
    parent.removeChild(node);
    delete(parent);
  }
}

public static void traverse(Node node) {
  if (node.isRoot())
    System.out.println("---");
  else
    System.out.println(node.getName());

  if (node.isLeaf()) {    // I'm still working on
    if (!node.isRoot()) { // removing unnecessary checks
      delete(node);
      traverse(node.getRoot());
    }
  } else {
    Node child = node.firstChild();
    if (null != child)
      traverse(child);
  }
}      

traverse(Node)函数总是打印出树的第一条可用路径（从根到叶子节点），而delete(Node)函数则删除已被traverse(Node)访问过的叶子节点。

虽然这种方法可以达到预期效果，但我很想找到一种在不破坏树的情况下以前述方式遍历树的解决方案。如果有这样的方法，我会对以图形的形式遍历相同结构（以减少冗余）感兴趣。

- Kohányi Róbert

Answer 1

好的，我想你实际上是想找到从根节点到叶子节点的每条路径。

那么以下是（未经优化的）方法：

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

- Dante May Code

---

你如何使用JavaScript实现这个？ - Jack Shultz

只需添加少量代码即可使函数返回所有路径。不管怎样，谢谢。 :) - dg_no_9

Answer 2

基本上，您正在进行深度优先搜索，但与以非破坏性方式明确跟踪节点的访问或保持足够上下文以无需跟踪搜索不同，您正在破坏树以进行此跟踪。

将其转换为普通DFS的传统方法是循环递归条件，基本上更改子递归调用为以下内容：

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

这将遍历所有子节点，你基本上可以删除node.isLeaf的情况，因为回溯会自动完成。请注意，我编写了nextChild函数，因为我看不到你的代码中它的名称，但你一定有类似的东西，或者有一种方法来遍历子节点。

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

- BeeOnRope

---

此外，您可能希望通读广度优先搜索和深度优先搜索的相关内容。 - Chris Moschini

代码片段中提供的解决方案适用于我销毁树（或其副本）的情况，但这并不是我的意图。第二个想法确实是最好的解决方案，正如我现在所看到的，但Dante Jiang提出了一个优雅的解决方案，这就是为什么我不能接受你的答案。无论如何，还是谢谢！ - Kohányi Róbert

就此问题而言，代码片段中的解决方案并不打算与树破坏一起使用，因为紧随其后的注释解释了这一点——实际上它是Dante Jiang提出的同一解决方案。 - BeeOnRope

Answer 3

在处理Trie树中单词打印时，我想到了一个可以轻松适应其他类型树或不同需求的方法：

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

这个解决方案在内存管理方面做得很好（它使用一个单一的 HashMap，其大小永远不会超过树的高度），并且它提供了很多灵活性（只需用你需要的内容替换 printValues 即可）。

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

- Marsellus Wallace

Answer 4

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(根节点);

- boiledwater