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]。