[Data Structure] 이진 트리 반복적 순회/레벨 순회

반복적 순회 (중위 순회)

- 스택을 이용해서 구현

• 스택에 자식 노드들을 push하고 pop하면서 순회

- 인공지능에서 지능적 탐색을 할 때 사용

 

 

알고리즘

1. root에서부터 root->left로 진행하면서 stack에 push ( root = root->left를 통해서 반복) -- (1)
2. root->left가 NULL이 되면 stack에서 하나씩 pop
3. pop한 노드를 방문해서 해당 노드에서 node->right로 이동
4. node->right가 NULL이면, 그냥 stack에서 pop
5. node->right가 NULL이 아니면 node->right로 이동해서 (1) 진행

- stack이 공백이 되면 순회 종료

void inorder_iter(treenode* root) {
	// LVR 순으로 순회
	while (1) {
		for (; root; root = root->left) // root부터 최종 root->left까지 스택에 push
			push(root);
		root = pop(); // 스택의 top에는 최종 root->left의 data가 존재하니까 pop해서 순회
		if (!root) break; 
		printf("[%d] ", root->data); // pop한 root->data print
		root = root->right; // LVR 순이니까 root->right는 마지막으로 순회
	}
}

 

 

※ Example

#include <stdio.h>
#include <stdlib.h>
// 이진트리 반복적 순회(중위 순회)

typedef int element;
typedef struct treenode {
	element data;
	struct treenode* left;
	struct treenode* right;
}treenode;

#define MAX_STACK_SIZE 1000
int top = -1;
treenode* stack[MAX_STACK_SIZE]; // 노드들 저장하는 스택 정의

treenode n1 = { 8, NULL, NULL };
treenode n2 = { 39, NULL, NULL };
treenode n3 = { 85, NULL, NULL };
treenode n4 = { 2, NULL, NULL };
treenode n5 = { 15, &n1, &n2 };
treenode n6 = { 21, &n3, &n4 };
treenode n7 = { 30, &n5, &n6 };
treenode* root = &n7; // 트리의 루트 노드(n7)를 가리키는 root 포인터

//           30
//    15          21
// 8     39    85    2

// 중위순회 : 8 15 39 30 85 21 2

void push(treenode* p) {
	if (top < MAX_STACK_SIZE - 1)
		stack[++top] = p;
}

treenode* pop() {
	treenode* p = NULL;
	if (top >= 0)
		p = stack[top--];
	return p;
}

void inorder_iter(treenode* root) {
	// LVR 순으로 순회
	while (1) {
		for (; root; root = root->left) // root부터 최종 root->left까지 스택에 push
			push(root);
		root = pop(); // 스택의 top에는 최종 root->left의 data가 존재하니까 pop해서 순회
		if (!root) break; 
		printf("[%d] ", root->data); // pop한 root->data print
		root = root->right; // LVR 순이니까 root->right는 마지막으로 순회
	}
}

int main(void) {
	printf("반복적 순회 (중위 순회) : ");
	inorder_iter(root);
	printf("\n");

	return 0;
}

---

레벨 순회

- 각 노드들을 레벨 순으로 검사하는 순회 방법

- 동일 레벨의 경우 좌 → 우로 방문

- 원형큐를 사용하여 구현

 

알고리즘

1. Tree의 root를 먼저 enqueue -- (1)
2. dequeue를 통해 나온 node->data print -- (2)
3. 해당 node의 node->left != NULL이면 node->left를 enqueue -- (3)
4. 그리고 해당 node의 node->right != NULL이면, node->right를 enqueue -- (4)
5. 해당 node의 left, right가 모두 NULL이면 (2) 과정으로 

- (2) ~ (4) 과정을 queue가 공백이 될 때 까지 계속 반복

void level_trv(treenode* root) {
	queue q;
	init(&q);
	if (root == NULL) return;
	enqueue(&q, root); // 루트 노드를 enqueue하고, 순회 시작
	while (!is_empty(&q)) {
		root = dequeue(&q); // dequeue를 통해서 루트 노드 select
		printf("[%d] ", root->data); // 루트 노드의 data print
		if (root->left != NULL) // 루트 노드의 left가 NULL이 아니면
			enqueue(&q, root->left); // 루트 노드의 left를 enqueue
		if (root->right != NULL) // 루트 노드의 right가 NULL이 아니면
			enqueue(&q, root->right); // 루트 노드의 right를 enqueue
	}
}

 

 

※ Example

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

#define MAX_QUEUE_SIZE 100

typedef struct treenode {
	int data;
	struct treenode* left;
	struct treenode* right;
}treenode;

treenode n1 = { 8, NULL, NULL };
treenode n2 = { 39, NULL, NULL };
treenode n3 = { 85, NULL, NULL };
treenode n4 = { 2, NULL, NULL };
treenode n5 = { 15, &n1, &n2 };
treenode n6 = { 21, &n3, &n4 };
treenode n7 = { 30, &n5, &n6 };
treenode* root = &n7; // 트리의 루트 노드(n7)를 가리키는 root 포인터

//           30
//    15          21
// 8     39    85    2

//  레벨 순회 : 30 15 21 8 39 85 2

// 원형큐로 구현
typedef treenode* element;
typedef struct queue {
	int front, rear;
	element queue[MAX_QUEUE_SIZE];
}queue;

void init(queue* q) {
	q->front = q->rear = 0;
}

int is_empty(queue* q) {
	return q->front == q->rear;
}

int is_full(queue* q) {
	return q->front == (q->rear + 1) % MAX_QUEUE_SIZE;
}

void enqueue(queue* q, element item) {
	if (is_full(q))
		return;
	else {
		q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
		q->queue[q->rear] = item;
	}
}

element dequeue(queue*q) {
	if (is_empty(q))
		return;
	else {
		q->front = (q->front + 1) % MAX_QUEUE_SIZE;
		return q->queue[q->front];
	}
}

void level_trv(treenode* root) {
	queue q;
	init(&q);
	if (root == NULL) return;
	enqueue(&q, root); // 루트 노드를 enqueue하고, 순회 시작
	while (!is_empty(&q)) {
		root = dequeue(&q); // dequeue를 통해서 루트 노드 select
		printf("[%d] ", root->data); // 루트 노드의 data print
		if (root->left != NULL) // 루트 노드의 left가 NULL이 아니면
			enqueue(&q, root->left); // 루트 노드의 left를 enqueue
		if (root->right != NULL) // 루트 노드의 right가 NULL이 아니면
			enqueue(&q, root->right); // 루트 노드의 right를 enqueue
	}
}

int main(void) {
	printf("레벨 순회 : ");
	level_trv(root);
	printf("\n");

	return 0;
}