[자료구조] 이진트리의 순회

1. 이진 트리의 순회

• 순회(Traversal) : 트리의 노드들을 체계적으로 방문하는 것

 

1) 기본적인 순회 방법

(1) 전위 순회(Preorder Traversal) : VLR

 - 자손 노드보다 루트 노드를 먼저 방문

 

(2) 중위 순회(Inorder Traversal) : LVR

 - 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문

 

 

(3) 후위 순회(Postorder Traversal) : LRV

 - 루트 노드보다 자손을 먼저 방문

 

	root (V)
↙		↘
left (L)		right (R)

 

2. 전위 순회(Preorder Traversal)

1) 수행 방법

1. 현재 노드 n을 방문하여 처리 : V
2. 현재 노드 n의 왼쪽 서브 트리로 이동 : L
3. 현재 노드 n의 오른쪽 서브 트리로 이동 : R

 

2) 알고리즘

 

preorder(T)
	if(T != NULL) then {
		visti T.data;
		preorder(T.left);
		preorder(T.right);
	}
end preorder()


// 위 알고리즘을 C언어로 바꿈
void PreOrder(Node *R){
	printf("%d ", R -> data);
	if(R -> left) PreOrder(R -> left);
	if(R -> right) PreOrder(R -> right);
}

 

3) 전위 순회(VLR)의 순서

• 루트, 왼쪽 자손, 오른쪽 자손 순으로 방문
• 10, 20, 40, 50, 30, 60, 70

 

			10
		↙		↘
	20				30
↙		↘		↙		↘
40		50		60		70

 

4) 수식 이진 트리에 대한 전위 순회

• 수식을 이진 트리로 구성한 수식 이진 트리를 전위 순회하면 수식에 대한 전위 표기 식을 구할 수 있다.

 

(1) 순회 경로

• +*AB/CD

 

			+
		↙		↘
	*				/
↙		↘		↙		↘
A		B		C		D

 

 

5) C언어 실습

 

#include <stdio.h>
#include <stdlib.h>
#define BOOL int	// typedef와 같음 int형을 BOOL형으로 바꿈
#define TRUE 1
#define FALSE 0

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

NODE *Root;

void InitTree(int data) {	// Tree 초기화
	Root = (NODE *)malloc(sizeof(NODE));
	Root -> data = data;
}

NODE *AddChild(NODE *Parent, int data, BOOL bLeft) {	// 노드 확장
	NODE *New;
	New = (NODE *)malloc(sizeof(NODE));
	New -> data = data;
	New -> left = NULL;
	New -> right = NULL;

	if (bLeft)
		Parent -> left = New;
	else
		Parent -> right = New;

	return New;
}

void PreOrder(NODE *R) {	// 노드 방문, 출력
	printf(" %d ", R -> data);	// 출력이 제일 앞 즉, 루트를 먼저 방문
	if (R -> left) PreOrder(R -> left);
	if (R -> right) PreOrder(R -> right);
}

void FreeTree(NODE *R) {	// 동적할당 free
	if (R->left) FreeTree(R->left);
	if (R->right) FreeTree(R->right);
	free(R);
}

void main() {
	NODE *Left, *Right;

	InitTree(10);

	Left = AddChild(Root, 20, TRUE);
	Right = AddChild(Root, 30, FALSE);
	AddChild(Left, 40, TRUE);
	AddChild(Left, 50, FALSE);
	AddChild(Right, 60, TRUE);
	puts(" --- PreOrder ---"); puts("");
	PreOrder(Root);	puts("");
	FreeTree(Root);
}

 

 

전위 순회 실행

 

3. 중위 순회(Inorder Traversal)

1) 수행 방법

1. 현재 노드 n의 왼쪽 서브 트리로 이동 : L
2. 현재 노드 n을 방문하여 처리 : V
3. 현재 노드 n의 오른쪽 서브 트리로 이동 : R

 

2) 중위 순회 알고리즘

 

inorder(T)
	if(T != NULL) then {
		inorder(T.left);
		visti T.data;
		inorder(T.right);
	}
end inorder()


// 위 알고리즘을 C언어로 바꿈
void InOrder(Node *R){
	if(R -> left) InOrder(R -> left);
	printf("%d ", R -> data);
	if(R -> right) InOrder(R -> right);
}

 

3) 중위 순회(LVR)의 순서

• 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문
• 40, 20, 50, 10, 60, 30, 70

 

			10
		↙		↘
	20				30
↙		↘		↙		↘
40		50		60		70

 

4) 수식 이진 트리에 대한 중위 순회

• 수식 이진 트리를 중위 순회 하면 수식에 대한 중위 표기 식을 구할 수 있다.

 

(1) 순회 경로

• A*B+C/D

 

			+
		↙		↘
	*				/
↙		↘		↙		↘
A		B		C		D

 

5) C언어 실습

 

#include <stdio.h>
#include <stdlib.h>
#define BOOL int	// typedef와 같음 int형을 BOOL형으로 바꿈
#define TRUE 1
#define FALSE 0

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

NODE *Root;

void InitTree(int data) {	// Tree 초기화
	Root = (NODE *)malloc(sizeof(NODE));
	Root -> data = data;
}

NODE *AddChild(NODE *Parent, int data, BOOL bLeft) {	// 노드 확장
	NODE *New;
	New = (NODE *)malloc(sizeof(NODE));
	New -> data = data;
	New -> left = NULL;
	New -> right = NULL;

	if (bLeft)
		Parent -> left = New;
	else
		Parent -> right = New;

	return New;
}

void InOrder(NODE *R) {		// 노드 방문, 출력
	if (R -> left) InOrder(R -> left);
	printf(" %d ", R -> data);	// 출력이 중간 즉, 루트를 중간에 방문
	if (R -> right) InOrder(R -> right);
}

void FreeTree(NODE *R) {	// 동적할당 free
	if (R->left) FreeTree(R->left);
	if (R->right) FreeTree(R->right);
	free(R);
}

void main() {
	NODE *Left, *Right;

	InitTree(10);

	Left = AddChild(Root, 20, TRUE);
	Right = AddChild(Root, 30, FALSE);
	AddChild(Left, 40, TRUE);
	AddChild(Left, 50, FALSE);
	AddChild(Right, 60, TRUE);
	AddChild(Right, 70, FALSE);
	puts(" --- InOrder ---"); puts("");
	InOrder(Root);	puts("");
	FreeTree(Root);
}

 

중위 순회 실행

 

4. 후위 순회(Postorder Traversal)

1) 수행 방법

1. 현재 노드 n의 왼쪽 서브 트리로 이동 : L
2. 현재 노드 n의 오른쪽 서브 트리로 이동 : R
3. 현재 노드 n을 방문하여 처리 : V

 

2) 후위 순회 알고리즘

 

postorder(T)
	if(T != NULL) then {
		postorder(T.left);
		postorder(T.right);
		visti T.data;
	}
end postorder()


// 위 알고리즘을 C언어로 바꿈
void PostOrder(Node *R){
	if(R -> left) PostOrder(R -> left);
	if(R -> right) PostOrder(R -> right);
	printf("%d ", R -> data);
}

 

3) 후위 순회(LRV)의 순서

• 왼쪽 자손, 오른쪽 자손, 루트 순으로 방문
• 40, 50, 20, 60, 70, 30, 10

 

			10
		↙		↘
	20				30
↙		↘		↙		↘
40		50		60		70

 

4) 수식 이진 트리에 대한 후위 순회

• 수식 이진 트리를 후위 순회 하면 수식에 대한 후위 표기 식을 구할 수 있다.

 

(1) 순회 경로

• AB*CD/+

 

			+
		↙		↘
	*				/
↙		↘		↙		↘
A		B		C		D

 

5) C언어 실습

 

#include <stdio.h>
#include <stdlib.h>
#define BOOL int	// typedef와 같음 int형을 BOOL형으로 바꿈
#define TRUE 1
#define FALSE 0

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

NODE *Root;

void InitTree(int data) {	// Tree 초기화
	Root = (NODE *)malloc(sizeof(NODE));
	Root -> data = data;
}

NODE *AddChild(NODE *Parent, int data, BOOL bLeft) {	// 노드 확장
	NODE *New;
	New = (NODE *)malloc(sizeof(NODE));
	New -> data = data;
	New -> left = NULL;
	New -> right = NULL;

	if (bLeft)
		Parent -> left = New;
	else
		Parent -> right = New;

	return New;
}

void PostOrder(NODE *R) {	// 노드 방문, 출력
	if (R -> left) PostOrder(R -> left);
	if (R -> right) PostOrder(R -> right);
	printf(" %d ", R -> data);	// 출력이 마지막 즉, 루트를 마지막에 방문
}

void FreeTree(NODE *R) {	// 동적할당 free
	if (R->left) FreeTree(R->left);
	if (R->right) FreeTree(R->right);
	free(R);
}

void main() {
	NODE *Left, *Right;

	InitTree(10);

	Left = AddChild(Root, 20, TRUE);
	Right = AddChild(Root, 30, FALSE);
	AddChild(Left, 40, TRUE);
	AddChild(Left, 50, FALSE);
	AddChild(Right, 60, TRUE);
	AddChild(Right, 70, FALSE);
	puts(" --- PostOrder ---"); puts("");
	PostOrder(Root);	puts("");
	FreeTree(Root);
}

 

후위 순회 실행