[자료구조] 트리(Tree)

이번시간에는 트리에 대해 공부해보겠습니다.

 

앞서 올린 포스팅 스택, 큐, 배열은 모두 선형구조입니다. 자료들이 모두 선의 형태로 나열되어 있죠. 하지만 트리의 경우는 비선형 자료구조인데, 그 중에서도 자료들 간에 계층관계를 가진 계층형 자료구조라고 부릅니다.

 

 

• 루트(root) : 부모가 없는 노드, 그림에서는 A노드 입니다.
• 간선(edge) : 노드를 연결하는 선
• 노드의 차수 : 한 노드가 가지는 서브 트리의 수, 즉 자식 노드의 수. A의 차수는 3, B의 차수는 2
• 트리의 차수 : 트리에 속한 노드의 최대 차수
• 레벨 : 트리의 각 층에 매겨진 번호, 처음부터 0,1,2,3...레벨
• 높이 : 트리의 속한 노드들의 레벨
• 포레스트 : 트리의 집합. [F,K,L], [G,L], [B,E,F,J,K].....등
• 단말노드 : 차수가 0인 노드, 즉 자식노드가 없는 노드. E,J,K,H,I
• 자식노드 : 노드X의 서브 트리의 루트노드. D의 자식 노드는 G,H,I
• 자손노드 : 서브 트리상의 모든 노드들. B의 자손노드는 E,F,J,K
• 형제노드 : 부모가 같은 노드. B의 형제노드는 C,D
• 조상노드 : 루트부터 임의의 노드까지 이르는 경로상에 있는 노드들. L의 조상노드는 A,D,G

 

이진트리

이진트리는 모든 노드의 차수가 최대2개인 트리를 말합니다. 이진트리는 왼쪽 자식노드와 오른쪽 자식노드 2개만을 가질 수 있음여, 아무것도 없는 공백노드도 이진 트리의 노드로 취급합니다. 그리고 이진트리는 다음과 같은 특징을 가집니다.

 

• n개의 노드를 가진 이진 트리는 항상(n-1)개의 간선을 가진다.
• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)이며, 최대 (2^h+1 -1)개 입니다.

일반적인 이진트리 이외에 모든 레벨과 노드 수에 대해서 일정한 관계를 가지는 이진 트리의 종류로 포화 이진트리, 완전 이진 트리, 편향 이진 트리가 있습니다.

 

 

포화 이진 트리

모든 레벨에 노드가 꽉 차서 포화 상태인 이진 트리를 의미합니다. 포화 이진 트리는 높이가 h일때, (2^h+1 -1)개의 최대 노드수를 갖는 이진 트리입니다.

 

 

완전 이진 트리

완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드들이 왼쪽부터 차례대로 채워져 있는 트리를 말합니다. 위의 트리는 마지막 레벨에서 왼쪽부터 값이 채워져 있기 때문에 완전 트리입니다.

 

 

편향 이진 트리

 

이진 트리 중에서 최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리입니다.

 

 

이진트리 구현

이진트리를 구현하는 방법에는 배열을 이용한 순차 자료구조 방식과 연결 자료구조 방식이 있습니다.

 

 

순차자료구조 방식

 

이진 트리를 배열로 표현하는 방법은 높이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스로 사용하여 1차원 배열로 표현하는 것입니다. 1차원 배열에서 인덱스 계산을 위해 간단히 하기 위해 인덱스 0번은 실제로 사용하지 않고, 항상 1번에 루트를 저장합니다.

노드의 개수가 n개인 이진 트리를 1차원 배열을 사용하여 표현하면 각 노드의 부모노드가 저장된 배열 인덱스와 자식 노드가 저장된 배열 인덱스에 대해 다음과 같은 규칙을 찾을 수 있습니다.

 

 

연결자료구조 방식

 

배열을 이용한 순차 자료구조 방식은 쉽게 만들 수 있지만, 만약 편향 이진 트리의 경우를 구현할 경우 많은 공간이 낭비되게 됩니다. 이런 메모리 낭비 문제와 삽입/삭제 연산이 비효율적이라는 순차 자료구조 방식의 문제 때문에 연결 자료구조 방식을 많이 사용합니다.

 

연결 자료구조 방식은 노드를 사용하는데 구조는 데이터를 저장하는 데이터 필드와 왼쪽 자식노드를 연결하는 왼쪽 링크 필드, 오른쪽 자식 노드를 연결하는 오른쪽 링크 필드로 구성됩니다.

 

public class Main {
    public static void main(String[] args) {

        TreeNode bt1 = new TreeNode("One");

        TreeNode bt2 = new TreeNode("Two");

        TreeNode bt3 = new TreeNode(3);

        TreeNode bt4 = new TreeNode(4);

        bt1.makeLeft(bt2);
        bt1.makeRight(bt3);
        bt2.makeLeft(bt4);

        System.out.println(bt1.getLeft().getData());
        System.out.println(bt1.getRight().getData());
    }
}

class TreeNode {

    private TreeNode left;
    private TreeNode right;
    private Object data;

    TreeNode(Object item) {
        left = null;
        right = null;
        data = item;
    }

    void makeLeft(TreeNode node) {
        if (this.left == null) {
            this.left = node;
        }
    }

    void makeRight(TreeNode node) {
        if (this.right == null) {
            this.right = node;
        }
    }

    Object getData() {
        return this.data;
    }

    TreeNode getLeft() {
        return this.left;
    }

    TreeNode getRight() {
        return this.right;
    }
}

 

 

이진트리 순회

이진 트리에 있는 모드 노드들을 한번씩 모두 방문하요 노드가 가지고 있는 데이터를 처리하는 것을 순회라고 합니다. 리스트나 스택, 큐와 같은 선형 자료구조는 순회하는 방법이 한 가지였지만, 트리는 계층적인 구조를 가지고 있기 때문에 여러가지 순회 방법이 있습니다. 그리고 각 노드들을 순회할 때는 재귀적으로 반복하게 됩니다.

 

전위 순회

전위 순회(Preorder Traversal)은 현재 노드를 방문하는 D작업을 가장 먼저 수행하여 DLR순서로 순회하는 방법입니다. 

(1) 현재 노드n을 방문한다 : D
(2) 현재 노드 n의 왼쪽 서브 트리로 이동한다 : L
(3) 현재 노드 n의 오른쪽 서브 트리로 이동한다 : R

 

결과 : -*AB/CD

 

 

 

중위 순회

중우 순회(Inorder Tracersal)은 현재 노드를 방문하는 D작업을 L작업과 R작업 중간에 수행하여 LDR순서로 순회하는 방법입니다.

(1) 현재 노드n의 왼쪽 서브 트리로 이동한다 : L
(2) 현재 노드 n을 방문한다 : D
(3) 현재 노드 n의 오른쪽 서브 트리로 이동한다 : R

결과 : A*B-C/D

 

 

후위 순회

후위 순회(Postorder Traversal)은 현재 노드를 방문하는 D작업을 가장 나중에 수행하여 LRD의 순서로 순회하는 방법입니다.

(1) 현재 노드n의 왼쪽 서브 트리로 이동한다 : L
(2) 현재 노드 n의 오른쪽 서브 트리로 이동한다 : R
(3) 현재 노드 n을 방문한다 : D

결과 : AB*CD/-