6

そのため、バイナリ ツリー内の子の親ノードの場所を常に提供する式を考え出すのに助けが必要です。これは、私の先生が私たちの試験に出題する問題の例です。

「インデックス 0 から始まる配列で実装された、正確に 10,000 個のノードを持つ完全なバイナリ ツリーを考えてみましょう。配列は、ツリーから一度に 1 レベルずつ左から右に要素を抽出することによって、順番に入力されます。ノードに値が保存されているとします。ロケーション 4999 にあります。このノードの親の値はどこに保存されていますか?"

私の先生は、このような問題の解き方を教えてくれませんでした。彼女はちょうど「二分木を描いてパターンを見つけなさい」と言っただけです。私はそれをやっただけですが、何も思いつきませんでした！助けてください。ありがとう。

4

5 に答える 5

14

以下は完全に整数除算を使用しています。つまり、小数剰余は削除されます。任意のノード index についてN、そのノードの子は常に場所2N+1と2(N+1)同じ配列にあります。

したがって、そのような配列内のノード > 0 の親は、N常に index になります(N-1)/2。

親から子への例:

Parent 0: children 1,2
Parent 1: children 3,4
Parent 2: children 5,6
Parent 3: children 7,8
etc...

子から親への例:

Child 8 : Parent = (8-1)/2 = 7/2 = 3
Child 7 : Parent = (7-1)/2 = 6/2 = 3
Child 6 : Parent = (6-1)/2 = 5/2 = 2
Child 5 : Parent = (5-1)/2 = 4/2 = 2

だからあなたの問題のために：

(4999-1)/2 = 4998/2 = 2499

注:配列ベースのヒープソート アルゴリズムのコーディングを開始するときに、これを広範囲に使用することになるため、これを覚えておいてください。

于 2013-03-20T02:50:31.373 に答える
3

助けてくれてありがとう。そして、私は私の質問に対する答えを見つけました！

親ノードの場所を見つけるための一般的なアルゴリズムは次のとおりです。

[i + (root - 1)] / 2 ここで、i は特定のノードの場所、root はルートの場所です。したがって、上記の問題では、ルートは位置 0 から始まります。したがって、任意のノードの親ノードを見つける式は [i + (0 - 1)] / 2 = (i - 1) / 2 です。

ここで、ルートが位置 3 から始まったとします。式は [i + (3 - 1)] / 2 = (i + 2) / 2!!!! になります。これは私が必要としていたアルゴリズムです。あなたのほとんどは、私が提供した1つの問題を解決するのを手伝ってくれましたが、実際には、ルートが任意の位置から開始できるバイナリツリーの一般的な解決策が必要でした。ゼロだけじゃない

于 2013-03-20T18:10:26.617 に答える
2

これは、配列インデックスに基づいて配列要素がツリーにマップされる方法のようです

     0
  1     2
3   4 5   6

もしそうなら、インデックスの親はn( floor( (n - 1) / 2 )for n != 0)にあります

于 2013-03-20T02:02:54.183 に答える
0

要求された数値 (4999) の log2 を実行し、整数部分を取ると、数値 (12) に最も近い 2 の累乗が得られます。2^12=4096 です。

4096 と 2^13 - 1 の間のノードの親は、2^11 と 2^12 - 1 の間のノードです。最初の範囲のノードの各ペアに対して、2 番目の範囲にその親があります。したがって、それらをマップして、差の半分 (4999 - 4096) の整数部分を取り、それを親範囲の開始 (2048) に追加できます。

したがって、903 / 2 のフロアがあり、それを 2048 に追加すると、2499 になります。

正確な計算を行っていないことに注意してください。結果ではなく、答えの戦略を取ります。

少し手を加えるだけで、このアルゴリズムを数式に入れることができます。

それが役に立てば幸い！

于 2013-03-20T01:33:43.917 に答える