如何使用具有此特定公式的未排序数组实现二叉搜索树？

Question

我需要使用数组来实现具有特定公式的二进制搜索树：root是tree [0]。对于tree [n]处的任何节点，将在树[2n + 1]（左分支）和树[2n + 2]（右分支）处找到n的子节点（如果有的话）。我被允许创建第二个数组来存储BST。我给一个伪代码：

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一个某一点。