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

Question

我需要使用一个数组来实现一个具有特定公式的二叉搜索树：root is tree[0]。对于树[n]上的任何节点，n（如果有）的子节点将在树[2n+1]（左分支）和树[2n+2]（右分支）上找到。我可以创建第二个数组来存储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

伪代码永远不会创建树

任何数组值都只与比较有关，有趣的信息是索引。“go to”也会修改一个位置。这个位置需要存储在某个地方（从根开始）

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