05_tree

Size: px

Start display at page:

Download "05_tree"

환 애
6 years ago
Views:

1 Tree Data Structures and Algorithms

2 목차 트리의개요 이진트리의구현 이진트리의순회 (Traversal) 수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 2

3 트리의개요 Data Structures and Algorithms 3

4 트리의접근과이해 트리는계층적관계 (Hierarchical Relationship) 를표현하는자료구조 데이터저장과데이터의표현 트리의예 트리의예 : 의사결정트리 Data Structures and Algorithms 4

5 트리관련용어의소개 노드 : node 트리의구성요소 (A, B, C, D, E, F) 간선 : edge 노드와노드를연결하는선 루트노드 : root node 트리구조에서최상위의노드 (A) 단말노드 : terminal node 아래로또다른노드가연결되어있지않은노드 (E, F, C, D) 내부노드 : internal node 단말노드를제외한모든노드 (A, B) Data Structures and Algorithms 5

6 트리의노드간관계 노드 A는노드 B, C, D의부모노드 (parent node) 노드 B, C, D는노드 A의자식노드 (child node) 부모노드가같은노드 B, C, D는형제노드 (sibling node) 부모, 자식관계 형제관계 Data Structures and Algorithms 6

7 서브트리 하나의트리를구성하는왼쪽과오른쪽의작은트리 서브트리역시서브트리로이뤄져있음 서브트리는재귀적 Data Structures and Algorithms 7

8 이진트리 조건 루트노드를중심으로두개의서브트리로나뉨 나뉜두서브트리도모두이진트리이어야함 이진트리의예 Data Structures and Algorithms 8

9 이진트리와공집합노드 공집합 (empty set) 도이진트리에서는노드 다른표현 하나의노드에두개의노드가달리는형태의트리는모두이진트리 Data Structures and Algorithms 9

10 레벨과높이 트리의높이 = 레벨의최대값 높이 = 3 Data Structures and Algorithms 10

11 포화, 완전이진트리 완전이진트리는위에서아래로왼쪽에서오른쪽으로채워진트리 포화이진트리는완전이진트리이지만그역은성립하지않음 모든레벨에노드가꽉찬 포화이진트리 빈틈없이차곡차곡채워짐 완전이진트리 Data Structures and Algorithms 11

12 이진트리의구현 Data Structures and Algorithms 12

13 이진트리구현의두가지방법 배열 : 인덱스를활용하는쉬운접근 노드번호가배열의인덱스 편의상첫요소사용않음 연결리스트 : 직관적구조 트리의구조와리스트의연결구조가일치 Data Structures and Algorithms 13

14 헤더파일에정의된구조체 이진트리의모든노드는직 / 간접적으로연결됨 루트노드의주소만알면이진트리전체탐색가능 typedef struct _btreenode BTData data; struct _btreenode * left; struct _btreenode * right; BTreeNode; Data Structures and Algorithms 14

15 헤더파일에선언된함수들 1 BTreeNode * MakeBTreeNode(void); // 노드의생성 BTData GetData(BTreeNode * bt); // 노드에저장된데이터를반환 void SetData(BTreeNode * bt, BTData data); // 노드에데이터를저장 동적으로노드를생성포인터변수 left 와 right 는 NULL 로초기화 Data Structures and Algorithms 15

16 헤더파일에선언된함수들 2 인자로트리의어떤노드도전달가능 BTreeNode * GetLeftSubTree(BTreeNode * bt); // 좌측서브트리의주소값반환! BTreeNode * GetRightSubTree(BTreeNode * bt); // 우측서브트리의주소값반환! void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub); // main의서브왼쪽서브트리로 sub를연결! void MakeRightSubTree(BTreeNode * main, BTreeNode * sub); // main의오른쪽서브트리로 sub를연결! Data Structures and Algorithms 16

17 main 함수 int main(void) BTreeNode * nda = MakeBTreeNode(); BTreeNode * ndb = MakeBTreeNode(); BTreeNode * ndc = MakeBTreeNode(); // 노드 A 생성 // 노드 B 생성 // 노드 C 생성 ndb, ndb, ndc 를이용한 SetData 함수호출을통해유용한데이터채운후 MakeLeftSubTree(ndA, ndb); // 노드 A 의왼쪽자식노드로노드 B 연결 MakeRightSubTree(ndA, ndc); // 노드 A 의오른쪽자식노드로노드 C 연결.... Data Structures and Algorithms 17

18 이진트리의구현 BTreeNode * MakeBTreeNode(void) BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode)); nd->left = NULL; nd->right = NULL; return nd; BTData GetData(BTreeNode * bt) return bt->data; void SetData(BTreeNode * bt, BTData data) bt->data = data; BTreeNode * GetLeftSubTree(BTreeNode * bt) return bt->left; Data Structures and Algorithms 18

19 이진트리의구현 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; Data Structures and Algorithms 19

20 이진트리활용 main 함수 int main(void) BTreeNode * bt1 = MakeBTreeNode(); BTreeNode * bt2 = MakeBTreeNode(); BTreeNode * bt3 = MakeBTreeNode(); BTreeNode * bt4 = MakeBTreeNode(); main 함수에서생성하는트리 SetData(bt1, 1); SetData(bt2, 2); SetData(bt3, 3); SetData(bt4, 4); MakeLeftSubTree(bt1, bt2); MakeRightSubTree(bt1, bt3); MakeLeftSubTree(bt2, bt4); InorderTraverse(bt1); return 0; Data Structures and Algorithms 20

21 이진트리의순회 (Traversal) Data Structures and Algorithms 21

22 순회의세가지방법 루트방문시점에따라전위, 중위후위순회 높이 2 이상도재귀적으로순회가능 전위중위후위 Data Structures and Algorithms 22

23 순회의재귀적표현 재귀적표현 void InorderTraverse(BTreeNode * bt) InorderTraverse(bt->left); printf("%d \n", bt->data); InorderTraverse(bt->right); 탈출조건이있어야함 Data Structures and Algorithms 23

24 순회의재귀적표현완성! void InorderTraverse(BTreeNode * bt) if(!bt) // bt 가 NULL 이면재귀탈출! InorderTraverse(bt->left); printf("%d \n", bt->data); InorderTraverse(bt->right); 단말노드의자식노드는 NULL Data Structures and Algorithms 24

25 전위순회와후위순회 void PreorderTraverse(BTreeNode * bt) if(!bt) // 전위순위 printf("%d \n", bt->data); PreorderTraverse(bt->left); PreorderTraverse(bt->right); void InorderTraverse(BTreeNode * bt) if(!bt) InorderTraverse(bt->left); // 중위순위 printf("%d \n", bt->data); InorderTraverse(bt->right); void PostorderTraverse(BTreeNode * bt) if(!bt) PostorderTraverse(bt->left); PostorderTraverse(bt->right); // 후위순위 printf("%d \n", bt->data);?? Level Order traversing? Data Structures and Algorithms 25

26 Option: 노드의방문 함수포인터형 VisitFuncPtr 의정의 typedef void VisitFuncPtr(BTData data); void InorderTraverse(BTreeNode * bt, VisitFuncPtr action) if(bt == NULL) return; InorderTraverse(bt->left, action); action(bt->data); // action 이가리키는함수로방문 InorderTraverse(bt->right, action); int main() InorderTraverse(bt1, ShowIntData); // VisitFuncPtr 형을기준으로정의된함수 void ShowIntData(int data) printf("%d ", data); Data Structures and Algorithms 26

27 수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 27

28 수식트리의이해 중위표기법의수식을수식트리로변환하는프로그램 중위표기법의수식은사람이인식하기좋은수식 컴퓨터의인식에는어려움이있음 컴파일러는중위표기법의수식을 수식트리 로재구성 수식트리는해석이쉬움 연산의과정에서우선순위를고려하지않아도됨 int main(void) int result = 0; result = * 2 1;.... 수식트리 Data Structures and Algorithms 28

29 수식트리의계산과정 Data Structures and Algorithms 29

30 수식트리를만드는절차! 중위표기법의수식후위표기법의수식수식트리 중위표기법에서수식트리로변환은어려움 후위표기법으로변경후수식트리로변경 앞서구현한필요한도구들! 수식트리구현에필요한이진트리 BinaryTree2.h, BinaryTree2.c 수식트리구현에필요한스택 ListBaseStack.h, ListBaseStack.c Data Structures and Algorithms 30

31 수식트리의구현과관련된헤더파일 트리만드는도구를기반으로함수를정의 #include "BinaryTree2.h" BTreeNode * MakeExpTree(char exp[]); int EvaluateExpTree(BTreeNode * bt); // 수식트리구성 // 수식트리계산 void ShowPrefixTypeExp(BTreeNode * bt); void ShowInfixTypeExp(BTreeNode * bt); void ShowPostfixTypeExp(BTreeNode * bt); // 전위표기법기반출력 // 중위표기법기반출력 // 후위표기법기반출력 Data Structures and Algorithms 31

32 수식트리의구성방법 : 그림상이해하기 먼저등장하는피연산자와연산자부터트리의하단을구성 * 후위표기법의수식 수식트리 Data Structures and Algorithms 32

33 수식트리의구성방법 : 코드로옮기기 1 피연산자는무조건스택으로! 연산자만나면스택에서 피연산자두개꺼내어트리구성! Data Structures and Algorithms 33

34 수식트리의구성방법 : 코드로옮기기 2 형성된트리는다시스택으로! Data Structures and Algorithms 34

35 수식트리의구성방법 : 코드로옮기기 3 최종결과는스택에서! Data Structures and Algorithms 35

36 수식트리의구성방법 : 코드로옮기기 4 BTreeNode * MakeExpTree(char exp[]) Stack stack; 피연산자는스택에 push BTreeNode * pnode; 연산자를만나면스택에서두개의 int explen = strlen(exp); int i; 피연산자꺼내어자식노드로연결! StackInit(&stack); for(i=0; i<explen; i++) pnode = MakeBTreeNode(); 자식노드를연결해서만들어진트리는 다시스택에 push if(isdigit(exp[i])) // 피연산자라면... SetData(pnode, exp[i]-'0'); else // 연산자라면... MakeRightSubTree(pnode, SPop(&stack)); MakeLeftSubTree(pnode, SPop(&stack)); SetData(pnode, exp[i]); SPush(&stack, pnode); return SPop(&stack); Data Structures and Algorithms 36

37 수식트리의순회 : 그결과 수식트리를구성하면, 전위, 중위, 후위표기법으로의수식표현이쉬움 전회, 중위, 후위순회하면서출력되는결과물을통해서 MakeExpTree 함수를검증가능 전위순회하여데이터를출력한결과 전위표기법의수식 중위순회하여데이터를출력한결과 중위표기법의수식 후위순회하여데이터를출력한결과 후위표기법의수식 Data Structures and Algorithms 37

38 수식트리의순회 : 방법 void ShowPrefixTypeExp(BTreeNode * bt) PreorderTraverse(bt, ShowNodeData); void ShowInfixTypeExp(BTreeNode * bt) InorderTraverse(bt, ShowNodeData); void ShowNodeData(int data) if(0<=data && data<=9) printf("%d ", data); else printf("%c ", data); void ShowPostfixTypeExp(BTreeNode * bt) PostorderTraverse(bt, ShowNodeData); typedef void VisitFuncPtr(BTData data); Data Structures and Algorithms 38

39 수식트리관련예제의실행 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"); // ListBaseStack.h 의 type 선언변경필요 typedef BTreeNode * BTData; printf(" 연산의결과 : %d \n", EvaluateExpTree(eTree)); 이진트리관련 BinaryTree2.h, BinaryTree2.c 스택관련 ListBaseStack.h, ListBaseStack.c 수식트리관련 ExpressionTree.h, ExpressionTree.c main 함수관련 ExpressionMain.c return 0; Data Structures and Algorithms 39

40 수식트리의계산 : 재귀적구성 int EvaluateExpTree(BTreeNode * bt) int op1, op2; // 탈출조건 if(getleftsubtree(bt)==null && GetRightSubTree(bt)==NULL) return GetData(bt); // 재귀적구성 op1 = EvaluateExpTree(GetLeftSubTree(bt)); // 첫번째피연자 op2 = EvaluateExpTree(GetRightSubTree(bt)); // 두번째피연자 switch(getdata(bt)) // 연산자확인 case '+': return op1+op2; case '-': return op1-op2; case '*': return op1*op2; case '/': return op1/op2; return 0; Data Structures and Algorithms 40

Chapter 08. 트리(Tree)

Chapter 08. 트리(Tree) 윤성우의열혈자료구조 : C 언어를이용한자료구조학습서 Chapter 08. 트리 (Tree) Introduction To Data Structures Using C Chapter 08. 트리 (Tree) Chapter 08-1: 트리의개요 트리의접근과이해 트리는계층적관계 (Hierarchical Relationship) 를표현하는자료구조이다. 트리의예 트리의예