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

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

2021. 12. 13. 14:48ㆍMajor`/자료구조

반복적 순회 (중위 순회)
- 알고리즘
- ※ Example
레벨 순회
- 알고리즘
- ※ Example

반복적 순회 (중위 순회)

- 스택을 이용해서 구현

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

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

알고리즘

root에서부터 root->left로 진행하면서 stack에 push ( root = root->left를 통해서 반복) -- (1)
root->left가 NULL이 되면 stack에서 하나씩 pop
pop한 노드를 방문해서 해당 노드에서 node->right로 이동
node->right가 NULL이면, 그냥 stack에서 pop
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;
}

레벨 순회

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

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

- 원형큐를 사용하여 구현

알고리즘

Tree의 root를 먼저 enqueue -- (1)
dequeue를 통해 나온 node->data print -- (2)
해당 node의 node->left != NULL이면 node->left를 enqueue -- (3)
그리고 해당 node의 node->right != NULL이면, node->right를 enqueue -- (4)
해당 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;
}

저작자표시 변경금지

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

Coding -> 블로그 이전

Coding

반복적 순회 (중위 순회)

알고리즘

※ Example

레벨 순회

알고리즘

※ Example

관련글

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역

	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는 마지막으로 순회
	}
	}

	#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;
	}

	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
	}
	}

	#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;
	}