枚举树中的所有路径

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

每当你在树上发现问题时,只需使用递归: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