이진 트리의 레벨 순회

레벨 순회(level order)

- 각 노드를 레벨 순으로 검사

- 루트 노드의 레벨은 1, 아래로 내려갈수록 레벨 증가

- 큐 사용

 

- 큐에 노드가 하나라도 있으면 계속 반복

- 큐에 있는 노드를 꺼내어 방문한 다음, 그 노드의 자식 노드를 큐에 삽입하는 과정이 한 번의 반복

- 이러한 반복을 큐에 노드가 존재하지 않을 때까지 계속

1. 루트 노드인 +가 큐에 입력된 상태에서 순회 시작

2. 큐에서 하나를 삭제하면 +가 pop

3. 노드 +를 방문한 다음 노드 +의 자식 노드인 *와 /를 큐에 삽입

4. 다시 반복의 처음으로 복귀

 

전체 코드

#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 euqueue(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;

	euqueue(&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;
}