Level Order Traversal이란?
이진트리 순회 방법으로는 앞서 언급한 전위, 중위, 후위 순회 뿐만 아니라,
트리의 레벨 순서대로 순회하는 Level order traversal 이 있습니다.
말 그대로 트리의 노드 레벨 순으로 순회하는 것입니다.
기본 구조는 다음과 같습니다.
- 1) 루트 노드를 방문한다.
2) 루트 노드의 Left Child 를 방문한다.
- 3) 루트 노드의 Right Child를 방문한다.
[그림 1] 이진 트리 예제
위의 이진 트리를 Level order로 순회하면 어떻게 될까요?
가장 최상위 루트 노드 즉 레벨 1부터 순회합니다.
따라서, A-B-C-D-E-F-G 순서로 순회하게 됩니다.
[그림 2] 이진 트리 예제
위 그림도 마찬가지로 레벨 순으로 순회하면 됩니다. A-B-C-D-E-F-G 가 됩니다.
앞에서 전위/중위/후위 순회는 재귀 함수로 구현했습니다. 즉, 메모리상 스택에 쌓이는 구조입니다.
(자료구조 Stack을 말하는 것이 아니라, 메모리 상 함수 호출이 계속 쌓이는 Stack을 말합니다.)
하지만 이제 알아볼 Level Order Traversal 는 큐로 구현해 볼 것입니다.
큐는 기본적으로 맨 앞과 맨 뒤를 가리키는 front와 rear, 그리고 큐에 데이터를 삽입하는 함수와, 데이터를 삭제하는 함수가 정의됩니다.
Level Order Traversal의 방법을 큐로 구현하는 것이지, 트리의 자료구조는 기존에 연결리스트로 구현한 소스를 토대로 하면 됩니다.
(1) 기본적인 알고리즘
[그림 3] 위의 이진 트리를 Level Order Traversal 할 것입니다.
그림에서 [1]~[9] 까지가 큐를 이용한 Level Order 순회 방법입니다.
루트 노드 넣기 -> dequeue로 반환해 출력 -> 반환한 노드의 자식 노드들 큐에 차례대로 넣기(왼쪽, 오른쪽 순) -> dequeue로 다음 노드 반환해 출력 -> 반환한 노드의 자식 노드를 큐에 넣기 -> …. 이 과정의 반복입니다.
이것만 보시면 소스로 구현하는 데는 어려움이 없으실 겁니다.
(2) 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
typedef struct _node{
int data;
struct _node * leftChild;
struct _node * rightChild;
}node;
typedef node* treePointer;
treePointer Create(int data) {
treePointer nd;
nd = (treePointer)malloc(sizeof(node));
nd->leftChild = NULL;
nd->rightChild = NULL;
nd->data = data;
return nd;
}
int front = 0; int rear = 0; // 전역변수 선언
treePointer Queue[MAX_QUEUE_SIZE];
void Enqueue(treePointer ptr) {
Queue[++rear] = ptr;
}
treePointer Dequeue() {
return Queue[++front];
}
void levelOrder(treePointer ptr) {
if (!ptr)
return;
Enqueue(ptr);
while (1) {
ptr = Dequeue();
if (ptr)
{
printf("%d ", ptr->data);
if (ptr->leftChild)
Enqueue(ptr->leftChild);
if (ptr->rightChild)
Enqueue(ptr->rightChild);
}
else
break;
}
}
int main(void)
{
/* 예시를 위한 트리 생성 */
treePointer ONE = Create(1);
treePointer TWO = Create(2);
treePointer THREE = Create(3);
treePointer FOUR = Create(4);
treePointer FIVE = Create(5);
ONE->leftChild = TWO;
ONE->rightChild = THREE;
TWO->leftChild = FOUR;
TWO->rightChild = FIVE;
printf("[구현 결과] level order : ");
levelOrder(ONE);
return 0;
}