08장.트리

Transcription

1 T STRUTURES USING HPTER 트리 /29

2 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모-자식관계의노드들로이루어짐 응용분야 : 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀 생산 팀 생산 2 팀 (a) 회사의조직도 내문서 동영상음악사진 영화예능드라마 여행 (b) 컴퓨터의폴더구조 배경화면 (c) 인공지능바둑프로그램의거대한결정트리 (decision tree) 2/29

3 트리의용어 노드 (node) : 트리의구성요소 루트 (root) : 부모가없는노드 () 서브트리 (subtree) : 하나의노드와자손들로이루어짐 단말노드 (terminal) : 자식이없는노드 (,B,,) 비단말노드 : 자식을가지는노드 (E,F,G,H,I,J) 루트노드 B E F G H I J 서브트리서브트리서브트리 3/29

4 트리의용어 자식, 부모, 형제, 조상, 자손노드 : 인간과동일 레벨 (level) : 트리의각층의번호 높이 (height) : 트리의최대레벨 (3) 차수 (degree) : 노드의자식노드수 부모노드 레벨 3 형제노드 2 나 3 B E F G H I J 자손노드 4/29

5 일반트리의표현 데이터필드 링크필드 일반트리 링크 링크 2... 링크 n data 자식노드 노드의예 : 너무복잡함 데이터필드 링크필드 자식노드 2... 자식노드 n 링크 : 첫번째자식노드연결링크 2: 다음형제노드연결 형제들 data 링크 링크 2 NULL data data data NULL NULL data NULL data data NULL NULL NULL NULL 5/29

6 이진트리 (binary tree) 모든노드가 2 개의서브트리를가지고있는트리 서브트리는공집합일수있다. 데이터필드 링크필드 링크 링크 2 data 이진트리 (binary tree) 왼쪽자식오른쪽자식 각노드에는최대 2개까지의자식노드가존재 모든노드의차수가 2 이하가된다-> 구현하기가편리함 서브트리간의순서가존재 ( 왼쪽, 오른쪽 ) 6/29

7 이진트리의성질 노드의개수가 n 개이면간선의개수는 n- + 노드의개수 : 7 간선의개수 : 6 * / a b c d 높이가 h: 최소 h 개 ~ 최대 2h- 개의노드를가짐 = 높이 =3 2 * / 2 2- =2 3 a b c d 2 3- =4 2 3 최소노드개수 = 3 최대노드개수 = /29

8 이진트리의성질 n 개노드의이진트리높이 : log 2 (n + ) ~ n 2 높이 = 높이 =3 7 8/29

9 이진트리의분류 포화이진트리 (full binary tree) 트리의각레벨에노드가꽉차있는이진트리 B E F G 노드의번호 /29

10 이진트리의분류 완전이진트리 (complete binary tree) 높이가 h 일때레벨 부터 h- 까지는노드가모두채워짐 마지막레벨 h 에서는노드가순서대로채워짐 B E F G 기타이진트리 H I J B 2 3 F G I 0/29

11 이진트리의추상자료형 데이터 : 노드의집합. 공집합이거나, 루트노드와왼쪽서브트리, 오른쪽서브트리로구성됨. 모든서브트리도이진트리이어야함. 연산 : init(): 이진트리를초기화한다. is_empty(): 이진트리가공백상태인지확인한다. create_tree(e, left, right): 이진트리 left 와 right 를받아 e 를루트로하는이진트리를생성한다. get_root(): 이진트리의루트노드를반환한다. get_count(): 이진트리의노드의수를반환한다. get_leaf_count(): 이진트리의단말노드의수를반환한다. get_height(): 이진트리의높이를반환한다. /29

12 2/29 모든이진트리를포화이진트리라고가정 각노드에번호를붙여서그번호를배열의인덱스로삼아노드의데이터를배열에저장 B E F B E F B B 이진트리의표현 : 배열표현법

13 이진트리의표현 : 링크표현법 부모노드가자식노드를가리키게하는방법 포인터를이용 링크 데이터 링크 2 왼쪽자식노드 오른쪽자식노드 NULL B B NULL B B NULL NULL E F NULL NULL NULL E NULL NULL F NULL NULL NULL 3/29

14 링크표현법을이용한이진트리 노드구조체 typedef char TElement; // 트리에저장할데이터의자료형 typedef struct BinTrNode { TElement data; // 노드에저장할데이터 struct BinTrNode* left; // 왼쪽자식노드의포인터 struct BinTrNode* right; // 오른쪽자식노드의포인터 } TNode; 이진트리데이터 TNode* root = NULL; // 루트노드의포인터 4/29

15 이진트리의순회 순회 (traversal) 트리의노드들을체계적으로방문하는것 선형자료구조 ( 큐 ) 에서의순회 하나의방법만존재함 이진트리에서의순회 2 3 B 다양한순회방법이존재함 ( 비선형자료구조 ) 3 2 B E 4 4 F B E 3 F 5 6 순회방법 순회방법 2 5/29

16 이진트리의기본순회 전위순회 (preorder traversal) 루트 왼쪽자식 오른쪽자식 중위순회 (inorder traversal) 왼쪽자식 루트 오른쪽자식 후위순회 (postorder traversal) 왼쪽자식 오른쪽자식 루트 전체트리나서브트리나구조는동일 6/29

17 전위순회 루트 왼쪽서브트리 오른쪽서브트리 preorder(x) if x NULL then print T(x); preorder(left(x)); preorder(right(x)); // x가 NULL이아닐때만처리 // 루트 (x) 노드처리 // 2 왼쪽서브트리방문 // 3 오른쪽서브트리방문 응용분야 : ( 예 ) 구조화된문서출력 자료구조. 자료구조와알고리즘이란? 2. 기초적인자료구조 3. 고급자료구조. 자료구조.2 알고리즘 2. 스택 2.2 큐 2.3 리스트 3. 트리 3.2 그래프 7/29

18 중위순회 왼쪽서브트리 루트 오른쪽서브트리 inorder(x) if x NULL then inorder(left(x)); print T(x); inorder(right(x)); // x가 NULL이아닐때만처리 // 왼쪽서브트리방문 // 2 루트 (x) 노드처리 // 3 오른쪽서브트리방문 void inorder(tnode *n) { if( n!= NULL ) { inorder(n->left); printf("[%c] ", n->data); inorder(n->right); } } 8/29

19 후위순회 왼쪽서브트리 오른쪽서브트리 루트 postorder(x) if x NULL // x가 NULL이아닐때만처리 then postorder(left(x)); // 왼쪽서브트리방문 postorder(right(x)); // 2 오른쪽서브트리방문 print T(x); // 3 루트 (x) 노드처리 응용예 : 폴더용량계산내문서 50KB 00KB 음악 그림 200KB 500KB 사진 동영상 9/29

20 순회방법에따른노드방문순서 전위순회 중위순회 후위순회 /29

21 레벨순회 노드를레벨순으로검사하는순회방법 큐를사용해구현 * / + * / / B B * / B B B /29

22 레벨순회알고리즘 level_order() initialize queue; if(root == NULL) then return; enqueue(root); while isempty(queue) TRUE do x dequeue(queue); if( x NULL) then print T(x); enqueue(left(x)); enqueue(right(x)); 22/29

23 순회프로그램비교 B E F 중위순회전위순회후위순회레벨순회 23/29

24 이진트리연산 : 노드개수 트리의노드개수를계산 count_node(x) if x NULL then return 0; else return +count_node(x.left)+count_node(x.right); int count_node(tnode *n) { if( n == NULL ) return 0; return + count_node(n->left) + count_node(n->right); } 24/29

25 이진트리연산 : 단말노드개수 트리의단말노드개수를계산 count_leaf(x) if x = NULL then return 0; if x.left=null and x.right=null then return ; else return count_leaf(x.left) + count_leaf(x.right); int count_leaf(tnode *n) { if( n == NULL ) return 0; if(n->left == NULL && n->right == NULL ) return ; else return count_leaf(n->left) + count_leaf(n->right); } 25/29

26 이진트리연산 : 트리높이 서브트리들의높이중에서최대값을구하여반환 getheight(x) if x = NULL then return 0; else return + max(getheight(x.left), getheight(x.right); h left h=max(h left,h right ), h right int calc_height(tnode *n) { int hleft, hright; if( n == NULL ) return 0; hleft = calc_height(n->left); hright = calc_height(n->right); return (hleft>hright)? hleft+ : hright+; } 26/29

27 수식트리 산술식을트리형태로표현한것 예 ) 비단말노드 : 연산자 (operator) 단말노드 : 피연산자 (operand) + - or a b a ⅹ < < b c a b c d 수식 a + b a - (b c) (a < b) or (c < d) 전위순회 + a b - a b c or < a b < c d 중위순회 a + b a - b c a < b or c < d 후위순회 a b + a b c - a b < c d < or 27/29

28 수식트리계산 후위순회를사용 서브트리의값을순환호출로계산 비단말노드 : 양쪽서브트리의값을연산자를이용해계산 evaluate(exp) if exp = NULL then return 0; else x evaluate(left(exp)); y evaluate(right(exp)); op T(exp); return (x op y); * /29

29 폴더용량계산 후위순회 내문서 int calc_size(tnode *n) { if( n == NULL ) return 0; return n->data + calc_size(n->left) + calc_size(n->right); } 음악 void main() { TNode *m2, *m3, *m4, *m5; m4 = create_tree ( 200, NULL, NULL ); m5 = create_tree ( 500, NULL, NULL ); m3 = create_tree ( 00, m4, m5 ); m2 = create_tree ( 50, NULL, NULL ); root = create_tree ( 0, m2, m3 ); } 50KB 200KB 사진 그림 00KB 동영상 500KB 29/29