この特定の数式を持つソートされていない配列を使用してバイナリ検索ツリーを実装する方法は？

Question

特定の数式でバイナリ検索ツリーを実装するには、配列を使用する必要があります。ルートはtree [0]です。ツリー[n]のノードの場合、ツリーの[2n + 1]（左側のブランチ）とツリー[2n + 2]（右側のブランチ）にnの子があります。私は、BSTを格納するために2番目の配列を作成することができます。

for(i=1;i<;i++) { 
    //Every iteration we start from the root node 
    while (the cell is not empty){ 
     if(less than the element) 
     go to 2i+1; 
     else if (greater than the element) 
     go to 2i+2; 

はこれまでのところ、この私がブレインストーミング何：

public class BinarySearchTree { 

    public void createBST(int[] array) { 

     int[] tree = new int[array.length]; 

     int root = array[0]; 

     for (int i = 0; i < array.length; i++) { 
      if (array[i] < root) { 
       tree[(2*i)+1] = array[i]; 
      } else { 
       array[(2 * i) + 2]; 
      } 
     } 
    } 
} 

私はここから行くかわからないん私は擬似コードを与えられています。私は解決策なしでこれをしばらく行ってきました。どんな助けもありがとうございます。ありがとうございました。

Answer 1

擬似コードは決してツリーを作成しません。

すべての配列値は比較にのみ関連し、興味深い情報はインデックスです。また、「行く」は位置を変更する。その位置はどこかに格納する必要があります（ルートから開始します）。

Integer[] tree = new Integer[array.length] 
//the element to add is array[i] 
for (int i = 0; i < array.length; ++i) { 
    //every iteration starts from the root node 
    int pos = 0; 
    //while the cell is not empty 
    while (tree[pos] != null) { 
     //if the cell is smaller than the element 
     if (tree[pos] < array[i]) { 
      //go to 2n+1 
      pos = 2 * pos + 1; 
     } else { 
      //go to 2n+2 
      pos = 2 * pos + 2; 
     } 
    } 
    //add at the empty position. 
    tree[pos] = array[i]; 
} 

注：これはテストしていないため、何らかの点でArrayIndexOutBoundExceptionがスローされる可能性があります。