python - python 实现任意树

Question

好像没有类似的话题。

我需要从一行整数构建一棵树以供将来处理。该行包含从 -1 到 𝑛 − 1 的整数 - 节点的父节点。如果其中第 𝑖 (0 ≤ 𝑖 ≤ 𝑛 − 1) 为 -1，则节点 𝑖 为根，否则为第 𝑖 父节点的从 0 开始的索引。例如

the input line of integers: 4 -1 4 1 1
then                    ->  0  1 2 3 4  
then  -> 1 is the root, 3 and 4 are children of node 1, 0 and 2 are children of node 4.

我应该能够完成剩下的工作，但不太清楚构建这棵树的过程。

Answer 1

您可以使用dict，其中值是子代的list来表示树。这将使树的构建变得微不足道，因为对于每个节点，您只需将当前索引附加到父子节点即可。这是使用 defaultdict 的示例以 list 作为默认工厂:

from collections import defaultdict

s = '4 -1 4 1 1'

tree = defaultdict(list)
for node, parent in enumerate(int(x) for x in s.split()):
    tree[parent].append(node)

# Remove "parent" of the root node
root = tree.pop(-1)[0]

def print_tree(root, tree, prefix=''):
    print(prefix + str(root))
    for child in tree[root]:
        print_tree(child, tree, prefix + '  ')

print_tree(root, tree)

输出:

1
  3
  4
    0
    2

更新:这是树遍历的另一个示例，用于计算树中的节点数。对于访问的每个节点，它返回 1 + 子节点的总和:

def count_nodes(root, tree):
    return 1 + sum(count_nodes(child, tree) for child in tree[root])