たとえば、これはツリーです。
10
12 -1
5 1 1 -2
2 3 10 -9
最大値を持つノードを見つける方法は?
5115 次
2 に答える
1
前述の問題を考慮すると、ツリー全体をトラバースする必要があります。以下の証明を参照してください。
ツリー全体をトラバースするのは、かなり簡単なプロセスです。
ツリー全体をトラバースする必要があることの証明:
ツリー全体をトラバースしなくても、ツリーのどちら側に最大値があるかを識別できると仮定します。
左側に最大ノードを持つツリーが与えられます。これを最大値と呼びますx。
右側の葉ノードの 1 つを選択します。それに 2 つの子を追加します:x+1と-x-1.
以来x+1-x-1 = 0、これらを追加しても、追加したリーフの合計は変更されず、ツリー内の他のノードの合計も変更されません。
これはツリー内の任意のリーフに追加でき、合計には影響しないため、ツリー全体をトラバースして、これがどこかで発生するかどうかを確認する必要があります。
したがって、ツリー全体をトラバースしなくても、ツリーのどちら側に最大値があるかを特定できるという仮定は正しくありません。
したがって、ツリー全体をトラバースする必要があります。
于 2013-10-05T15:11:09.410 に答える
0
一般的なケースでは、ツリー全体をトラバースする必要があります。ツリー内の値が制約されていない場合 (たとえば、すべて非負であるが、この例では負の値がある)、ノード内の値はその下の個々の値について何も教えてくれません。
于 2013-10-05T10:34:33.633 に答える