본문 바로가기
프로그래밍/자료구조

Chapter08 트리(Tree)

by Ohdumak 2018. 1. 15.
728x90

2018/01/10 - [프로그래밍/자료구조] - Chapter07 큐(Queue)



08-1 트리의 개요

스택, 큐와 같은 선형 자료구조들과 달리 트리는 비선형 자료구조이다.


트리(Tree)의 접근

"트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다."

트리는 데이터의 저장과 삭제가 아닌 '표현'에 초점일 맞춰져 있다.

"트리의 구조로 이뤄진 무엇인가를 표현하기에 적절히 정의되어 있는가?"


트리 관련 용어의 소개

- 노드: node

트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소

- 간선: edge

노드와 노드를 연결하는 연결선

- 루트 노드: root node

트리 구조에서 최상위에 존재하는 A와 같은 노드

- 단말 노드: terminal node

아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드

- 내부 노드: internal node


참고로 '단말 노드'는 나무의 구조상 잎에 해당한다 하여 '잎사귀 노드(leaf node)'라고도 불리며, '내부 노드'는 단말 노드가 아니라 하여 '비단말 노드(nonterminal node)'라고도 불린다. 그리고 노드간에는 부모(parent), 자식(child), 형제(sibling)의 관계가 성립이 된다. 조금 더 나아가서 조상(Ancestor), 후손(Descendant)의 관계도 있다.


이진 트리(Binary Tree)와 서브 트리(Sub Tree)

이진트리

- 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

- 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다.

"노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(empty set) 노드가 존재하는 것으로 간주한다! 물론 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정한다!"


포화 이진 트리(Full Binary Tree)와 완전 이진 트리(Complete Binary Tree)

트리에서는 각 층별로 숫자를 매겨서 이를 트리의 '레벨'이라 하고, 트리의 최고 레벨을 가리켜 '높이'라 한다.

모든 레벨이 꽉 찬 이진트리를 가리켜 '포화 이진 트리'라 한다.

포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 빈 틈 없이 노드가 채워진 이진 트리를 '완전 이진 트리'라 한다.



08-2 이진 트리의 구현

이진 트리의 재귀적인 특성 때문에 이진 트리와 관련된 일부 연산은 재귀호출의 형태를 띤다.


이진 트리의 구현 방법: 배열 기반 or 연결 리스트 기반

배열은 분명 연결 리스트에 비해서 탐색이 매우 용이하고 또 빠르다. 연결 리스트를 기반으로 트리를 구현할 경우 연결 리스트의 구성 형태가 트리와 일치한다.


헤더파일에 정의된 구조체의 이해

이진 트리 자료구조의 ADT

- BTreeNode *MakeBTreeNode(void);

이진 트리 노드를 생성하여 그 주소 값을 반환한다.

- BTData GetData(BTreeNode *bt);

노드에 저장된 데이터를 반환한다.

- void SetData(BTreeNode *bt, BTData data);

노드에 데이터를 저장한다. data로 전달된 값을 저장한다.

- BTreeNode *GetLeftSubTree(BTreeNode *bt);

왼쪽 서브 트리의 주소 값을 반환한다.

- BTreeNode *GetRightSubTree(BTreeNode *bt);

오른쪽 서브 트리의 주소값을 반환한다.

- void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub);

왼쪽 서브 트리를 연결한다.

- void MakeRightSubTree(BTreeNode *main, BTreeNode *sub);

오른쪽 서브 트리를 연결한다.


이진 트리의 구현

BinaryTree.h

/*---- INCLUDES      --------------------------------------------------------*/

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
typedef int BTData;

typedef struct _bTreeNode {
	BTData data;
	struct _bTreeNode *left;
	struct _bTreeNode *right;
} BTreeNode;


BTreeNode *MakeBTreeNode(void);
BTData GetData(BTreeNode *bt);
void SetData(BTreeNode *bt, BTData data);

BTreeNode *GetLeftSubTree(BTreeNode *bt);
BTreeNode *GetRightSubTree(BTreeNode *bt);

void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub);
void MakeRightSubTree(BTreeNode *main, BTreeNode *sub);

BinaryTree.c

/*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/

BTreeNode *MakeBTreeNode(void) {
	BTreeNode *newTree = (BTreeNode *)malloc(sizeof(BTreeNode));
	newTree->data = 0;
	newTree->left = NULL;
	newTree->right = NULL;
	return newTree;
}
BTData GetData(BTreeNode *bt) {
	return bt->data;
}
void SetData(BTreeNode *bt, BTData data) {
	bt->data = data;
}

BTreeNode *GetLeftSubTree(BTreeNode *bt) {
	return bt->left;
}
BTreeNode *GetRightSubTree(BTreeNode *bt) {
	return bt->right;
}

void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub) {
	if (main->left != NULL) {
		free(main->left);
	}
	main->left = sub;
}
void MakeRightSubTree(BTreeNode *main, BTreeNode *sub) {
	if (main->right != NULL) {
		free(main->right);
	}
	main->right = sub;
}

BinaryTreeMain.c

/*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>
#include "BinaryTree.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
int main(void) {
	BTreeNode *bt1 = MakeBTreeNode();			// 노드 bt1 생성
	BTreeNode *bt2 = MakeBTreeNode();			// 노드 bt2 생성
	BTreeNode *bt3 = MakeBTreeNode();			// 노드 bt3 생성
	BTreeNode *bt4 = MakeBTreeNode();			// 노드 bt4 생성

	SetData(bt1, 1);			// bt1에 1 저장
	SetData(bt2, 2);			// bt2에 2 저장
	SetData(bt3, 3);			// bt3에 3 저장
	SetData(bt4, 4);			// bt4에 4 저장

	MakeLeftSubTree(bt1, bt2);				// bt2를 bt1의 왼쪽 자식 노드로
	MakeRightSubTree(bt1, bt3);			// bt3를 bt1의 오른쪽 자식 노드로
	MakeLeftSubTree(bt2, bt4);				// bt4를 bt2의 왼쪽 자식 노드로

	// bt1의 왼쪽 자식 노드의 데이터 출력
	printf("%d \n", GetData(GetLeftSubTree(bt1)));

	// bt1의 왼쪽 자식 노드의 왼쪽 자식 노드의 데이터 출력
	printf("%d \n", GetData(GetLeftSubTree(GetLeftSubTree(bt1))));

	return 0;
}

08-3 이진 트리의 순회(Traversal)
순회의 세 가지 방법

- 전위 순회(Preorder Traversal)            루트 노드를 먼저!

- 중위 순회(Inorder Traversal)              루트 노드를 중간에!

- 후위 순회(Postorder Traversal)          루트 노드를 마지막에!


순회의 재귀적 표현

중위 순회 구현

BinaryTreeTraverseMain.c

/*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>
#include "BinaryTree.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
void InorderTraverse(BTreeNode *bt) {
	if (bt == NULL) {
		return;
	}
	InorderTraverse(bt->left);
	printf("%d \n", bt->data);
	InorderTraverse(bt->right);
}

int main(void) {
	BTreeNode *bt1 = MakeBTreeNode();			// 노드 bt1 생성
	BTreeNode *bt2 = MakeBTreeNode();			// 노드 bt2 생성
	BTreeNode *bt3 = MakeBTreeNode();			// 노드 bt3 생성
	BTreeNode *bt4 = MakeBTreeNode();			// 노드 bt4 생성

	SetData(bt1, 1);			// bt1에 1 저장
	SetData(bt2, 2);			// bt2에 2 저장
	SetData(bt3, 3);			// bt3에 3 저장
	SetData(bt4, 4);			// bt4에 4 저장

	MakeLeftSubTree(bt1, bt2);				// bt2를 bt1의 왼쪽 자식 노드로
	MakeRightSubTree(bt1, bt3);			// bt3를 bt1의 오른쪽 자식 노드로
	MakeLeftSubTree(bt2, bt4);				// bt4를 bt2의 왼쪽 자식 노드로

	InorderTraverse(bt1);
	return 0;
}

중위, 전위, 후위 순회 함수의 유일한 차이점은 루트 노드를 방문하는 문장이 삽입된 위치이다.

void PreorderTraverse(BTreeNode *bt) {
	if (bt == NULL) {
		return;
	}
	printf(" %d="" \n",="" bt-="">data);
	preorderTraverse(bt->left);
	preorderTraverse(bt->right);
}

void PostorderTraverse(BTreeNode *bt) {
	if (bt == NULL) {
		return;
	}
	PostorderTraverse(bt->left);
	PostorderTraverse(bt->right);
	printf("%d \n", bt->data);
}

노드의 방문 이유! 자유롭게 구성하기!

함수 포인터를 사용해서 할일을 결정

문제 08-1 [이진 트리의 소멸] 추가

BinaryTree2.h

#ifndef DATASTRUCTURES_TREE_BINARYTREE2_H_
#define DATASTRUCTURES_TREE_BINARYTREE2_H_
/*---- INCLUDES      --------------------------------------------------------*/

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
typedef int BTData;

typedef struct _bTreeNode {
	BTData data;
	struct _bTreeNode *left;
	struct _bTreeNode *right;
}BTreeNode;

BTreeNode *MakeBTreeNode();
BTData GetData(BTreeNode *bt);
void SetData(BTreeNode *bt, BTData data);

BTreeNode *GetLeftSubTree(BTreeNode *bt);
BTreeNode *GetRightSubTree(BTreeNode *bt);

void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub);
void MakeRightSubTree(BTreeNode *main, BTreeNode *sub);

typedef void VisitFuncPtr(BTData data);

void PreorderTraverse(BTreeNode *bt, VisitFuncPtr action);
void InorderTraverse(BTreeNode *bt, VisitFuncPtr action);
void PostorderTraverse(BTreeNode *bt, VisitFuncPtr action);

void DeleteTree(BTreeNode *bt);

#endif /* DATASTRUCTURES_TREE_BINARYTREE2_H_ */


BinaryTree2.c

/*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree2.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/

BTreeNode *MakeBTreeNode() {
	BTreeNode *newNode = (BTreeNode *)malloc(sizeof(BTreeNode));
	newNode->data = 0;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
}
BTData GetData(BTreeNode *bt) {
	return bt->data;
}
void SetData(BTreeNode *bt, BTData data) {
	bt->data = data;
}

BTreeNode *GetLeftSubTree(BTreeNode *bt) {
	return bt->left;
}
BTreeNode *GetRightSubTree(BTreeNode *bt) {
	return bt->right;
}

void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub) {
	if (main->left != NULL) {
		free(main->left);
	}
	main->left = sub;
}
void MakeRightSubTree(BTreeNode *main, BTreeNode *sub) {
	if (main->right != NULL) {
		free(main->right);
	}
	main->right = sub;
}

void PreorderTraverse(BTreeNode *bt, VisitFuncPtr action) {
	if (bt == NULL) {
		return;
	}
	action(bt->data);
	PreorderTraverse(bt->left, action);
	PreorderTraverse(bt->right, action);
}
void InorderTraverse(BTreeNode *bt, VisitFuncPtr action) {
	if (bt == NULL) {
		return;
	}
	InorderTraverse(bt->left, action);
	action(bt->data);
	InorderTraverse(bt->right, action);
}
void PostorderTraverse(BTreeNode *bt, VisitFuncPtr action) {
	if (bt == NULL) {
		return;
	}
	PostorderTraverse(bt->left, action);
	PostorderTraverse(bt->right, action);
	action(bt->data);
}

void DeleteTree(BTreeNode *bt) {
	if (bt == NULL) {
		return;
	}
	DeleteTree(bt->left);
	DeleteTree(bt->right);
	printf("Delete tree data %d\n", bt->data);
	free(bt);
}


BinaryTreeMain2.c

/*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>
#include "BinaryTree2.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
void ShowIntData(int data);

int main(void) {
	BTreeNode *bt1 = MakeBTreeNode();			// 노드 bt1 생성
	BTreeNode *bt2 = MakeBTreeNode();			// 노드 bt2 생성
	BTreeNode *bt3 = MakeBTreeNode();			// 노드 bt3 생성
	BTreeNode *bt4 = MakeBTreeNode();			// 노드 bt4 생성
	BTreeNode *bt5 = MakeBTreeNode();			// 노드 bt5 생성
	BTreeNode *bt6 = MakeBTreeNode();			// 노드 bt6 생성

	SetData(bt1, 1);			// bt1에 1 저장
	SetData(bt2, 2);			// bt2에 2 저장
	SetData(bt3, 3);			// bt3에 3 저장
	SetData(bt4, 4);			// bt4에 4 저장
	SetData(bt5, 5);			// bt5에 5 저장
	SetData(bt6, 6);			// bt6에 6 저장

	MakeLeftSubTree(bt1, bt2);				// bt2를 bt1의 왼쪽 자식 노드로
	MakeRightSubTree(bt1, bt3);			// bt3를 bt1의 오른쪽 자식 노드로
	MakeLeftSubTree(bt2, bt4);				// bt4를 bt2의 왼쪽 자식 노드로
	MakeRightSubTree(bt2, bt5);				// bt4를 bt2의 왼쪽 자식 노드로
	MakeRightSubTree(bt3, bt6);				// bt4를 bt2의 왼쪽 자식 노드로

	PreorderTraverse(bt1, ShowIntData);
	printf("\n");
	InorderTraverse(bt1, ShowIntData);
	printf("\n");
	PostorderTraverse(bt1, ShowIntData);
	printf("\n");
	DeleteTree(bt1);
}

void ShowIntData(int data) {
	printf("[%d]", data);
}


08-4 수식 트리(Expression Tree)의 구현
수식 트리의 이해

수식 트리는 그냥 수식 트리일 뿐이다. 중위 표기법이 수식 표현의 한가지 방법이라면 수식 트리도 이와 대등한, 수식을 표현하는 또 다른 방법일 뿐이다.

수식 트리 구성 방법

중위 표기법의 수식 -> 후위 표기법의 수식 -> 수식 트리

수식 트리의 구현에 필요한 도구와 헤더파일의 정의

- 수식 트리 구현에 필요한 이진 트리        BinaryTree2.h, BinaryTree2.c

- 수식 트리 구현에 필요한 스택               ListBaseStack.h, ListBaseStack.c


ExpressionTree.h

#ifndef DATASTRUCTURES_TREE_EXPRESSIONTREE_H_
#define DATASTRUCTURES_TREE_EXPRESSIONTREE_H_

/*---- INCLUDES      --------------------------------------------------------*/
#include "BinaryTree2.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
BTreeNode *MakeExpTree(char exp[]);		// 수식 트리 구성
int EvaluateExpTree(BTreeNode *bt);		// 수식 트리 계산

void ShowPrefixTypeExp(BTreeNode *bt);	// 전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode *bt);	// 중위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode *bt);	// 후위 표기법 기반 출력

#endif /* DATASTRUCTURES_TREE_EXPRESSIONTREE_H_ */

후위 표기법의 수식을 기반으로 수식 트리 구성하기

수식 트리의 구성을 위해서는 후위 표기법의 다음 두 가지 특성

- 연산 순서대로 왼쪽에서 오른쪽으로 연산자가 나열된다.

- 해당 연산자의 두 피연산자는 연산자 앞에 나열된다.

"후위 표기법의 수식에서 앞쪽에 등장하는 피연산자와 연산자를 이용해서 트리의 하단을 만들고, 이를 바탕으로 점진적으로 수식 트리의 윗부분을 구성해 나간다!"


수식 트리를 구성하는 방법

- 피연산자를 만나면 무조건 스택으로 옮긴다.

- 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내어 자식 노드로 연결한다.

- 자식 노드를 연결해서 만들어진 트리는 다시 스택으로 옮긴다.


실행을 위해 필요한 파일들

- 이진 트리 관련 BinaryTree2.h, BinaryTree2.c

- 스택 관련 ListBaseStack.h, ListBaseStack.c

- 수식 트리 관련 ExpressionTree.h, ExpressionTree.c

- main 함수 관련 ExpressionMain.c


수식 트리 관련 파일과 main 함수


ExpressionTree.c

/*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "ExpressionTree.h"
#include "../stack/ListBaseStack.h"
#include "BinaryTree2.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
BTreeNode *MakeExpTree(char exp[]) {
	// 수식 트리 구성
	Stack stack;
	BTreeNode *pnode;

	int expLen = strlen(exp);
	int i;

	StackInit(&stack);

	for(i=0; i







ExpressionMain.c


/*---- INCLUDES      --------------------------------------------------------*/
#include 
#include "ExpressionTree.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/

int main(void) {
	char exp[] = "12+7*";
	BTreeNode *eTree = MakeExpTree(exp);

	printf("전위 표기법의 수식: ");
	ShowPrefixTypeExp(eTree);
	printf("\n");

	printf("중위 표기법의 수식: ");
	ShowInfixTypeExp(eTree);
	printf("\n");

	printf("후위 표기법의 수식: ");
	ShowPostfixTypeExp(eTree);
	printf("\n");
}
728x90
저작자표시

'프로그래밍 > 자료구조' 카테고리의 다른 글

Chapter10 정렬(Sorting)  (0) 2018.02.23
Chapter09 우선순위 큐(Priority Queue)와 힙(Heap)  (0) 2018.02.20
Chapter07 큐(Queue)  (0) 2018.01.10
Chapter06 스택(Stack)  (0) 2018.01.02
Chapter05 연결 리스트(Linked List) 3  (0) 2017.12.21

관련글

댓글

티스토리툴바