ArrayindexOutOfBoundsException与最佳二叉搜索树实现java

Question

我正在实施java中的最佳二叉搜索树问题。对于我的程序，我正在阅读一个txt文件，其中第一行是节点数量，每个前面的行由空格分隔，其中第一个元素是节点，第二个元素是概率。下面是我的程序在读取样品输入：

5 
A 0.213 
B 0.547 
D 0.10 
X 0.12 
AAA 0.02 

在我的计划，我想创建一个打印方法，当我运行该程序，我可以看到它是什么节点，其概率是什么，它的父母是什么，他们的孩子是什么。

Node 
Key: B 
Probability: 21.3% 
Parent: (null) 
Left Child: A 
Right Child: X 

，我遇到了现在的问题是，它是阅读的树细根，但随后一段时间后，它会给我一个索引出的问题：一个节点的样本输出下面提供界限。下面是我为我打印树法码

public static void printTree(String keys[], double prob[], int root[][]){ 
System.out.println(""); 
int pos = root[1][keys.length-1]; 
int t=pos; 

for(int i = 0; i < keys.length-1; i ++){ 

    System.out.println("Node Key "+ pos); 
    System.out.println("Key: "+ keys[pos]); 
    System.out.println("Probability: "+ prob[pos]); 

    if(i ==0){ 
     System.out.println("Parent: null"); 
     System.out.println("Left Child: "+ keys[pos-1]); 
     System.out.println("Right Child: "+ keys[pos+1]); 
     if(root[1][pos]==t){ 
      pos-=1; 
     } 
    } 

    else{ 

     System.out.println("Parent: "+ keys[pos+1]); 
     System.out.println("Left Child: "+ keys[pos-1]); //where the error is occurring 
     System.out.println("Right Child: "+ keys[pos+1]); 
     pos--; 
    } 


    System.out.println(""); 
} 
} 

这是我收到的输出，当我运行代码：

Node 
Key: B 
B is the root 

Node Key 2 
Key: B 
Probability: 0.547 
Parent: null 
Left Child: A 
Right Child: D 

Node Key 1 
Key: A 
Probability: 0.213 
Parent: B 
Left Child: null 
Right Child: B 

Node Key 0 
Key: null 
Probability: 0.0 
Parent: A 
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 
at OBST.printTree(OBST.java:62) 
at OBST.main(OBST.java:155 

很显然，我已经尝试增加和减少的大小，但我当我这样做时，我仍然在和IndexOutofBoundsException。我相信问题是，它正在读取根目录，然后它正在列表中并且不停止。

如果有人可以帮助我解决这个问题，我将非常感激！

编辑： 我重建我的打印方法，包括节点，但我仍然得到一个ArrayIndexOutofBoundsException。下面是使用一个节点类

public static void printTree(int i, int j, int pos, String side, String keys[], double prob[], int root[][], Nodes[] node){ 

    int temp;  
    if(i<=j){ 

     temp = root[i][j]; 
     System.out.println("Node"); 
     System.out.println("Key: " + keys[pos]); 

     System.out.println("Probability: "+ prob[pos]+" %"); 
     System.out.println("Parent: "+ keys[pos]); 
     System.out.println(keys[temp] + " is the "+ side +" child of "+ keys[pos]); 
     for(int k =0; k< keys.length-1; k++){ 

      if(keys[pos].equalsIgnoreCase(node[k].getKey())){ 
       if(side.equalsIgnoreCase("left")){ 
        node[i].setLeftChild(keys[temp]); 
       } 
       else{ 
        node[i].setRightChild(keys[temp]); 
       } 

      } 

      System.out.println(" "); 


     } 
     constructTree(i,temp-1,temp,"left", keys, prob, root, node); 
     constructTree(temp+1,j,temp,"right", keys, prob,root, node); 

    } 

这是我收到的输出更新方法：

Node 
Key: B 
Probability: 0.547 % 
Parent: B 
A is the left child of B 





Node 
Key: B 
Probability: 0.547 % 
Parent: B 
X is the right child of B 





Node 
Key: X 
Probability: 0.12 % 
Parent: X 
D is the left child of X 





Node 
Key: X 
Probability: 0.12 % 
Parent: X 
AAA is the right child of X 



Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5 
at OptimalBT.Optimal.constructTree(Optimal.java:117) 
at OptimalBT.Optimal.constructTree(Optimal.java:127) 
at OptimalBT.Optimal.main(Optimal.java:90) 

Answer 1

我在做你正在试图代表您的二叉树为前提一个二维数组。

在你的代码写：

System.out.println("Parent: "+ keys[pos+1]); 
System.out.println("Left Child: "+ keys[pos-1]); 
System.out.println("Right Child: "+ keys[pos+1]); 

这里有几个问题。

首先，你的代码意味着右边的孩子和父母在同一个位置（都在键[pos + 1]）。这是不正确的。正确的孩子与父母不是同一个节点。其次，你的代码意味着左边的孩子在键[pos-1]处，右边的孩子在键[pos + 1]处。这是不正确的。对于数组中位置“K”处的任何节点，该节点的左侧子节点位于“2K”位置，该节点的右侧子节点位于“2K + 1”位置。

这是一幅很好的图片，我为阿尔伯塔大学CS网站提供了参考。它应该可以帮助你理解如何使用二维数组索引来表示二叉树。

Source

我期待你的投入实际上是这种格式，而你没有意识到这一点。这将意味着你确实有以下作为输入：

节点{名，父，left_child，right_child，机会}

Node1 {A, null, B, D, 21.3} 
Node2 {B, A, X, AAA, 54.7} 
Node3 {D, A, null, null, 10.0} 
Node4 {X, B, null, null, 12.0} 
Node5 {AAA, B, null, null, 2.0} 

Answer 2

指数不回绕这样。您的数组键的索引从0到keys.length-1。所以当你做System.out.println("Left Child: "+ keys[pos-1]);当pos为0时，你试图访问索引-1，就像你在错误信息中看到的那样，你的程序不能访问索引-1。

但是我有点难以弄清楚你到底想要什么。我也不知道你如何插入节点，所以我不能说如果打印是正确的。所以我的答案是有限的。

但根据你的评论，你想要它访问索引4当发生这种情况是keys.length-1。要做到这一点，你需要环绕。最简单的方法是使用模数。所以，而不是使用keys[pos-1]，你会使用keys[(pos-1)%keys.length]或keys[(pos+1)%keys.length]。