Суммируйте все узлы n-арного дерева в Python - PullRequest
Новая
       51

Суммируйте все узлы n-арного дерева в Python

1 голос
/ 14 июля 2020

У меня есть таблица в файле Excel по этой ссылке :

введите описание изображения здесь

Как я мог прочитать его как n-арное дерево и суммировать все узлы в Python, если Input значения равны 1 s? Было бы лучше, если бы его имена nodes и leaves также отображались в дереве. 

         15
     /        \
    8          7
  /  \      /     \
  6   2    2       5
/ | \ |   /  \   / | \
3 3 0 2   2  0  0  2  3

Большое спасибо за вашу любезную помощь в продвижении.

Мой пробный код: 

class Node:
    def __init__(self, name, weight, children):
        self.children = children
        self.weight = weight
        self.weight_plus_children = weight

    def get_all_weight(self):
        if self.children is None:
            return self.weight_plus_children
        else:
            for child in self.children:
                # print(child)
                print("Child node score", child.get_weigth_with_children())
                self.weight_plus_children += child.get_weigth_with_children()

        return self.weight_plus_children

    def get_weigth_with_children(self):
        return self.weight_plus_children

leaf1 = Node('Evaluation item 1', 3, None)
leaf2 = Node('Evaluation item 2', 3, None)

leaf3 = Node('Evaluation item 3', 3, None)
leaf4 = Node('Evaluation item 4', 1, None)
leaf5 = Node('Evaluation item 5', 1, None)
leaf6 = Node('Evaluation item 6', 2, None)

leaf7 = Node('Evaluation item 7', 2, None)
leaf8 = Node('Evaluation item 8', 2, None)


subroot1 = Node('Ordinary account authentication', 0, [leaf1, leaf2])
subroot2 = Node('Public account identity verification', 0, [leaf3, leaf4, leaf5, leaf6])
subroot3 = Node('Platform equipment information record', 0, [leaf7, leaf8])

root1 = Node('User Management', 0, [subroot1, subroot2])
root2 = Node('Business platform deployment', 0, [subroot3])

root = Node('Business application security', 0, [root1, root2])

print(subroot1.get_all_weight())
print(subroot2.get_all_weight())
print(subroot3.get_all_weight())

print(root1.get_all_weight())
print(root2.get_all_weight())

print(root.get_all_weight())

Вых: 

Child node score 3
Child node score 3
6
Child node score 3
Child node score 1
Child node score 1
Child node score 2
7
Child node score 2
Child node score 2
4
Child node score 6
Child node score 7
13
Child node score 4
4
Child node score 13
Child node score 4
17

1 Ответ

5 голосов
/ 14 июля 2020

Вы можете назначить целое число каждому узлу дерева, которое будет рекурсивно содержать сумму всех дочерних значений.

Начальное значение каждого узла будет 0.

Тогда вы можете запустите рекурсивный алгоритм вроде этого: 

def sum_children(root):
    if root is None:
        return 0
    sum_total = 0
    for child in root.get_children():
        child_value = sum_children(child)
        if child_value > 0:
            sum_total += child_value
    root.value = sum_total
    return sum_total

# Call this function on the tree root
sum_children(tree_root)
...