作成バイナリ検索ツリー

Question

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

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

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

Answer 1

私は完全に介してこれを考えていないが、特定の深さの木を得るための一つの方法は、それらを挿入する前に、あなたの要素を並べ替えることです：バイナリ検索ツリーにN要素を挿入し、その後ソートは、ツリーを生成します。すなわち深さはNです。

あなたことができるかもしれないと：ソート

1. あなたの要素
2. を挿入し、このような方法で、残りの要素を挿入深さの木K
3. を生成するために、それらの具体的なK=4木は深くならない。

（もちろん、選んいる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へ。

   12 
       \ 
       14 
       \ 
        16 
        \ 
        20 
   

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

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

   ...最後の2の後、最後の4を選別し、挿入した後、例えば

：

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の場合にのみ機能します。

Answer 2

はい、完全にバランスの取れたツリーを最初に構築することができます。その結果、ノードの前に親ノードが印刷されるようにノードを出力できます。

完全にバランスのとれたツリーを作成するには、数値をソートし、再帰的バイナリディビジョンを使用してツリーを作成します。例えば

---

、あなたのケースでは、我々は数字

1 2 5 7 10 11 12 14 16 20 

を並べ替えるだろうし、それらからのバランスの取れたツリーを構築する（rootとして中央の数字を取ると、再帰的にこのプロセスを繰り返す）

  11 
    5   14 
1  7  12 16 
    2  10    20 

私たちはあなたが望む順番でノードを印刷するために、先行走査または幅優先走査を使用できるようになりました（子ノードよりも前に親ノードを出力する限り）。

11 5 14 1 7 12 16 2 10 20 

Answer 3

public void testMakeBinarySearchTree() { 
    List<Integer> array = new ArrayList<>(); 
    for (int i = 0; i < 10; i++) { 
     array.add(i+1); 
    } 


    Collections.shuffle(array); 


    Node root = new Node(array.get(5)); 
    for (int value : array) { 
     binarySearchTreeInsertNode(root, value); 
    } 
} 


private void binarySearchTreeInsertNode(Node node, int value) { 
    int data = node.getData(); 
    if (value > data) { 
     Node right = node.getRight(); 
     if (right != null) { 
      binarySearchTreeInsertNode(right, value); 
     } else { 
      node.setRight(new Node(value)); 
     } 
    } else if (value < data) { 
     Node left = node.getLeft(); 
     if (left != null) { 
      binarySearchTreeInsertNode(left, value); 
     } else { 
      node.setLeft(new Node(value)); 
     } 
    } 
}