5

次の値を順番に追加してバイナリ検索ツリーを構築する場合:

 10, 7, 16, 12, 5, 11, 2, 20, 1, 14

高さ5のツリーを取得します。高さ4のツリーを作成する整数の順序を決定するために使用できる方法(試行錯誤以外)はありますか?

4

3 に答える 3

5

これについては完全には考えていませんが、特定の深さのツリーを取得する1つの方法は、要素を挿入する前に並べ替えることです。つまり、要素を並べ替えてからN二分探索木に挿入すると、深さのツリーが生成されNます。

次のことできる場合があります。

  1. 要素を並べ替える
  2. それらの特定のものを挿入してK=4、深さの木を作成しますK
  3. ツリーが深くならないように、残りの要素を挿入します。

(もちろん、どのK要素から始めるか、残りの要素を挿入するための戦略を選択するのは難しい部分ですが、おそらくこれが始まりになるでしょうか?)


編集K:十分に大きいと仮定すると、一般的な解決策は可能だと思います。これはどう:

  1. 与えられた10, 7, 16, 12, 5, 11, 2, 20, 1, 14
  2. 要素を並べ替えます:1, 2, 5, 7, 10, 11, 12, 14, 16, 20
  3. 最後のK=4要素、最後のK-1、K-2のように、1まで挿入します。

たとえば、最後の4を並べ替えて挿入した後:

12
  \
   14
     \
      16
        \
         20

...最後の3を挿入した後:

  12
 /  \
7    14
 \     \
  10    16
    \     \
     11    20

...最後の2の後:

    12
   /  \
  7    14
 / \     \
2   10    16
 \    \     \
  5    11    20

...そして最後に、最後の要素を挿入した後:

      12
     /  \
    7    14
   / \     \
  2   10    16
 / \    \     \
1   5    11    20

...高さK=4のBSTが残ります。

このアプローチは、Kが十分に大きい場合、特に。の場合にのみ機能することに注意してくださいK(K+1)/2 >= N

于 2012-05-11T16:55:11.840 に答える
5

はい、最初に完全にバランスの取れたツリーを構築してから、親ノードが子の前に出力されるようにノードを出力できます。

完全にバランスの取れたツリーを作成するには、数値を並べ替えてから、再帰的な 2 分割を使用してツリーを構築します。


たとえば、あなたの場合、数字を並べ替えます

 1 2 5 7 10 11 12 14 16 20

そして、それらからバランスの取れたツリーを構築します(真ん中の数字をルートとして、このプロセスを再帰的に繰り返します)

            11
     5            14
 1     7       12    16
   2     10             20

preorder traversal または width-first traversal を使用して、必要な順序でノードを出力できるようになりました (子ノードの前に親ノードを出力する限りは問題ありません)。

11 5 14 1 7 12 16 2 10 20
于 2012-05-11T16:38:56.563 に答える