枚举树中的所有路径

Question

我在想，怎么才能最好地实现一个树形数据结构，以便能够列出所有层级的路径。让我用下面的例子来解释一下：

     A
   /   \
   B    C
   |    /\
   D   E  F

我想能够生成以下内容：

A
B
C
D
E
F
A-B
A-C
B-D
C-E
C-F
A-B-D
A-C-E
A-C-F

目前，我正在对一个用字典构建的数据结构进行深度优先搜索，针对不同的深度来查找，并记录下看到的独特节点。但我在想，是否还有更好的方法来进行这种遍历。有什么建议吗？

Answer 1

使用深度优先搜索来找到树中每个节点的路径，然后调用 enumerate-paths(Path p)，其中 p 是从根节点到当前节点的路径。我们可以把路径 p 想象成一个节点的数组 p[0] [1] .. p[n]，其中 p[0] 是根节点，p[n] 是当前节点。

enumerate-paths(p) {
    for i = 0 .. n  
        output p[n - i] .. p[n] as a path. 
}

每一条路径都是不同的，而且每条路径和树中其他节点返回的结果也不一样，因为没有其他路径会以 p[n] 结束。显然，这个方法是完整的，因为任何路径都是从一个节点到它和根节点之间的某个节点。它也是最优的，因为它准确地找到并输出每条路径一次。

路径的顺序可能和你想的不太一样，但你可以创建一个路径列表的数组，其中 A[x] 是长度为 x 的路径列表。这样你就可以按路径长度的顺序输出这些路径，虽然这样会占用 O(n) 的存储空间。

Answer 2

再介绍一种方法：

在树形结构中，每一条不重复的路径都可以通过它的起点和终点唯一确定。

所以，列举路径的一种方法就是列出每一对可能的节点。对于每一对节点，找到它们的共同祖先，然后沿着这条路径走过去，这样就比较容易找到路径了。

Answer 3

每当你在处理树形结构的问题时，记得用递归的方法哦 :D

def paths(tree):
  #Helper function
  #receives a tree and 
  #returns all paths that have this node as root and all other paths

  if tree is the empty tree:
    return ([], [])
  else: #tree is a node
    root = tree.value
    rooted_paths = [[root]]
    unrooted_paths = []
    for subtree in tree.children:
        (useable, unueseable) = paths(subtree)
        for path in useable:
            unrooted_paths.append(path)
            rooted_paths.append([root]+path)
        for path in unuseable:
            unrooted_paths.append(path)
    return (rooted_paths, unrooted_paths)

def the_function_you_use_in_the_end(tree):
   a,b = paths(tree)
   return a+b