N 元树遍历，包括指向内部节点的路径

Question

以下文章中接受的答案提供了n元树中的所有根到叶路径：打印n元树python的所有路径。如何修改上述答案(也包含在下面(中的代码以包括从根节点到内部节点的路径？例如，在帖子中提供的树中，完整列表将是：

[10, 2] #path from root to internal node
[10, 4] #path from root to internal node
[10, 2, 15] #path from root to leaf
[10, 2, 20] #...
[10, 2, 25]
[10, 2, 30]
[10, 4, 45]
[10, 4, 50]
[10, 4, 55]
[10, 4, 60]

您如何修改此程序以完成此任务？

def traverse(node, path = []):
path.append(node.data)
if len(node.child) == 0:
print(path)
path.pop()
else:
for child in node.child:
traverse(child, path)
path.pop()

Answer 1

这是一个非常简单的修改;保留DFS，但在每个节点打印，而不仅仅是叶子。对于每个递归调用帧，推送根节点，让出路径，递归每个子节点，然后在访问完所有子节点后弹出根。

traverse是一个糟糕的函数名称，因为它没有描述正在执行的遍历类型。

def all_tree_paths(node, path=[]):
path.append(node)
yield path[:]
for child in node.child:
yield from all_tree_paths(child, path)
path.pop()
if __name__ == "__main__":
from collections import namedtuple
Node = namedtuple("Node", "data child")
"""  a
/ | 
b  c  d
/     / 
e     f   g
"""
tree = Node(
"a",
[
Node(
"b", 
[
Node("e", [])
]
),
Node("c", []),
Node(
"d", 
[
Node("f", []),
Node("g", [])
]
) 
]
)
print([[x.data for x in path] for path in all_tree_paths(tree)])

输出：

['a']
['a', 'b']
['a', 'b', 'e']
['a', 'c']
['a', 'd']
['a', 'd', 'f']
['a', 'd', 'g']

考虑到这一点，我认为原文更清楚，因为：

def all_root_to_leaf_paths(node, path=[]):
path.append(node)
if not node.child:
yield path[:]
for child in node.child:
yield from traverse(child, path)
path.pop()

if len(node.child) == 0:应该是if node.child的;else是多余的;path.pop()只需要在函数末尾调用，而不是在每个分支中调用一次;并且更喜欢退回生成器，也不愿产生打印等副作用，这会削弱可重用性。