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树中序遍历不工作

回答

相关问题