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

申し訳ありませんが、私の間違いです。合計ではなく、葉の値のみを上に移動する必要があります。使用される新しい leafValue を参照してください。

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 に答える