AVL 트리에서 차 순회

Question

내 AVL 트리 정수 avlTree[35][5]의 2 차원 배열을 사용하여 자바로 구현되어 작동하지 않습니다 - 열 대표 :

• [0] - 왼쪽 높이
• [1 ] - 왼쪽 자식
• [2] - 데이터
• [3] - 오른쪽 자식
• [4] - 높이 오른쪽.

주 프로그램에서 다음과 같은 메서드를 호출하면 결과적으로 3 개의 노드가 나타납니다. 가장 왼쪽 노드와 그 부모가 두 번 이어집니다.

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

및 출력이 예상대로 :

73,375
3005
7485
831,954

나는 당신의 코드에도 문제가 없다. 그것은 내 테스트에서 잘 작동합니다. 어쩌면 당신의 나무가 거짓일까요? 또한 -1이 없으면 오른쪽/왼쪽 자식으로 -1을 사용하는 것이 좋습니다. 0은 positon 0에있는 노드를 의미 할 수 있기 때문에 그렇지 않다.