python - 在 Python 中遍历一棵不寻常的树

Question

我有一个像这样的不寻常的树数组:

[[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], 
 [4, 6], [3, 6], [0, 7], [7, 6], [8, 9], [9, 6]]

数组的每个元素都是一对，这意味着第二个是第一个的跟随者，例如:

[0, 1] - 0 is followed by 1
[1, 2] - 1 is followed by 2

我正在尝试像这样提取数组:

0 1 2 3 6    
0 1 2 4 6    
0 1 2 5 6
0 7 6
8 9 6

我无法像这样编写强大的遍历程序来提取所有可能的路径。我怎样才能用 Python 做到这一点？

Answer 1

您可以使用递归生成器函数来完成。我假设树中的根节点总是在原始列表中出现在它的所有子节点之前。

tree = [[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], [4, 6], [3, 6],
        [0, 7], [7, 6], [8, 9], [9, 6]]

paths = {}
for t in tree:
    if t[0] not in paths: paths[t[0]] = []
    paths[t[0]].append(tuple(t))

used = set()

def get_paths(node):
    if node[1] in paths:
        for next_node in paths[node[1]]:
            used.add(next_node)
            for path in get_paths(next_node):
                yield [node[0]] + path
    else:
        yield [node[0], node[1]]

for node in tree:
    if tuple(node) in used: continue
    for path in get_paths(node):
        print path

输出:

[0, 1, 2, 3, 6]
[0, 1, 2, 4, 6]
[0, 1, 2, 5, 6]
[0, 7, 6]
[8, 9, 6]

说明:首先，我构建了一个包含每个节点的所有可能路径的列表。然后对于我还没有使用过的每个节点，我假设它是一个根节点并递归地找到从它引出的路径。如果没有从任何节点找到路径，则它是叶节点，我停止递归并返回找到的路径。

如果关于节点顺序的假设不成立，那么您首先必须找到所有根节点的集合。这可以通过查找所有未在任何连接中显示为第二个节点的节点来完成。