AVLツリーはインオーダートラバーサルが

Question

マイAVLツリーは整数avlTree[35][5]の二次元アレイを使用して、Javaで実装されて動作していない - 列が表す：

• [0] - 左高
• [1 ] - 左の子
• [2] - データ
• [3] - 右の子
• [4] - 高右。

私はメインプログラムから次のメソッドを呼び出しています。その結果、3つのノードが得られます。一番左のノードに2回続けて親が続きます。

public void inorderTraversal(int root) { 
    if ((Main.avlTree[root][1] == 0) && (Main.avlTree[root][3] == 0)) { 
     System.out.println(Main.avlTree[root][2]); 
    } else { 
     if (Main.avlTree[root][1] != 0) { 
      root = Main.avlTree[root][1]; 
      inorderTraversal(root); 
     } 
     System.out.println(Main.avlTree[root][2]); 

     if (Main.avlTree[root][3] != 0) { 
      root = Main.avlTree[root][3]; 
      inorderTraversal(root); 
     } 
    } 
} 

Answer 1

私はこのテストプログラムを書いた：

public class AVLTree { 

    /* 
     [0] - Height Left 
     [1] - Left Child 
     [2] - Data 
     [3] - Right Child 
     [4] - Height Right. 
    */ 
    private static int[][] avlTree; 

    public static void main(String[] args) { 
     avlTree = new int[4][5]; 

     // root (L: 1; R: 3) 
     avlTree[0][0] = 0; 
     avlTree[0][1] = 1; 
     avlTree[0][2] = 3005; 
     avlTree[0][3] = 2; 
     avlTree[0][4] = 1; 

     // parent: root (L: -1; R: -1) 
     avlTree[1][0] = 0; 
     avlTree[1][1] = -1; 
     avlTree[1][2] = 73375; 
     avlTree[1][3] = -1; 
     avlTree[1][4] = 0; 

     // parent: root (L: 3; R: -1) 
     avlTree[2][0] = 0; 
     avlTree[2][1] = 3; 
     avlTree[2][2] = 831954; 
     avlTree[2][3] = -1; 
     avlTree[2][4] = 0; 

     // parent: 2 (L: -1; R: -1) 
     avlTree[3][0] = 0; 
     avlTree[3][1] = -1; 
     avlTree[3][2] = 7485; 
     avlTree[3][3] = -1; 
     avlTree[3][4] = 0; 

     inOrder(0); 
    } 

    private static void inOrder(int root) { 
     if(root == -1) { 
      // nothing to do 
      return ; 
     } 

     // call function with left child 
     inOrder(avlTree[root][1]); 

     // print root 
     System.out.println(avlTree[root][2]); 

     // call function with right child 
     inOrder(avlTree[root][3]); 
    } 
} 

をし、期待通りの出力は次のようになります。

あなたのコードにも問題はありません。それは私のテストでうまく動作します。多分あなたの木は偽ですか？右または左の子として-1を使用することをお勧めします。それ以外の場合、0はpositon 0のノードを意味する可能性があるため、少し誤解を招く可能性があります。