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

Question

我需要用一个数组来实现一个二叉搜索树，具体公式为：root is tree[0]。对于 tree[n] 中的任何节点，n 的子节点（如果有的话）将在 tree[2n+1]（左分支）和 tree[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。

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

How to implement Binary Search Tree using an unsorted array with this specific formula?

java

arrays

binary-tree

binary-search

binary-search-tree