我有一个树数据结构（有根、不平衡、具有无限分支因子），其中每个单独的节点都有一个关联的“权重”。对于每个节点在树中，我想计算以节点为根的子树中所有节点的累积权重.
例如，在下面的树中，我想计算括号中的数字：
A: 4 (27)
|
+--B: 1 (12)
| |
| +--D: 5 (9)
| | |
| | +--I: 3 (3)
| | |
| | `--J: 1 (1)
| |
| `--E: 2 (2)
|
`--C: 2 (11)
|
+--F: 4 (4)
|
+--G: 2 (2)
|
`--H: 3 (3)
从根节点开始，如何在访问每个节点最少次数的同时计算这些？
不需要任何高级书籍，最容易实现的答案是：
使用 DFS ( http://en.wikipedia.org/wiki/Depth-first_search )，并将每个子树的累积和存储在堆栈中。
例如，您的示例中可能的 DFS 遍历是：A->B->D->I->J->E->C->F->G->H。
在计算节点的子节点的累积和之后，将此值添加到父节点的值。计算完所有子节点的总和后，让父节点将其值返回给自己的父节点。（例如，在计算完 B 的所有孩子之后，将 B 的值返回给 A）。继续直到完成树。
伪代码：
int sum(int n)
{
int cumulative=0;
for all children i of n
cumulative+=sum(i)
cumulative+=value[n]
return cumulative
}
对于伪代码与 C++ 的相似性，我深表歉意；）。复杂度为 Θ(n)，而且您无法获得更快的速度，因为您必须至少访问每个节点一次才能找到总和/获取输入（如果存在）。