[자료구조] 비선형 자료구조 - 트리

1. 트리란 무엇일까

---

노드와 링크로 구성된 자료구조이다. 그래프의 일종으로 Cycle 이없다. 즉, 비선형 그래프이다. 연결리스트도 트리의 일종으로 볼 수 있다. 계층적 구조를 나타낼 때 사용한다. 예를 들면 폴더구조 (디렉터리, 서브 디렉터리), 조직도, 가계도 등이 있다.

 

(1) 트리의 구조, 특징

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

 

---

 

 

(2) 트리의 특징

• 하나의 노드에서 다른 노드로 이동하는 경로는 유일하다.
• 노드가 N개인 트리의 edge 의 수는 N-1 개 이다.
• Acycle 즉, Cycle 이 존재하지않는다. 비순환이다.
• 모든 노드는 서로 연결되어 있다.
• 하나의 edge를 끊으면 2개의 sub-tree로 분리된다.

 

 

---

 

 

 

2. 이진트리의 종류와 특징

---

(1) 이진트리의 특징

• 각 노드는 최대 2개의 자식을 가질 수 있다.
• 자식 노드는 좌우를 구분한다.
  • 왼쪽 자식 : 부모 노드의 왼쪽 아래
  • 오른쪽 자식 : 부모 노드의 오른쪽 아래

 

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

 

 

(2) 이진트리의 종류

포화 이진 트리 (Perfect Binary Tree) 

- 모든 레벨에서 노드들이 꽉 채워져 있는 트리

 

포화 이진 트리 (Perfect Binary Tree) 

- 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리

 

정 이진 트리 (Full Binary Tree)

- 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

 

편향 트리 (Skewed binary Tree)

- 사향트리 라고도 한다.

- 한쪽으로 기울어진 트리

 

균형 이진 트리 (Balanced binary Tree)

- 모든 노드의 좌우 서브 트리 높이가 1 이상 차이 나지 않는 트리

 

 

 

---

 

 

 

3. 이진트리의 순회

---

• 모든 노드를 빠트리거나 중복하지 않고 방문하는 연산
• 순회 종류는 4가지가 있다.
• 전위 순회, 중위 순회, 후위 순회 -> DFS (Depth-First Search : 깊이 우선 탐색)
• 레벨 순회 -> BFS (Breadth-First Search : 너비 우선 탐색)

 

(1) 전위 순회 (Preorder Traversal)

• 방문 순서 : 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드
• 루트 노드를 먼저 탐색하고, 자식 노드를 탐색하는 방식

 

 

 

(2) 중위 순회 (Inorder Traversal)

• 방문 순서 : 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드
• 왼쪽 자식 노드를 탐색하고, 루트 노드를 탐색하고, 오른쪽 자식 노드를 탐색하는 방식

 

 

 

(3) 후위 순회 (Postorder Traversal)

• 방문 순서 : 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드
• 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식

 

 

 

(4) 레벨 순회 (Level Traversal)

• 방문 순서 : 위쪽 레벨부터 왼쪽 노드 -> 오른쪽 노드
• 루트 노드를 먼저 탐색하고, 그 다음 레벨의 노드를 탐색하는 방식이다. queue 를 이용하여 루트 노드를 넣어준 다음 queue에 넣어둔 노드를 하나씩 탐색하면서 자식 노드를 queue에 추가한다. 이를 queue가 비어있을 때까지 반복한다.

 

 

 

 

---

 

 

4. 이진트리 구현

---

(1) 배열로 이진 트리 구현

class BinaryTree {
    char[] arr;

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

    public void preOrder(int idx) {    // 전위 순회 구현
        System.out.println(this.arr[idx] + " ");
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        if (left < this.arr.length) {
            this.preOrder(left);
        }
        if (right < this.arr.length) {
            this.preOrder(right);
        }
    }

    public void inOrder(int idx) {    // 중위 순회 구현
        int left = idx * 2 + 1;
        int right = 2 * idx + 2;

        if (left < this.arr.length) {
            this.inOrder(left);
        }
        System.out.println(this.arr[idx] + " ");
        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) {
            postOrder(left);
        }
        if (right < this.arr.length) {
            postOrder(right);
        }

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

    public void levelOrder(int idx) {
        for (int i = 0; i < this.arr.length; i++) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }

}

 

 

 

---

 

 

 

(2) 연결리스트로 이진 트리 구현

class Node {
    char data;
    Node left;
    Node right;

    Node(char data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

class BinaryTree2 {    //ArrayList 를 이용한 트리 구현
    Node head;

    BinaryTree2() {
    }

    BinaryTree2(char[] arr) {   // 노드 생성
        Node[] nodes = new Node[arr.length];
        for (int i = 0; i < arr.length; i++) {
            nodes[i] = new Node(arr[i], null, null);
        }

        for (int i = 0; i < arr.length; i++) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < arr.length) {
                nodes[i].left = nodes[left];
            }
            if (right < arr.length) {
                nodes[i].right = nodes[right];
            }
        }
        this.head = nodes[0];
    }

    public void preOrder(Node node) {   //전위 순회
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        this.preOrder(node.left);
        this.preOrder(node.right);
    }

    public void inOrder(Node node) {  //중위 순회
        if (node == null) {
            return;
        }
        this.preOrder(node.left);
        System.out.print(node.data + " ");
        this.preOrder(node.right);
    }

    public void postOrder(Node node) {   // 후위 순회
        if (node == null) {
            return;
        }
        this.postOrder(node.left);
        this.postOrder(node.right);
        System.out.print(node.data + " ");
    }

    public void levelOrder(Node node) {    //레벨 순회
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.println(cur.data + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

}