이론공부/자료구조
자료구조 공부 #17 (트리순회)
한반가
2021. 5. 16. 14:55
2021.05.04 - [이론공부/자료구조] - 자료구조 공부 #16 (트리)
이진 트리 순회
트리의 노드들을 체계적으로 방문 하는것
- 3 가지의 기본적인 순회 방법
- 전위순회 : VLR
- 자손 노드보다 루트 노드를 먼저 방문함
- 중위순회 : LVR
- 왼쪽 자손노드, 루트, 오른쪽 노드순으로 방문함
- 후위순회 : LRV
- 루트 노드보다 자손을 먼저 방문함
- 전위순회 : VLR
전위 순회
- 루트 노드를 방문
- 왼쪽 서브트리 방문
- 오른쪽 서브트리 방문
응용 용도
알고리즘
preorder(x)
if x != null
then print data(x);
preorder(LEFT(x));
preorder(RIGHT(x));
순환 호출(재귀 호출)을 이용함
2021.03.12 - [전체글] - 자료구조 공부#4 (순환, 반복)
자료구조 공부#4 (순환, 반복)
2021.03.09 - [이론공부/자료구조] - 자료구조 공부#3 (알고리즘의 성능 분석) 이전 내용이 포함되어 있다. 이해가 안되는 부분이 있다면 이전 이론 공부 내용을 참고하길 바란다. 이전글과 마찬가지
thesauro.tistory.com
중위 순회
- 왼쪽 서브트리 방문
- 루트 노드 방문
- 오른쪽 서브트리 방문
중위 순회 응용
중위 순회 알고리즘
inorder(x)
if x != null
then inorder(LEFT(x));
print data(x);
inorder(RIGHT(x));
후위 순회
- 왼쪽 서브트리 방문
- 오른쪽 서브트리 방문
- 루트 노드 방문
후위 순회 알고리즘
postorder(x)
if x != null
then postorder(LEFT(x));
postorder(RIGHT(x));
print data(x);
순회 알고리즘 C 구현
더보기
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode* left, * Right;
} TreeNode;
// 15
// 4 20
// 1 16 25
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;
//중위순회
//LVR
void inorder(TreeNode* root) {
if (root) {
inorder(root->left);
printf("[%d]", root->data);
inorder(root->Right);
}
}
//전위 순회
//VLR
void preorder(TreeNode* root) {
if (root) {
printf("[%d]", root->data);
preorder(root->left);
preorder(root->Right);
}
}
// 후위 순회
//LRV
void postorder(TreeNode* root) {
if (root) {
postorder(root->left);
postorder(root->Right);
printf("[%d]", root->data);
}
}
int main() {
printf("중위 순회 =");
inorder(root);
printf("\n");
printf("전위 순회 =");
preorder(root);
printf("\n");
printf("후위 순회 =");
postorder(root);
printf("\n");
return 0;
}
반복, 스택을 이용한 순회 알고리즘
더보기
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode* left, * Right;
} TreeNode;
int top = -1;
TreeNode* stack[100];
#define SIZE 100
void push(TreeNode* p) {
if (top < SIZE - 1)
stack[++top] = p;
}
TreeNode* pop() {
TreeNode* p = NULL;
if (top >= 0)
p = stack[top--];
return p;
}
// 15
// 4 20
// 1 16 25
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;
//중위순회 반복
//LVR
void inorder_iter(TreeNode* root) {
while (true)
{
for (; root; root = root->left)
push(root);
root = pop();
if (!root) break;
printf("[%d]", root->data);
root = root->Right;
}
}
//전위순회 반복
//VLR
void preorder_iter(TreeNode* root) {
while (true)
{
for (; root; root = root->left) {
printf("[%d]", root->data);
push(root);
}
root = pop();
if (!root) break;
root = root->Right;
}
}
//후위 순회 반복
//LRV
void postorder_iter(TreeNode* root) {
while (true)
{
do
{
if (root->data != NULL && root != NULL) {
push(root);
root = root->left;
}
else {
break;
}
} while (root != NULL);
root = pop();
if (!root) break;
if (root->Right != NULL) {
if (root->Right->data == NULL) {
printf("[%d]", root->data);
root->data = NULL;
}
else {
push(root);
root = root->Right;
}
}
else {
printf("[%d]", root->data);
root->data = NULL;
}
}
}
/////////////////////////////////////////////////
//중위순회
//LVR
void inorder(TreeNode* root) {
if (root) {
inorder(root->left);
printf("[%d]", root->data);
inorder(root->Right);
}
}
//전위 순회
//VLR
void preorder(TreeNode* root) {
if (root) {
printf("[%d]", root->data);
preorder(root->left);
preorder(root->Right);
}
}
// 후위 순회
//LRV
void postorder(TreeNode* root) {
if (root) {
postorder(root->left);
postorder(root->Right);
printf("[%d]", root->data);
}
}
/*
printf("중위 순회 =");
inorder(root);
printf("\n");
printf("전위 순회 =");
preorder(root);
printf("\n");
printf("후위 순회 =");
postorder(root);
printf("\n");
*/
int main() {
printf("==============반복==============\n");
printf("중위 순회 =");
inorder(root);
printf("\n");
printf("전위 순회 =");
preorder(root);
printf("\n");
printf("후위 순회 =");
postorder(root);
printf("\n");
printf("==============순환==============\n");
printf("중위 순회 =");
inorder_iter(root);
printf("\n");
printf("전위 순회 =");
preorder_iter(root);
printf("\n");
printf("후위 순회 =");
postorder_iter(root);
printf("\n");
return 0;
}
레벨 순회
- 레벨 순회는 각 노드의 레벨 순으로 검사하는 방법
- 스택이 아닌 큐를 사용하여 연산하는 순회방식
레벨 순회 알고리즘
level_order(root);
initialize queue;
enqueue(queue, root);
while is_empty(queue) = true do
x<-dequeue(queue);
if(x!=null) then
print data(x);
enqueue(queue, left(x));
enqueue(queue, reft(x));
C 로 구현 한 코드
더보기
#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(const 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);
}
}
// 15
// 4 20
// 1 16 25
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;
}
수식 트리
- 산술식을 트리 형태로 표현한것
- 비단말노드(자식이 있는 노드) : 연산자
- 단말노드(자식이 없는 노드) : 피연산자
- 후위순회를 연산에 사용
- 서브트리의 값을 순환 호출로 계산
- 비단말 노드를 방문할 때, 양쪽 서브 트리의 값을 노드에 저장된 연산자를 이용하여 계산
알고리즘
evaluate(exp)
if exp = NULL
then return 0;
else x <-evaluate(exp->left);
y <-evaluate(exp->right);
op <-exp->data;
return (x op y);
구현코드
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode* left, * right;
}TreeNode;
// +
// * +
//1 4 16 25
TreeNode n1 = { 1,NULL, NULL };
TreeNode n2 = { 4,NULL, NULL };
TreeNode n3 = { '*',&n1, &n2 };
TreeNode n4 = { 16,NULL, NULL };
TreeNode n5 = { 25,NULL, NULL };
TreeNode n6 = { '+',&n4, &n5 };
TreeNode n7 = { '+',&n3, &n6 };
TreeNode* exp = &n7;
int evaluate(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL)
return root->data;
else {
int op1 = evaluate(root->left);
int op2 = evaluate(root->right);
printf("%d %c %d을 계산 합니다\n", op1, root->data, op2);
switch (root->data)
{
case '+': return op1 + op2;
case '-': return op1 - op2;
case '*': return op1 * op2;
case '/': return op1 / op2;
default:
break;
}
}
return 0;
}
int main(void) {
printf("수식의 값은 %d 입니다.\n", evaluate(exp));
return 0;
}그 외에도 트리순회는 디렉토리들의 용량 계산을 하는데도 많이 사용한다.
후위순회, 중위순회, 전위순회 전부 어느 방식인지 일단 숙지해두자.