如何递归求和并将所有子值存储在树中 [英] How to recursively sum and store all child values in a tree

问题描述

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

Given a tree, what's the easiest way to calculate the sum of all children at a given node?

像这样说一棵树...

红色值代表节点及其子节点的总和.

The red values represent the sum of the node and its children.

假设节点结构如下(示例):

Let's say the node structure look like this (an example):

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

如何以高效的单次传递(在 Python 中)执行此操作?

How can I do this in an efficient, single pass (in Python)?

谢谢！

推荐答案

只要判断一个节点是否是叶子节点，然后将其和权重相加，举个例子:

Just judge if a node is a leaf and add the sum to the weight, here is an example:

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

这篇关于如何递归求和并将所有子值存储在树中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！