본문으로 바로가기

자료구조 공부 #17 (트리순회)

category 이론공부/자료구조 2021. 5. 16. 14:55

2021.05.04 - [이론공부/자료구조] - 자료구조 공부 #16 (트리)


이진 트리 순회

트리의 노드들을 체계적으로 방문 하는것

순회 설명 이미지

  • 3 가지의 기본적인 순회 방법
    • 전위순회 : VLR
      • 자손 노드보다 루트 노드를 먼저 방문함
    • 중위순회 : LVR
      • 왼쪽 자손노드, 루트, 오른쪽 노드순으로 방문함
    • 후위순회 : LRV
      • 루트 노드보다 자손을 먼저 방문함

 

전위 순회

  1. 루트 노드를 방문
  2. 왼쪽 서브트리 방문
  3. 오른쪽 서브트리 방문

방문 순서 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

 

중위 순회

  1. 왼쪽 서브트리 방문
  2. 루트 노드 방문
  3. 오른쪽 서브트리 방문

 

중위 순회 : LVR

중위 순회 응용

 

수식 트리 순서는 중위순회가 어울리다

 

 

중위 순회 알고리즘

inorder(x)
if x != null
 then	inorder(LEFT(x));
        print data(x);   
        inorder(RIGHT(x));

 

 

후위 순회

  1. 왼쪽 서브트리 방문
  2. 오른쪽 서브트리 방문
  3. 루트 노드 방문

 

후위 순회 : LRV

 

 

후위 순회 알고리즘

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

 

수식 트리

  • 산술식을 트리 형태로 표현한것
    • 비단말노드(자식이 있는 노드) : 연산자
    • 단말노드(자식이 없는 노드) : 피연산자

수식 트리 예시

  • 후위순회를 연산에 사용
  • 서브트리의 값을 순환 호출로 계산
  • 비단말 노드를 방문할 때, 양쪽 서브 트리의 값을 노드에 저장된 연산자를 이용하여 계산

32*32*+

알고리즘

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;
}
그 외에도 트리순회는 디렉토리들의 용량 계산을 하는데도 많이 사용한다.

 


후위순회, 중위순회, 전위순회 전부 어느 방식인지 일단 숙지해두자.