이진 트리(Binary Trees)

이진 트리의 정의

이진 트리의 성질

이진 트리의 표현 - 배열

이진 트리의 표현 - 연결 리스트

이진 트리 운행

중순위 운행

후순위 운행과 전순위 운행

레벨 순위 운행

이진 트리의 정의

이진 트리는 분지수가 2 이하인 트리이다. 일반적으로 트리에서는 부트리의 순서를 중요시하지 않으나, 이진 트리에서는 왼쪽 부트리와 오른쪽 부트리를 구분하여 말한다.

이진 트리는 노드의 유한 집합으로써,

(a) 노드의 집합이 공집합이거나,

(b) 루트와 왼쪽 부트리와 오른쪽 부트리라고 부르는 두 개의 서로 다른 이진 트리로 구성된다.

이진 트리의 특별한 경우로 skewed binary tree, 완전 이진 트리(complete binary tree), 포화 이진 트리(full binary tree) 등이 있다.

이진 트리의 성질

성질 1.

(a) 레벨 [eqn: i]에 있는 노드의 개수는 최대 [eqn: 2^i]이다.

(b) 깊이가 [eqn: k]인 이진 트리의 최대 노드 수는 [eqn: SUM from { 0 <= i <= k } 2^i] = [eqn: 2^k+1 - 1]이다.

위 성질을 증명하여 보시오.

성질 2. 노드의 수가 [eqn: 1] 이상인 이진 트리 T에서 분지수가 [eqn: i]인 노드의 수를 [eqn: n_i]라고 할 때, [eqn: n_0 = n_2 + 1]이 성립한다.

증명. T의 노드의 개수를 [eqn: n], 에지의 수를 [eqn: e]라고 하자.

[eqn: n = n_0 + n_1 + n_2]

[eqn: e = 1 cdot n_1 + 2 cdot n_2]

[eqn: e = n - 1]

위의 식으로부터 [eqn: n_0 = n_2 + 1]을 얻을 수 있다.

이진 트리의 표현 - 배열

성질. [eqn: n]개의 노드를 가진 완전 이진 트리가 위와 같은 방식으로 표현되어 있다고 하자.

(a) 노드 [eqn: i]의 부모 노드는 [eqn: LFLOOR{ i/2 }RFLOOR]이다. 단, [eqn: i ne 1].

(b) 노드 [eqn: i]의 왼쪽 자식 노드는 [eqn: 2i]이다. 단, [eqn: 2i <= n].

(c) 노드 [eqn: i]의 오른쪽 자식 노드는 [eqn: 2i+1]이다. 단, [eqn: 2i+1 <= n].

모든 이진 트리를 배열을 이용하여 표현할 수 있으나, 대부분의 경우는 메모리를 낭비하게 된다.

이진 트리의 표현 - 연결 리스트

배열을 이용한 이진 트리의 표현에서는 메모리의 낭비뿐만 아니라 이진 트리의 가운데에 노드를 삽입하거나 삭제할 경우에 많은 노드들의 이동이 발생하게 된다. 연결 리스트 표현에서는 이러한 문제를 극복할 수 있다.

이진 트리 운행 (Binary Tree Traversals)

이진 트리에 대한 연산은 여러 가지가 있을 수 있으나 가장 흔히 일어나는 것이 트리의 운행, 즉 트리의 각 노드를 한번씩 방문하는 것이다. 이것은 주로 트리의 노드에 저장되어 있는 정보에 체계적인 접근 방식이 필요할 때 사용된다.

- 중순위 운행(inorder traversal), LvR

- 후순위 운행(postorder traversal), LRv

- 전순위 운행(preorder traversal), vLR

- 레벨순위 운행(level order traversal)

수식 트리(expression tree)

inorder traversal sequence:   A / B * C * D + E

postorder traversal sequence: A B / C * D * E +

preorder traversal sequence:  + * * / A B C D E

중순위 운행

중순위 운행은 자연스럽게 재귀 함수로 나타낼 수 있다. 여기서는 트리의 노드를 방문하여 노드에 저장되어 있는 데이터를 출력한다고 가정한다.

void inorder(tree_pointer ptr)

{

if (ptr) {

inorder(ptr->left_child);

printf("%d", ptr->data);

inorder(ptr->right_child);

}

}

앞의 수식트리에 inorder()를 적용하여 보시오. 그리고 이 알고리즘의 시간 복잡도가 O(n)이 됨을 설명하여 보시오.

중순위 운행 (계속)

중순위 운행을 반복적인 방식으로 기술할 수 있다. 이 때에는 재귀 함수가 가지고 있는 시스템 스택을 대신할 수 있는 스택이 필요하다. 함수 pop()은 스택이 비어있을 때 NULL을 넘겨  준다고 가정한다.

void inorder2(tree_pointer ptr)

{

int top = 0; // 스택 초기화

tree_pointer stack[N];

for (;;) {

for (; ptr; ptr=ptr->left_child)

push(&top, ptr);

ptr = pop(&top);

if (!ptr) break;

printf("%d", ptr->data);

ptr = ptr->right_child;

}

}

앞의 수식트리에 inorder2()를 적용하여 보시오. 그리고 이 알고리즘의 시간 복잡도가 O(n)이 됨을 설명하여 보시오.

후순위 운행과 전순위 운행

후순위 운행과 전순위 운행도 중순위 운행과 마찬가지고 재귀적으로 구현할 수도 있고, 또한 반복적으로 구현할 수도 있다.

void postorder(tree_pointer ptr)

{

if (ptr) {

postorder(ptr->left_child);

postorder(ptr->right_child);

printf("%d", ptr->data);

}

}

void preorder(tree_pointer ptr)

{

if (ptr) {

printf("%d", ptr->data);

preorder(ptr->left_child);

preorder(ptr->right_child);

}

}

앞의 수식트리에 postorder()와 preorder()를 적용하여 보시오. 그리고 이들 알고리즘의 시간 복잡도가 모두 O(n)이 됨을 설명하여 보시오.

레벨 순위 운행

앞에서 소개한 중순위, 후순위, 전순위 운행은 재귀적으로 구현되었다고 하더라도 스택을 사용하지만, 레벨 순위 운행은 큐를 사용한다. 함수 enqueue()와 dequeue()는 다음과 같이 선언되어 있고, dequeue()는 큐가 비어 있을 때 NULL을 되돌려 준다고 가정한다.

void enqueue(int *rear_ptr, int front, element item)

element dequeue(int *front_ptr, int rear)

void levelorder(tree_pointer ptr)

{

int front = rear = 0; // 큐 초기화

tree_pointer queue[N];

if (!ptr) return;

enqueue(&rear, front, ptr);

for (;;) {

ptr = dequeue(&front, rear);

if (ptr) {

printf("%d", ptr->data);

if (ptr->left_child)

enqueue(&rear, front, ptr->left_child);

if (ptr->right_child)

enqueue(&rear, front, ptr->right_child);

}

else break;

}

}