[자료구조] 이진 트리의 순회 - 레벨 순회

이진트리의 레벨 순회

레벨 순회는 각 노드를 레벨 순으로 검사하는 순회 방법입니다. 중위, 후위, 전위 순회가 스택을 사용했던 것에 비해 레벨 순회는 선입선출 기반의 큐를 사용하는 순회 법입니다.

 

위의 이진트리를 레벨 순회해보겠습니다. "만나는 노드를 꺼내서 출력하고 서브트리를 왼쪽부터 큐에 넣는다" 만 기억하면 됩니다. 먼저 루트를 방문하여 +를 큐에 넣습니다.

큐 : | + |

+를 꺼내서 출력하고 서브트리인 *와 /를 큐에 넣습니다.

큐 : | * | / |

*를 꺼내서 출력하고 서브트리인 A와 B를 큐에 넣습니다.

큐 : | / | A | B |

/를 꺼내서 출력하고 서브트리인 C와 D를 큐에 넣습니다.

큐 : | A | B | C | D |

A를 꺼내서 출력하고 큐에 넣을 서브트리는 없습니다. D까지 출력하고 종료합니다.

출력 결과 : +*/ABCD

 

 

알고리즘

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

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

// 원형 큐 사용
#define MAX_QUEUE_SIZE 100
typedef TreeNode* element;
typedef struct { 		// 큐 타입
	element  data[MAX_QUEUE_SIZE];
	int  front, rear;
} QueueType;

void error(char* message) {			// 오류 함수
	fprintf(stderr, "%s\n", message);
	exit(1);
}
void init_queue(QueueType* q) {		// 큐 초기화 함수
	q->front = q->rear = 0;
}
int is_empty(QueueType* q) {			// 공백 상태 검출 함수
	return (q->front == q->rear);
}
int is_full(QueueType* q) {			// 포화 상태 검출 함수
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
void enqueue(QueueType* q, element item) {	// 삽입 함수
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}
element dequeue(QueueType* q) {		// 삭제 함수

	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}
void level_order(TreeNode* ptr) {
	QueueType q;
	init_queue(&q);	 // 큐 초기화
	if (ptr == NULL) return;
	enqueue(&q, ptr);
	while (!is_empty(&q)) {
		ptr = dequeue(&q);
		printf(" [%d] ", ptr->data);
		if (ptr->left)	enqueue(&q, ptr->left);
		if (ptr->right)	enqueue(&q, ptr->right);
	}
}

TreeNode n1 = { 1,  NULL, NULL };	
TreeNode n2 = { 4,  &n1,  NULL };	
TreeNode n3 = { 16, NULL, NULL };	
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3,  &n4 };
TreeNode n6 = { 15, &n2,  &n5 };
TreeNode* root = &n6;

int main(void) {
	printf("레벨 순회=");
	level_order(root);
	printf("\n");
	return 0;
}
/*
레벨 순회= [15]  [4]  [20]  [1]  [16]  [25]
*/

함수 level_order() 는 다음과 같은 이진 트리의 레벨 순회를 수행합니다.

 

            15                                 n6
    4             20                  n2            n5         
 1            16    25           n1            n3    n4    

 

매개변수가 n6인 경우 가장 먼저 15를 출력하고 그 서브트리인 n2와 n5를 큐에 넣습니다. 4를 출력하고 n1을 큐에 넣습니다. 20을 출력하고 n3와 n4를 큐에 넣습니다. 1을 출력합니다. 16을 출력합니다. 25를 출력합니다.