如何使用递归列出树中的所有路径?
我在外壳中称呼它为:
t = Tree(1)
t2 = Tree(2)
t7 = Tree(7), t2.children = [t7]
t5 = Tree(5)
t9 = Tree(9)
t8 = Tree(8)
t5.children = [t8, t9]
t.children = [t5, t2]
基本上我把那棵树做成这样:
1
/ \
2 5
| /\
7 9 8
我想在列表中返回以下路径:
[[1, 2, 7], [1, 5, 9], [1, 5, 8]]
总的来说,我可以列出清单,这只是找到一种方法来获取我正在努力去做的特定路径!将不胜感激!
假设您的类结构与以下类似,则可以使用递归获取所有路径。
class Tree:
def __init__(self, value):
self.value = value
self.children = []
def get_paths(t, paths=None, current_path=None):
if paths is None:
paths = []
if current_path is None:
current_path = []
current_path.append(t.value)
if len(t.children) == 0:
paths.append(current_path)
else:
for child in t.children:
get_paths(child, paths, list(current_path))
return paths
t = Tree(1)
t2 = Tree(2)
t7 = Tree(7)
t2.children = [t7]
t5 = Tree(5)
t9 = Tree(9)
t8 = Tree(8)
t5.children = [t9, t8]
t.children = [t2, t5]
print get_paths(t)
输出:
[[1, 2, 7], [1, 5, 9], [1, 5, 8]]
@Shashank感谢您猜测可能的结构 Tree
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句