реализовать произвольное дерево 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 

Update: Вот дополнительный пример обхода дерева, который подсчитывает количество узлов в дереве. Для каждого посещенного узла возвращается 1 + сумма дочерних узлов:

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