[자바] Tree의 개념, 종류, 재귀함수를 이용한 구현까지

트리(Tree)

노드와 링크로 구성된 자료구조를 말한다.
폴더, 조직도 등의 계층적 구조를 나타낼 때 사용한다.

용어설명 (위 사진참고)

• Node: 트리구조에서 값을 담고있는 단위
• Edge: 노드간 연결선 (link 혹은 branch라고도 함)
• Root: 부모가 없는 최상단의 노드 (A)
• Leaf: 자식이 없는 노드 (E, F, G)
• 내부노드: Leaf 노드를 제외한 나머지 노드
• 부모노드: (상대적 개념) 연결된 두 노드 중 상위 노드
• 자식노드: (상대적 개념) 연결된 두 노드 중 하위 노드
• 형제노드: 같은 부모와 연결된 노드
• Depth: 루트(최상단 노드)에서 특정 노드까지 Edge의 수
• Level: 트리의 깊이를 의미함. Lv.0부터 시작한다. (Lv.2: D, E, F)
• Height: 가장 큰 레벨값
• Size: 자신 노드를 포함하여 자식 노드의 개수
• 차수: 각 노드가 가진 Edge의 수
• 트리의 차수: 트리에서 하나의 노드가 가지고 있는 최대 Edge의 수

특징

• 특정 노드에서 특정 노드로 이동하는 경우는 단 한가지다.
• 노드가 N개일 경우 트리의 전체 Edge 수는 N-1
• Cycle이 존재하지 않는 Acyclic 구조 (트리와 그래프의 차이점)
• 하나의 Edge를 끊으면, 별개의 트리 생성으로 간주함. (Sub-Tree)

이진트리 (Binary Tree)

• 각 노드는 최대 2개의 자식을 가질 수 있다.
  자식 노드는 좌우로 구분함.

이진트리의 종류

1. 포화 이진트리: 모든 레벨에서 각 노드마다 Edge가 2개씩 완전히 채워진 트리를 말한다.
   
   
2. 완전 이진트리: 마지막 레벨을 제외하고 모든 레벨 구간에서 노드들이 모두 채워진 트리를 말한다.
   
   
3. 정 이진트리: 모든 레벨에서 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리. (1개는 X)
   
   
4. 편향트리: 모든 레벨에서 모든 노드가 1개의 Edge만 갖는 트리 (한쪽으로 기울어진 모양이다.)
   
   
5. 균형 이진트리: 모든 레벨 구간에서 트리의 좌우 Edge를 끊었을 때, 끊어진 좌우의 서브트리 높이차이가 1을 초과하지 않는 트리.
   • D-B-A-C 트리에서 A를 기준으로 좌우를 끊을 경우 D-B-와 -C가 생성된다. 이 둘은 트리높이가 각각 2와 1이므로 D-B-A-C는 균형 이진트리다.
   • 균형 이진트리가 그렇지 않은 트리보다 탐색속도가 더 빠르다.
     
     
     

이진트리의 특징

• 포화이진트리의 높이가 h면, 노드의 수는 2^(h+1) - 1
  

  

• 사진에서 h = 1이므로 식에 대입하면 노드의 수는 3
  
  
• 포화이진트리, 완전이진트리의 노드 개수가 N일때 높이는 log(2)N
• 이진트리의 노드 개수가 N일때 가능한 최대 높이는 N-1
  
  
  

이진트리의 순회 (Traversal)

• 이진트리에 존재하는 모든 노드를 딱 한번씩 방문하는 연산(중복X)
• 순회 종류는 4가지
  • 전위순회, 중위순회, 후위순회: Depth중심의 DFS 순회방법.
  • 레벨순회: 각 레벨별로 차례차례 순회하는 BFS 순회방법.
    
    
    
    

이진트리의 순회 종류와 구현

• 전위순회, 중위순회, 후위순회 각각을 재귀함수로 구현하는 방식은 출력 위치에만 차이를 두고 나머지 코드의 구조는 비슷하다.

전위순회

현재노드-> 왼쪽노드 최대Depth까지 -> 오른쪽노드

class BinaryTree {
    char[] arr;

    BinaryTree(char[] data) {
        this.arr = data.clone();
    }

    public void preOrder(int idx) {
    
        System.out.print(this.arr[idx] + " "); 

        int left = 2 * idx + 1; // 트리 구조에 따른 left와 right의 위치는 이렇다.
        int right = 2 * idx + 2;
        
        if (left < this.arr.length) { //
            this.preOrder(left);
        }
        // 재귀함수를 돌면서 left의 left노드부터 모드 호출

        if (right < this.arr.length) {
            this.preOrder(right);
            
        // left의 left노드 호출이 최대 레벨까지 끝난 후 right노드 호출
        }
    }
}    

 

중위순회

왼쪽노드 -> 현재노드 -> 오른쪽노드

    public void inOrder(int idx) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;

        if (left < this.arr.length) {
            this.inOrder(left); // 노드의 left노드가 있으면 따라 내려간다
        }

        System.out.print(this.arr[idx] + " ");
        
        // 최대 레벨까지 간 후에 left노드 호출

        if (right < this.arr.length) {
            this.inOrder(right);
        }
    }

 

후위순회

왼쪽노드 -> 오른쪽노드 -> 현재노드

    public void postOrder(int idx) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;

        if (left < this.arr.length) {
            this.postOrder(left); //
        }


        if (right < this.arr.length) {
            this.postOrder(right);
        }

        System.out.print(this.arr[idx] + " ");
    }

 

레벨순회

각 레벨별로 좌에서 우로 순회

    public void levelOrder(int idx) {
        for (int i = 0; i < this.arr.length; i++) {
            System.out.print(this.arr[i] + " ");
            // 레벨오더는 각각의 레벨을 순서대로 좌->우로 순회한다.
        }
    }