AVL樹中序遍歷不工作

我的AVL樹使用整數avlTree[35][5]的二維陣列中的Java實現的 - 該列表示：AVL樹中序遍歷不工作

[0] - 高度左
[1 ] - 左子
[2] - 數據
[3] - 右子
[4] - 高度右。

我從主程序中調用下面的方法，結果我得到三個節點：最左邊的節點兩次跟着它的父節點。

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

來源

2012-01-13 Star Shine

我想這是一項家庭作業，但聲明方法像'inorderTraversal（** final ** int root）'，它將有助於解決問題。至於StackOverflowError - 很可能你在樹中有一個循環。 – bestsss 2012-01-13 15:50:35

你不需要最終聲明它。類型是int，因此「真實」值不會更改。 – MasterCassim 2012-01-13 15:54:53

@MasterCassim，root代表節點的當前索引，實際上是節點。代碼（'root = ...'）改變了它，因此它被搞砸了。最後是一個提示，因爲這是一個功課。沒有「真正的」價值，而是對有效改變的節點的索引。 – bestsss 2012-01-13 17:52:15

我寫了這個測試程序：

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可能意味着節點在位置0.

來源

2012-01-13 15:19:39 MasterCassim

謝謝...我會嘗試 – 2012-01-13 15:48:16

AVL樹中序遍歷不工作

回答

相關問題