在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

我想到的最简单的方法，就是建立一个字典，这个字典里包含了每个父节点可能有的所有子节点，像这样：

d = {}

for parent, child in tree:
    try:
        d[parent].append(child)
    except KeyError:
        d[parent] = [child]

假设有一个树结构是这样的：[[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, 7],
 1: [2],
 2: [3, 4, 5],
 3: [6],
 4: [6],
 5: [6],
 7: [6],
 8: [9],
 9: [6]}

现在就可以像这样递归地遍历这棵树：

def printPaths(d, currentPath):
    if currentPath[-1] not in d:
        print currentPath # last node can't possibly be a parent, so stop
    else:
        for child in d[currentPath[-1]]:
            printPaths(d, currentPath + [child])


for root in d:
    printPaths(d, [root])

我还没有测试过这个递归，但这应该能给你一个大概念 :)

Answer 2

你可以使用一个递归生成器函数来实现这个功能。我假设树中的根节点总是在原始列表中所有子节点之前。

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]

解释：首先，我会构建一个包含每个节点所有可能路径的列表。然后，对于每个我还没有使用过的节点，我假设它是一个根节点，并递归地找出从它出发的路径。如果从任何节点都找不到路径，那它就是一个叶子节点，我就停止递归并返回找到的路径。

如果节点的顺序假设不成立，那么你需要先找到所有根节点。这可以通过找出所有没有出现在任何连接的第二个节点的节点来实现。

Answer 3

给你看看。虽然这段代码不是最优雅的，但它能正常工作：

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

tree = {}
numberOfChildren = {}
for (f, t) in inputValues:
  if not tree.has_key(f):
    tree[f] = []
  tree[f].append(t)
  if not numberOfChildren.has_key(t):
    numberOfChildren[t] = 0
  numberOfChildren[t] += 1

roots = [c for c in tree if c not in numberOfChildren]
permutations = []

def findPermutations(node, currentList):
  global tree
  global permutations
  if not tree.has_key(node):
    permutations.append(currentList)
    return
  for child in tree[node]:
    l = list()
    l.extend(currentList)
    l.append(child)
    findPermutations(child, l)

for r in roots:
  findPermutations(r, [r])

print permutations