python - 树的所有路径

Question

如何继续使用递归列出树中的所有路径？

我在 shell 中称之为:

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]]

总的来说，我可以列出 list ，这只是找到一种方法来获得我正在努力做的特定路径!将不胜感激任何帮助!

Answer 1

假设您的类结构类似于以下内容，那么您可以使用递归来获取所有路径。

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 感谢您猜测树 的可能结构