ArrayindexOutOfBoundsException 与最佳二进制搜索树实现 java

ArrayindexOutOfBoundsException with Optimal Binary Search Tree implementation java

我正致力于在 java 中实现最优二叉搜索树问题。对于我的程序,我正在读取一个 txt 文件,其中第一行是节点数,前一行由 space 分隔,其中第一个元素是节点,第二个元素是概率.下面是我的程序读取的示例输入:

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

Obviously I have tried increasing and decreasing the size, but I am still getting and IndexOutofBoundsException at when I do that. I believe what the problem is, is that it is reading the root, and then it is going down the list and doesn't stop.

如果有人能帮我解决这个问题,我将不胜感激!

编辑: 我重构了我的打印方法以包含节点,但是我仍然收到 ArrayIndexOutofBoundsException。以下是使用节点 class

的更新方法
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)

我假设您正在尝试将二叉树表示为二维数组。

在你的代码中你写:

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

这里有几个问题。

首先,您的代码暗示右 child 与 parent 位于同一位置(均在键 [pos+1] 处)。这是不正确的。右边的child和parent不是同一个节点。

其次,您的代码暗示左侧 child 位于键 [pos-1] 处,右侧 child 位于键 [pos+1] 处。这是不正确的。对于数组中位置 "K" 处的任何节点,该节点的左侧 child 位于位置“2K”,该节点的右侧 child 位于位置“2K + 1”。

这是我为阿尔伯塔大学 CS 网站截取的一张漂亮图片。它应该可以帮助您了解如何使用二维数组索引来表示二叉树。

Source

我希望你的输入实际上是这种格式,而你并没有意识到。这意味着您实际上将以下内容作为输入:

节点{名称,parent,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} 

指数不会像那样环绕。您的数组键的索引从 0 到 keys.length-1。因此,当您执行 System.out.println("Left Child: "+ keys[pos-1]); 当 pos 为 0 时,您正在尝试访问索引 -1,正如您在错误消息中看到的那样,指出您的程序无法访问索引 -1。

然而,我很难弄清楚您到底想要什么。我也不知道你是如何插入节点的,所以我不能说打印是否正确。所以我的回答有些局限。

但是根据您的评论,您希望它在 keys.length-1 发生时访问索引 4。为此,您需要环绕。最简单的方法是使用模数。因此,不要使用 keys[pos-1],而是使用 keys[(pos-1)%keys.length]keys[(pos+1)%keys.length]