如何递归求和并将所有子值存储在树中

Question

给定一棵树，计算给定节点上所有子节点的总和的最简单方法是什么？

像这样说一棵树...

红色值表示节点及其子节点的总和。

假设节点结构如下所示（示例）：

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

我怎样才能高效地完成此操作（在 Python 中）？

谢谢！

Answer 1

你可以试试下面的递归程序：

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 2

一个将其权重添加到其子项权重的函数，其中其子项的权重是根据函数本身定义的。在根节点上调用它，它应该 return 整棵树的总和。

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

Answer 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.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

如何递归求和并将所有子值存储在树中

How to recursively sum and store all child values in a tree

python

tree

recursion