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 网站截取的一张漂亮图片。它应该可以帮助您了解如何使用二维数组索引来表示二叉树。
我希望你的输入实际上是这种格式,而你并没有意识到。这意味着您实际上将以下内容作为输入:
节点{名称,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]
。
我正致力于在 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 网站截取的一张漂亮图片。它应该可以帮助您了解如何使用二维数组索引来表示二叉树。
我希望你的输入实际上是这种格式,而你并没有意识到。这意味着您实际上将以下内容作为输入:
节点{名称,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]
。