使用数组的二叉树

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; 
     } 
    } 
} 

这可能玷污然后插件的所有其余的，因为它们可能会被跳过前面一个节点，如果他们的第一个节点的权利。

好像你应该这样做：（或者把方法的其余部分在else块我猜）

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

    return; // <- 
} 

我编译并运行它自己并注意到一些其他简单的错误。

你在每次调用创建一个新的阵列插入：

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

所以，你可以移动到new int[100]的aTree声明：你跟aTree[0]调用preOrder

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

而不是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）那样存储。