트리 - 레벨 순회 알고리즘

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다.

 

이전 글: 트리 - 반복적 순회(스택으로 이해하기)

 

레벨 순회 level order

각 노드를 레벨 순으로 검사하는 순회 방법이다.

루트 노드의 레벨이 1이고, 아래로 내려갈수록 레벨은 증가한다.

동일한 레벨의 경우에는 좌->우로 방문한다.

 

레벨 순회에 적합한 자료구조는 큐 Queue 이다.

큐를 이용해서 레벨 순회를 진행하면 다음과 같다.

트리의 루트 노드를 우선 삽입한다. 그 다음부터는 큐가 공백 상태가 될 때까지 아래의 과정을 반복한다.
큐에서 dequeue를 한 다음, 삭제된 노드의 왼쪽 서브트리의 루트노드와 오른쪽 서브트리의 루트노드를 순서대로 큐에 enqueue한다. (NULL이 아니라는 가정 하에)

알고리즘은 아래와 같다. 

// Pseudo Code
level_order(root):
	if(root == NULL) return
	enqueue(queue, root)
	while (not queue.isEmpty)
		x <- dequeue(queue)
		print x<-data
		if( x->left != NULL) then
			enqueue(queue, x->left)
		if( x->right != NULL) then
			enqueue(queue, x->right)

이를 이용해 레벨 순회 프로그램을 구현해보면 다음과 같다.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int data;
	struct TreeNode* left, * right;
} TreeNode;

//-------------원형 큐 코드 시작-------------
#define MAX_QUEUE_SIZE 20

typedef TreeNode* element;
typedef struct {
	element data[MAX_QUEUE_SIZE];
	int front, rear;
} QueueType;

// Error Check
void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}
// init queue
void init_queue(QueueType* q) {
	q->front = q->rear = 0;
}
// check empty
int is_empty(QueueType* q) {
	return (q->front == q->rear);
}
// check full
int is_full(QueueType* q) {
	return (q->front == ((q->rear + 1) % MAX_QUEUE_SIZE));
}
// enqueue
void enqueue(QueueType* q, element item) {
	if (is_full(q)) {
		error("queue is full\n");
	}
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}
// dequeue
element dequeue(QueueType* q) {
	if (is_empty(q)) {
		error("queue is empty\n");
	}
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}
// level traversal
void level_order(TreeNode *node) {
	QueueType q;
	init_queue(&q);
	if (node == NULL) return;
	enqueue(&q, node);
	while (!is_empty(&q)) {
		node = dequeue(&q);
		printf("%c -> ", node->data);
		if (node->left)
			enqueue(&q, node->left);
		if (node->right)
			enqueue(&q, node->right);
	}
}
TreeNode n0 = { 'D', NULL, NULL };
TreeNode n1 = { 'E', NULL, NULL };
TreeNode n2 = { 'B', &n0, &n1 };
TreeNode n3 = { 'F', NULL, NULL };
TreeNode n4 = { 'C', &n3, NULL };
TreeNode n5 = { 'A', &n2, &n4 };
TreeNode* root = &n5;

int main()
{
	printf("레벨 순회\n");
	level_order(root);
	printf("\n");
	return  0;
}

결과