java - 使用数组的二叉树

Question

我试图从第一个数组中插入键并将它们排序到第二个数组中的二叉树中。我知道我的插入方法有问题，但我无法弄清楚。任何帮助将不胜感激

import java.util.Arrays;

public class BSTreeArray {
static int startValues[]={50, 25, 75, 10, 15, 5, 53, 29, 79, 78, 111, 33};
int [] aTree;
public BSTreeArray(){
    for(int i=0; i<startValues.length;i++){
        insert(startValues[i]);
    }
    System.out.println("Pre-Order:");
    preOrder(aTree[0], "");
}


public void insert(int key){
    aTree=new int [100];

    if(aTree[0]==0){
        aTree[0]=key;
    }

    boolean add = false;
    int curIdx=0;

    while(!add){
        if(key<aTree[curIdx]){
            //go left
            if (aTree[curIdx*2+1]==0){
                aTree[curIdx*2+1]=key;
                add = true;
            }else{
                curIdx=curIdx*2+1;
            }
        }else{
            //go right
            if(aTree[curIdx*2+2]==0){
                aTree[curIdx*2+2]= key;
                add=true;
            }else{
                curIdx=curIdx*2+2;
            }
        }
    }
}

public void preOrder(int idx, String i){
    if(idx>aTree.length){
        return;
    }else{
        System.out.println(i+aTree[idx]);
        preOrder(((2*idx)+1), i+".");
        preOrder(((2*idx)+2), i+".");

    }
}

public static void main (String []args){
    BSTreeArray a=new BSTreeArray();
}
 }

当前输出:

Pre-Order:
0
.0
.0

期望的输出:

50

....25

........10

............5

............15

........29

............33

....75

........53

........79

............78

............111

Answer 1

我几乎立即看到的一件事是第一个插入将被添加到数组中两次。

if(aTree[0]==0){
    aTree[0]=key;
}

boolean add = false;
int curIdx=0;

while(!add){ // add is false so the loop is entered
    if(key<aTree[curIdx]){ // aTree[curIdx] == key so false

    }else{
        if(aTree[curIdx*2+2]==0){ // true because arrays are initialized
                                  // with all elements 0

            aTree[curIdx*2+2]= key; // assign key a second time
            add=true;
        }
    }
}

这可能会污染所有其余的插入，因为如果它们位于第一个节点的右侧，它们将被跳过一个节点。

看来你应该这样做:

if(aTree[0]==0){
    aTree[0]=key;

    return; // <-
}

(或者将方法的其余部分放在 else block 中，我猜。)

我自己编译并运行它，发现了一些其他简单的错误。

每次调用 insert 时都会创建一个新数组:

public void insert(int key){
    aTree=new int [100];

所以你可以移动new int[100]至 aTree 的声明:

public class BSTreeArray {
    int [] aTree = new int[100]; // <-

您正在调用 preOrder与 aTree[0]而不是0 :

preOrder(aTree[0], "");

应该是:

preOrder(0, "");

内部preOrder ，你有idx>aTree.length :

if(idx>aTree.length){

这将生成越界异常，因为数组索引为 0...length - 1所以应该是>= :

if(idx>=aTree.length){

最后，由于您使用 0 来指示空节点，因此您不妨在 preOrder 中检查该节点。 :

if(aTree[idx] != 0)
    System.out.println(i+aTree[idx]);

之后的输出是:

Pre-Order:
50
.25
..10
...5
...15
..29
...33
.75
..53
..79
...78
...111

作为建议，您可能希望将数组设置为 Integer[]而不是int[] 。这意味着您的 int 值将被装箱，但它允许您使用 null 来指示空节点而不是 0。另一种方法是使用 long[]并将空值设置为 int 无法存储的某个值，例如 1L << 63L (即 Long.MIN_VALUE )。