문과생이 이해한 트리(순회-레벨 순회)

출처 : <c언어로 쉽게 풀어쓴 자료구조> + 학교 수업

 

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

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

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

void init(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 == q->front;
}

void enqueue(QueueType* q, TreeNode* item) {  //int item
	if (is_full(q)) {
		fprintf(stderr, "큐가 포화 상태입니다.");
		return;
	}
	q->rear = (q->rear + 1) % MAX;
	q->data[q->rear] = item;
}

TreeNode* dequeue(QueueType* q) {
	if (is_empty(q)) {
		fprintf(stderr, "큐가 공백상태입니다.");
		return;
	}
	q->front = (q->front + 1) % MAX;
	return q->data[q->front];
}

void level_order(TreeNode* ptr) {
	QueueType q;
	init(&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() {
	printf("레벨 순회>>");
	level_order(root);
	printf("\n");

	return 0;
}

 

 레벨 순회는 트리의 층마다 출력하는 순회 방법이다.  요런 식으로!! 이건 원형큐를 사용한다.

 

 

 

 

 

#level_order()

 

 

 init()까지 하면 요런 상태.  enqueue는 원형 큐 게시글 참고하면 좋을 것 같당. (신기한 건 enqueue할 때 item을 구조체 포인터 형식으로 받지 않고 int형으로 받아도 실행 가능한 거. ptr은 구조체 변수라서 data 뿐만 아니라 *left, *right 포인터도 2개가 있는데 귀신같이 data 필드를 참고해서 enqueue 하는 거..)

 

 

 현재 front와 rear가 같지 않으므로 q는 비어있지 않다. 

 

 

 

여기서 ptr이 가리키는 data를 출력한다. (이거 진짜 대박인 듯.. 큐에 TreeNode라는 구조체 변수의 주소값을 넣어놓고 그걸 이용해서 모든 필드를 사용하는 코드... 미쳐버렸다.)

 

 

 

 아 참고로 if문 조건식에 주소값이 들어가게 되면 NULL이 아닐 경우 true를 리턴한다고 함. 

 

 

 

 아무튼 이걸 계속 반복한다보면 결구 레벨 순회를 할 수 있게 된다.