Tree Data Structures and Algorithms
목차 트리의개요 이진트리의구현 이진트리의순회 (Traversal) 수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 2
트리의개요 Data Structures and Algorithms 3
트리의접근과이해 트리는계층적관계 (Hierarchical Relationship) 를표현하는자료구조 데이터저장과데이터의표현 트리의예 트리의예 : 의사결정트리 Data Structures and Algorithms 4
트리관련용어의소개 노드 : 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
트리의노드간관계 노드 A는노드 B, C, D의부모노드 (parent node) 노드 B, C, D는노드 A의자식노드 (child node) 부모노드가같은노드 B, C, D는형제노드 (sibling node) 부모, 자식관계 형제관계 Data Structures and Algorithms 6
서브트리 하나의트리를구성하는왼쪽과오른쪽의작은트리 서브트리역시서브트리로이뤄져있음 서브트리는재귀적 Data Structures and Algorithms 7
이진트리 조건 루트노드를중심으로두개의서브트리로나뉨 나뉜두서브트리도모두이진트리이어야함 이진트리의예 Data Structures and Algorithms 8
이진트리와공집합노드 공집합 (empty set) 도이진트리에서는노드 다른표현 하나의노드에두개의노드가달리는형태의트리는모두이진트리 Data Structures and Algorithms 9
레벨과높이 트리의높이 = 레벨의최대값 높이 = 3 Data Structures and Algorithms 10
포화, 완전이진트리 완전이진트리는위에서아래로왼쪽에서오른쪽으로채워진트리 포화이진트리는완전이진트리이지만그역은성립하지않음 모든레벨에노드가꽉찬 포화이진트리 빈틈없이차곡차곡채워짐 완전이진트리 Data Structures and Algorithms 11
이진트리의구현 Data Structures and Algorithms 12
이진트리구현의두가지방법 배열 : 인덱스를활용하는쉬운접근 노드번호가배열의인덱스 편의상첫요소사용않음 연결리스트 : 직관적구조 트리의구조와리스트의연결구조가일치 Data Structures and Algorithms 13
헤더파일에정의된구조체 이진트리의모든노드는직 / 간접적으로연결됨 루트노드의주소만알면이진트리전체탐색가능 typedef struct _btreenode BTData data; struct _btreenode * left; struct _btreenode * right; BTreeNode; Data Structures and Algorithms 14
헤더파일에선언된함수들 1 BTreeNode * MakeBTreeNode(void); // 노드의생성 BTData GetData(BTreeNode * bt); // 노드에저장된데이터를반환 void SetData(BTreeNode * bt, BTData data); // 노드에데이터를저장 동적으로노드를생성포인터변수 left 와 right 는 NULL 로초기화 Data Structures and Algorithms 15
헤더파일에선언된함수들 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
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
이진트리의구현 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
이진트리의구현 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
이진트리활용 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
이진트리의순회 (Traversal) Data Structures and Algorithms 21
순회의세가지방법 루트방문시점에따라전위, 중위후위순회 높이 2 이상도재귀적으로순회가능 전위중위후위 Data Structures and Algorithms 22
순회의재귀적표현 재귀적표현 void InorderTraverse(BTreeNode * bt) InorderTraverse(bt->left); printf("%d \n", bt->data); InorderTraverse(bt->right); 탈출조건이있어야함 Data Structures and Algorithms 23
순회의재귀적표현완성! 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
전위순회와후위순회 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
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
수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 27
수식트리의이해 중위표기법의수식을수식트리로변환하는프로그램 중위표기법의수식은사람이인식하기좋은수식 컴퓨터의인식에는어려움이있음 컴파일러는중위표기법의수식을 수식트리 로재구성 수식트리는해석이쉬움 연산의과정에서우선순위를고려하지않아도됨 int main(void) int result = 0; result = 7 + 4 * 2 1;.... 수식트리 Data Structures and Algorithms 28
수식트리의계산과정 Data Structures and Algorithms 29
수식트리를만드는절차! 중위표기법의수식후위표기법의수식수식트리 중위표기법에서수식트리로변환은어려움 후위표기법으로변경후수식트리로변경 앞서구현한필요한도구들! 수식트리구현에필요한이진트리 BinaryTree2.h, BinaryTree2.c 수식트리구현에필요한스택 ListBaseStack.h, ListBaseStack.c Data Structures and Algorithms 30
수식트리의구현과관련된헤더파일 트리만드는도구를기반으로함수를정의 #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
수식트리의구성방법 : 그림상이해하기 먼저등장하는피연산자와연산자부터트리의하단을구성 1 2 + 7 * 후위표기법의수식 수식트리 Data Structures and Algorithms 32
수식트리의구성방법 : 코드로옮기기 1 피연산자는무조건스택으로! 연산자만나면스택에서 피연산자두개꺼내어트리구성! Data Structures and Algorithms 33
수식트리의구성방법 : 코드로옮기기 2 형성된트리는다시스택으로! Data Structures and Algorithms 34
수식트리의구성방법 : 코드로옮기기 3 최종결과는스택에서! Data Structures and Algorithms 35
수식트리의구성방법 : 코드로옮기기 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
수식트리의순회 : 그결과 수식트리를구성하면, 전위, 중위, 후위표기법으로의수식표현이쉬움 전회, 중위, 후위순회하면서출력되는결과물을통해서 MakeExpTree 함수를검증가능 전위순회하여데이터를출력한결과 전위표기법의수식 중위순회하여데이터를출력한결과 중위표기법의수식 후위순회하여데이터를출력한결과 후위표기법의수식 Data Structures and Algorithms 37
수식트리의순회 : 방법 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
수식트리관련예제의실행 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
수식트리의계산 : 재귀적구성 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