2

我要站出来说我不是世界上最伟大的数学家 :D 所以这个问题对你们大多数人来说可能很简单。不幸的是，这让我感到困惑，并且已经尝试了几个可行的解决方案。

与任何一棵树一样，一棵树可以有许多分支，许多分支可以有更多分支，依此类推，直到它们以叶节点结束。我有关于每片叶子的信息，表明它的价值。

我需要的是清楚地解释如何解决将每个叶节点值汇总为它的分支（父）的总和并为其余部分做同样的问题，但不要忘记如果一个分支由其他分支共享它是每个与自身直接相关的较低级别分支和叶子的摘要。

为了更好地解释：

Root
|----Branch
|         |-Leaf 10
|----Branch
|         |----Branch
|         |-Leaf 20 |-Leaf 30
|----Branch         |-Leaf 40
|         |----Branch
|                   |----Branch
|                             |----Leaf 50
|-Leaf 60

目标：

Root 210
|----Branch 10
|         |-Leaf 10
|----Branch 90
|         |----Branch 70
|         |-Leaf 20 |-Leaf 30
|----Branch 50      |-Leaf 40
|         |----Branch 50
|                   |----Branch 50
|                             |----Leaf 50
|-Leaf 60

我能够识别最低级别的成员（叶节点）、根节点和分支本身。我无法确定该分支是否有其他分支链接到自身较低或直接链接到叶节点。这种关系非常自下而上。IE：分支没有提及它的孩子是谁，但孩子知道父母是谁。

如果有不清楚的地方，请询问，我会尝试更好地解释问题。

任何帮助，将不胜感激。

4

2 回答 2

2

好的，左派给这个刺。

我会用一些伪代码来做这件事

foreach leaf in knownLeafs
    parent = leaf.parent //get the leaf parent
    parent.total = parent.total + leaf.value //add leaf value to parent total
    while parent.parent != null //loop until no more parents, this would be the root
    {
        current = parent
        parent = parent.parent //move up the structure
        parent.total = parent.total + current.total
    }
next leaf

你需要创建一个函数，给定一个节点，返回父节点

节点GetParentNodeFrom（节点）

新的伪代码看起来像这样

foreach leaf in knownLeafs
parent = GetParentNodeFrom(leaf) //get the leaf parent

parent.total = parent.total + leaf.value //add leaf value to parent total
while GetParentNodeFrom(parent) != null //loop until no more parents, this would be the root
{
    current = parent
    parent = GetParentNodeFrom(current) //move up the structure
    parent.total = parent.total + current.total
}
next leaf

对不起，我的错误，你应该只向上移动叶子值，而不是总数。请参阅使用的新叶子值。

foreach leaf in knownLeafs
parent = GetParentNodeFrom(leaf) //get the leaf parent
leafValue = leaf.value
parent.total = parent.total + leafValue //add leaf value to parent total
while GetParentNodeFrom(parent) != null //loop until no more parents, this would be the root
{
    current = parent
    parent = GetParentNodeFrom(current) //move up the structure
    parent.total = parent.total + leafValue
}
next leaf
于 2009-12-04T07:54:24.890 回答
0

您想确定树中所有节点的总和吗？

树行走有助于优雅的递归解决方案：

public int SumTree (TreeNode n) {
    if(n.isLeafNode) return n.value;
    return SumTree(n.left) + SumTree(n.right);
}

假设一棵二叉树。

于 2009-12-04T07:43:45.533 回答