Как рекурсивно суммировать и хранить все дочерние значения в дереве

Question

Учитывая дерево, какой самый простой способ рассчитать сумму всех детей на данном узле?

Say дерево, как это ...

КРАСНУЮ значений представляют собой сумму узла и его детей.

Скажем, структура узла выглядит следующим образом (пример):

class Node: 
    def __init__(self, name): 
     self.children = [] 
     self.weight = 100 
     self.weight_plus_children = 295 

Как я могу это сделать эффективным, один проход (в Python)?

Спасибо!

Answer 1

Просто судить, если узел является листом и добавить сумму к весу, вот пример:

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.get_all_weight()", 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('C1', 58, None) 
leaf2 = Node('C2', 7, None) 
leaf3 = Node('C3', 10, None) 
leaf4 = Node('C4', 20, None) 

subroot = Node('B1', 50, [leaf1, leaf2]) 
subroot1 = Node('B2', 50, [leaf3, leaf4]) 

root = Node('A', 100, [subroot, subroot1]) 

print subroot.get_all_weight() 
print 
print subroot1.get_all_weight() 
print 
print root.get_all_weight() 

Выход:

F:\so>python test-tree.py 
child.get_all_weight() 58 
child.get_all_weight() 7 
115 

child.get_all_weight() 10 
child.get_all_weight() 20 
80 

child.get_all_weight() 115 
child.get_all_weight() 80 
295 

Answer 2

Вы можете попробовать следующую рекурсивную программу:

def calculate_sum(cur): 
    children_sum = 0 
    for child in cur.children: 
     children_sum += calculate_sum(child) 
    return cur.weight + children_sum 

calculate_sum(root) # pass in your root node 

Answer 3

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

def treesum(node): 
    return node.weight + sum(treesum(child) for child in node.children)