最適なバイナリ検索ツリーを実装したArrayindexOutOfBoundsException java

Question

私はJavaで最適なバイナリ検索ツリーの問題を実装しようとしています。私のプログラムでは、最初の行がノードの数であり、各前の行が最初の要素がノードで、2番目の要素が確率であるスペースで区切られたtxtファイルを読み込んでいます。以下は、私のプログラムを読み込み、サンプル入力である：私のプログラムで

5 
A 0.213 
B 0.547 
D 0.10 
X 0.12 
AAA 0.02 

が、私はプログラムを実行するとき、私はその確率が何であるか、それが何であるかのノードを参照することができるように、印刷法を作成しようとしていますその親は何か、そして彼らの子供は何か。 1つのノードの出力例を以下に示す。

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

私は今に実行しています問題は、それが木の罰金のルートを読んでいるということですが、その後しばらくした後、それは私のうち指標を与えます境界。私はサイズを増減しようとしている

明らか

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 

、私：以下は私のプリントツリー方式のための私のコード

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(""); 
} 
} 

は、これは私が自分のコードを実行したとき、私は受け付けており出力されています私はそれを行うときにまだ取得してIndexOutofBoundsExceptionです。私は問題が何であるか、ルートを読んでいることを信じています。それからリストの下に落ちて止まりません。

誰かがこの問題で私を助けることができたら、私は非常に感謝します！

EDIT： ノードを含む印刷メソッドを再構築しましたが、ArrayIndexOutofBoundsExceptionがまだ表示されています。

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

私はあなたのようにあなたのバイナリツリーを表現しようとしている仮定を作っています：次は、これは私が受けていた出力がある

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

    } 

ノードクラスを使用する更新方法であり、 2次元配列。あなたが書いたあなたのコードで

：

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]の両方）。これは正しくありません。右の子は親と同じノードではありません。

第2に、左の子がkeys [pos-1]にあり、右の子がkeys [pos + 1]にあることを意味します。これは正しくありません。配列内の位置「K」にある任意のノードについて、そのノードの左の子は位置「2K」にあり、そのノードの右の子は位置「2K + 1」にある。

私はアルバータ州立大学のウェブサイトのためにうんざりした素敵な絵です。 2次元配列インデックスを使用してバイナリツリーを表現する方法を理解するのに役立ちます。

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にすると、インデックス-1にアクセスしようとしています。プログラムがインデックス-1にアクセスできないというエラーメッセージが表示されます。

しかし、私はちょっとあなたが欲しいものを見つけようとするのに苦労しています。また、どのようにノードを挿入するのかわからないので、プリントが正しいかどうかはわかりません。だから私の答えは幾分限られています。

あなたのコメントに基づいて、それが起きたときにインデックス番号4にアクセスします。これはkeys.length-1です。そうするためにはラップアラウンドが必要です。最も簡単な方法はモジュロを使うことです。したがって、keys[pos-1]の代わりにkeys[(pos-1)%keys.length]またはkeys[(pos+1)%keys.length]を使用します。