Tree (트리)

1. 트리 (Tree)

• 노드와 링크로 구성된 자료구조 (그래프의 일종, Cycle 없음)
• 계층적 구조를 나타날 때 사용
  • 폴더 구조 (디렉토리, 서브 디렉토리)
  • 조직도, 가계도, …

  

  • 노드(Node): 트리 구조의 자료 값을 담고 있는 단위
  • 에지(Edge): 노드 간의 연결선 (=link, branch)
  • 루트 노드(Root): 부모가 없는 노드, 가장 위의 노드
  • 잎새 노드(Leaf): 자식이 없는 노드 (=단말)
  • 내부 노드(Internal): 잎새 노드를 제외한 모든 노드
  • 부모(Parent): 연결된 두 노드 중 상위의 노드
  • 자식(Child): 연결된 두 노드 중 하위의 노드
  • 형제(Sibling): 같은 부모를 가지는 노드
  • 깊이(Depth): 루트에서 어떤 노드까지의 간선의 수
  • 레벨(Level): 트리의 특정 깊이를 가지는 노드 집합
  • 높이(Height): 트리에서 가장 큰 레벨 값
  • 크기(Size): 자신을 포함한 자식 노드의 개수
  • 차수(Degree): 각 노드가 지닌 가지의 수
  • 트리의 차수: 트리의 최대 차수

2. 트리의 특징

• 하나의 노드에서 다르 노드로 이동하는 경로는 유일
• 노드가 N개인 트리의 Edge의 수는 N-1개
• Acyclc(Cycle이 존재하지 않음)
• 모든 노드는 서로 연결되어 있음
• 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리

3. 이진 트리(Binary Tree)

• 각 노드는 최대 2개의자식을 가짐
• 자식 노드는 좌우를 구분함
  • 왼쪽 자식 : 부모 노드의 왼쪽 아래
  • 오른쪽 자식 : 부모 노드의 오른쪽 아래

  

4. 이진 트리 종류 (1)

• 포화 이진 트리 (Perfect binary tree)
  • 모든 레벨에서 노드들이 꽉 채워져 있는 트리
• 완전 이진 트리 (Complete Binary tree)
  • 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리

5. 이진 트리 종류 (2)

• 정 이진 트리 (Full Binary Tree)
  • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
• 편향 트리 (Skewed Binary Tree) = 사향 트리
  • 한 쪽으로 기울어진 트리

6. 이진 트리 종류 (3)

• 균형 이진 트리 (Balanced Binary Tree)
  • 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리

7. 이진 트리 특징

• 포화 이진 트리의 높이가 h일 때, 노드의 수는 2^(h+1) - 1개
• 포화(or 완전) 이진 트리의 노드가 N개 일때, 높이는 logN
• 이진 트리의 노드가 N개 일 때, 최대 가능 높이는 N

8. 이진 트리의 순회 (Traversal)

• 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산

• 순회 종류는 4가지

  1) 전위 순회

  

  

    // Practice1
    // 배열을 이용한 이진 트리 구성, 순회
      
    class BinaryTree {
        char[] arr;
      
        BinaryTree(char[] data) {
            this.arr = data.clone();
        }
      
        public void preOrder(int idx) {
            System.out.print(this.arr[idx] + " ");
            int left = idx * 2 + 1;
            int right = idx * 2 + 2;
            if (left < this.arr.length) {
                this.preOrder(left);
            }
      
            if (right < this.arr.length) {
                this.preOrder(right);
            }
        }
      
    }
      
    public class Practice1 {
        public static void main(String[] args) {
            // Test code
            char[] arr = new char[10];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (char)('A' + i);
            }
      
            BinaryTree bt = new BinaryTree(arr);
      
            System.out.println("== Preorder ==");
            bt.preOrder(0);
            System.out.println();
      
        }
    }
  

  2) 중위 순회

  

  

    // Practice1
    // 배열을 이용한 이진 트리 구성, 순회
      
    class BinaryTree {
        char[] arr;
      
        BinaryTree(char[] data) {
            this.arr = data.clone();
        }
      
        public void inOrder(int idx) {
        int left = idx * 2 + 1;
        int right = idx * 2 + 2;
  
        if (left < this.arr.length) {
            this.inOrder(left);
        }
  
        System.out.print(this.arr[idx] + " ");
  
        if (right < this.arr.length) {
            this.inOrder(right);
        }
    }
      
    }
      
    public class Practice1 {
        public static void main(String[] args) {
            // Test code
            char[] arr = new char[10];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (char)('A' + i);
            }
      
            BinaryTree bt = new BinaryTree(arr);
      
        System.out.println("== Inorder ==");
        bt.inOrder(0);
        System.out.println();
      
        }
    }
  

  3) 후위 순회

  

  

    // Practice1
    // 배열을 이용한 이진 트리 구성, 순회
      
    class BinaryTree {
        char[] arr;
      
        BinaryTree(char[] data) {
            this.arr = data.clone();
        }
      
        public void postOrder(int idx) {
            int left = idx * 2 + 1;
            int right = idx * 2 + 2;
      
            if (left < this.arr.length) {
                this.postOrder(left);
            }
      
            if (right < this.arr.length) {
                this.postOrder(right);
            }
      
            System.out.print(this.arr[idx] + " ");
        }
      
    }
      
    public class Practice1 {
        public static void main(String[] args) {
            // Test code
            char[] arr = new char[10];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (char)('A' + i);
            }
      
            BinaryTree bt = new BinaryTree(arr);
          
            System.out.println("== Postorder ==");
            bt.postOrder(0);
            System.out.println();
      
        }
    }
  

  4) 레벨 순회

  

  

    // Practice1
    // 배열을 이용한 이진 트리 구성, 순회
      
    class BinaryTree {
        char[] arr;
      
        BinaryTree(char[] data) {
            this.arr = data.clone();
        }
      
        public void levelOrder(int idx) {
            for (int i = 0 ; i < this.arr.length ; i++) {
                System.out.print(this.arr[i] + " ");
            }
        }
    }
      
    public class Practice1 {
        public static void main(String[] args) {
            // Test code
            char[] arr = new char[10];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (char)('A' + i);
            }
      
            BinaryTree bt = new BinaryTree(arr);
      
            System.out.println("== Levelorder ==");
            bt.levelOrder(0);
            System.out.println();
        }
    }