以下文章中接受的答案提供了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()
这是一个非常简单的修改;保留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()
只需要在函数的末尾调用,而不是在每个分支中调用一次;并且更喜欢使生成器返回产生诸如打印之类的副作用,这会削弱可重用性。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句