Chapter 08. 트리(Tree)

Transcription

1 윤성우의열혈자료구조 : C 언어를이용한자료구조학습서 Chapter 08. 트리 (Tree) Introduction To Data Structures Using C

2 Chapter 08. 트리 (Tree) Chapter 08-1: 트리의개요

3 트리의접근과이해 트리는계층적관계 (Hierarchical Relationship) 를표현하는자료구조이다. 트리의예 트리의예 : 의사결정트리 트리는단순한데이터의저장을넘어서 데이터의표현을위한도구이다!

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

5 트리의노드간관계 부모, 자식관계 부모, 자식관계 형제관계 형제관계 노드 A 는노드 B, C, D 의부모노드 (parent node) 이다. 노드 B, C, D 는노드 A 의자식노드 (child node) 이다. 노드 B, C, D 는부모노드가같으므로, 서로가서로에게형제노드 (sibling node) 이다.

6 서브트리의이해 서브트리역시서브트리로이뤄져있으며, 그서브트리역시또 다른서브트리로이뤄져있다. 이렇듯트리는그구조가재귀적이다! 하나의트리를구성하는왼쪽과오른쪽의작은트 리를가리켜서브트리라한다. 서브트리역시또다른 서브트리를갖는다!

7 이진트리의이해 이진트리의조건 루트노드를중심으로두개의서브트리로나뉘어진다. 나뉘어진두서브트리도모두이진트리이어야한다. 이진트리의예 이진트리가되려면, 루트노드를중심으로둘로나뉘는두개의서브트리도이진트리이어야하 고, 그서브트리의모든서브트리도이진트리이어야한다. 재귀적인성향을담아내지못한완전하지않은표현 트리그리고이진트리는그구조가재귀적이다! 따라서트리와관련된연산은재귀적으로사고하고재귀적으로구현할필요가있다!

8 이진트리와공집합노드 공집합 (empty set) 도이진트리에서는노드로간주한다! 다른표현 하나의노드에두개의노드가달리는 형태의트리는모두이진트리이다.

9 레벨과높이, 그리고포화, 완전이진트리 높이는 3! 트리의높이와레벨의최대값은같다! 모든레벨에노드가꽉찬! 포화이진트리 완전이진트리는위에서아래로왼쪽에서오른쪽으로채워진트리를의미한다. 따라서포화이진트리는동시에완전이진트리이지만그역은성립하지않는다. 빈틈없이차곡차곡채워진! 완전이진트리

10 Chapter 08. 트리 (Tree) Chapter 08-2: 이진트리의구현

11 이진트리구현의두가지방법 노드에번호를부여하고그번호에해당하는값을 배열의인덱스값으로활용한다. 편의상배열의첫번째요소는사용하지않는다. 배열의기본적인장정! 접근이용이하다라는특성이트리에서도그대로반영이된다! 뿐만아니라 배열을기반으로했을때완성하기용이한트리관련연산도존재한다. 연결리스트기반에서는트리의구조와리스트의연결구조가일치한다. 따라서구현과관련된직관적인이해가더좋은편이다.

12 헤더파일에정의된구조체의이해 이것이노드이자이진트리를표현한구조체의정의이다! 이진트리의모든노드는직 / 간접적으로연결되어있다. 따라서루트노드의주소값만기억하면, 이진트리전체를가리키는것과다름이없다. 논리적으로도하나의노드는그자체로이진 트리이다. 따라서노드를표현한구조체는실 제로이진트리를표현한구조체가된다.

13 헤더파일에선언된함수들 1 BTreeNode * MakeBTreeNode(void); // 노드의생성 이러한형태의노드를동적으로할당하여생성한다! 유효한데이터는 SetData 함수를통해서채우되포인터 변수 left 와 right 는 NULL 로자동초기화된다. BTData GetData(BTreeNode * bt); // 노드에저장된데이터를반환 void SetData(BTreeNode * bt, BTData data); // 노드에데이터를저장 노드에직접접근하는것보다. 함수를통한접근이보다칭찬받을수있는구조!

14 헤더파일에선언된함수들 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를연결! 하나의노드도일종의이진트리이다! 따라서위와같이함수를이름을짓는것이타당하다! 위의함수들은단순히노드가아니라트리를대상으로도그결과를보인다는사실을기억하자!

15 정의된함수들의이해를돕는 main 함수 int main(void) { BTreeNode * nda = MakeBTreeNode(); BTreeNode * ndb = MakeBTreeNode(); BTreeNode * ndc = MakeBTreeNode(); // 노드 A 생성 // 노드 B 생성 // 노드 C 생성 ndb, ndb, ndc 를이용한 SetData 함수호출을통해유용한데이터채운후 // 노드 A 의왼쪽자식노드로노드 B 연결 MakeLeftSubTree(ndA, ndb); // 노드 A 의오른쪽자식노드로노드 C 연결 MakeRightSubTree(ndA, ndc); }.... 앞서정의한이진트리관련함수들은이진트리를만드는도구이다!

16 이진트리의구현 구현자체는크게어려움이없다! 기존에연결된노드는 삭제되게구현! 기존에연결된노드는 삭제되게구현!

17 이진트리관련 main 함수 main 함수에서생성하는트리 실행결과 트리를완전히소멸시키는방법은? 순회!

18 Chapter 08. 트리 (Tree) Chapter 08-3: 이진트리의순회 (Traversal)

19 순회의세가지방법 기준은루트노드를언제방문하느냐에있다! 즉루트노드를방문하는시점에따라서중위, 후위, 전위순회로나뉘어진다. 높이가 2 이상인트리의순회도이와다르지않다. 재귀적인형태로순회의과정을구성하면높이에상관없이순회가가능하다!

20 순회의재귀적표현 재귀적표현 탈출조건이명시되지않은불완전한구현

21 순회의재귀적표현완성! 노드가단말노드인경우, 단말노드의자식노드는 NULL 이다! 적용가능

22 지금까지의결과물실행 실행결과

23 전위순회와후위순회 중위순회 전위순회 후위순회

24 노드의방문이유! 자유롭게구성하기! (*VisitFuncPtr) 로대신해도됩니다. typedef void VisitFuncPtr(BTData data); 함수포인터형 VisitFuncPtr 의정의 void InorderTraverse(BTreeNode * bt, VisitFuncPtr action) { if(bt == NULL) return; } InorderTraverse(bt->left, action); action(bt->data); // 노드의방문 InorderTraverse(bt->right, action); action 이가리키는함수를통해서방문을진행 ~ void ShowIntData(int data) { printf("%d ", data); } VisitFuncPtr 형을기준으로정의된함수

25 Chapter 08. 트리 (Tree) Chapter 08-4: 수식트리 (Expression Tree) 의구현

26 수식트리의이해 중위표기법의수식을수식트리로변환하는프로그램의작성이목적! int main(void) { int result = 0; result = * 2 1; }.... 수식트리 두개의자식노드에는피연산자를! 중위표기법의수식은사람이인식하기좋은수식이다. 컴퓨터의인식에는어려움이있다. 그래서컴파일러는중위표기법의수식을 수식트리 로재구성한다. 수식트리는해석이쉽다. 연산의과정에서우선순위를고려하지않아도된다!

27 수식트리의계산과정 두개의자식노드기피연산자라는 단순하지만전부인하나의특성을근거로 연산이매우쉽게진행된다!

28 수식트리를만드는절차! Ch06 의 ConvToRPNExp 함수에서구현 중위표기법의수식 후위표기법의수식 수식트리 그래서후위표기법의수식을수식트리로구성하는방법만고민! 중위표기법의수식을바로수식트리로표현하는것은쉽지않다. 하지만일단후위표기법의수식으로변경한다음에수식트리로표현하는것은어렵지않다! 앞서구현한필요한도구들! 수식트리구현에필요한이진트리 수식트리구현에필요한스택 BinaryTree2.h, BinaryTree2.c ListBaseStack.h, ListBaseStack.c

29 수식트리의구현과관련된헤더파일 #include "BinaryTree2.h 트리만드는도구를기반으로함수를정의한다! BTreeNode * MakeExpTree(char exp[]); // 수식트리구성후위표기법의수식을인자로받아서수식트리를구성하고루트노드의주소값을반환한다! int EvaluateExpTree(BTreeNode * bt); // 수식트리계산 MakeExpTree 가구성한수식트리의수식을계산하여그결과를반환한다! void ShowPrefixTypeExp(BTreeNode * bt); // 전위표기법기반출력 void ShowInfixTypeExp(BTreeNode * bt); // 중위표기법기반출력 void ShowPostfixTypeExp(BTreeNode * bt); // 후위표기법기반출력전위, 중위, 후위순회하여출력시각각전위, 중위, 후위표기법의수식이출력된다.

30 수식트리의구성방법 : 그림상이해하기 * 후위표기법의수식 수식트리 후위표기법의수식에서먼저등장하는피연산자와연산자를이용해서트리의하단부 터구성해나가고이어서점진적으로윗부분을구성해나간다. 이사실을이해하는것과이를코드로옮기는것은다소다른문제이다!

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

32 수식트리의구성방법 : 코드로옮기기 2 형성된트리는다시스택으로! 최종결과는스택에서!

33 수식트리의구성방법 : 코드로옮기기 3 BTreeNode * MakeExpTree(char exp[]) { Stack stack; 피연산자는스택으로옮긴다. BTreeNode * pnode; 연산자를만나면스택에서두개의피연산자꺼내어자식노드로연결! int explen = strlen(exp); 자식노드를연결해서만들어진트리는다시스택으로옮긴다. int i; for(i=0; i<explen; i++) { pnode = MakeBTreeNode(); 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); }

34 수식트리의순회 : 그결과 전위순회하여데이터를출력한결과 중위순회하여데이터를출력한결과 후위순회하여데이터를출력한결과 전위표기법의수식 중위표기법의수식 후위표기법의수식 수식트리를구성하면, 전위, 중위, 후위표기법으로의수식표현이쉬워진다. 그리고전회, 중위, 후위순회하면서출력되는결과물을통해서 MakeExpTree 함수를검증할수 있다.

35 수식트리의순회 : 방법 VisitFuncPtr 형함수 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); 후위표기법수식출력 }

36 수식트리관련예제의실행 ListBaseStack.h 의 type 선언변경필요하다! typedef BTreeNode * BTData; 이진트리관련 BinaryTree2.h, BinaryTree2.c 스택관련 ListBaseStack.h, ListBaseStack.c 수식트리관련 ExpressionTree.h, ExpressionTree.c main 함수관련 ExpressionMain.c 실행결과

37 수식트리의계산 : 기본구성 int EvaluateExpTree(BTreeNode * bt) { int op1, op2; op1 = GetData(GetLeftSubTree(bt)); // 첫번째피연산자 op2 = GetData(GetRightSubTree(bt)); // 두번째피연산자 switch(getdata(bt)) // 연산자를확인하여연산을진행 { case '+': return op1+op2; case '-': return op1-op2; case '*': return op1*op2; case '/': return op1/op2; } return 0; } 이모델을대상으로한구현

38 수식트리의계산 : 재귀적구성 int EvaluateExpTree(BTreeNode * bt) { int op1, op2; op1 = GetData(GetLeftSubTree(bt)); // 첫번째피연산자 op2 = GetData(GetRightSubTree(bt)); // 두번째피연산자 switch(getdata(bt)) // 연산자를확인하여연산을진행 { 재귀적구성 case '+': op1 = EvaluateExpTree(GetLeftSubTree(bt)); return op1+op2; op2 = EvaluateExpTree(GetRightSubTree(bt)); case '-': return op1-op2; case '*': return op1*op2; case '/': return op1/op2; } return 0; } 이모델을대상으로한구현단! 단말노드에대해서는고려되지않았다!

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)) {.... 이전과동일.... } return 0; 이모델을대상으로한구현 단말노드는탈출의조건이다!

40 수고하셨습니다 ~ Chapter 08 에대한강의를마칩니다!