7장

Transcription

1 CHAP 7: 트리 C 로쉽게풀어쓴자료구조

2 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현파일시스템인공지능에서의결정트리 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산 1 팀생산 2 팀 * 예제 : 책그림 7-2, 7-3, 7-4

3 트리의용어 노드 (node): 트리의구성요소 루트 (root): 부모가없는노드 (A) 서브트리 (subtree): 하나의노드와그노드들의자손들로이루어진트리 A B C D E F G H I J 단말노드 (terminal node): 자식이없는노드 (E,F,G,H,I,J) 비단말노드 : 적어도하나의자식을가지는노드 (A,B,C,D) 자식, 부모, 형제, 조상, 자손노드 : 인간과동일 간선 (edge) : 루트와서브트리를연결하는선

4 트리의용어 노드의차수 : 노드의서브트리의수 트리의차수 : 트리에있는노드의최대차수 level: root node는1, 다른노드는부모노드에 1을더한다. depth (or height) of a tree: 트리 에속한노드의최대레벨 K B A C E F G H I J L M D Level * See 예제 7.1

5 이진트리

6 이진트리 (binary tree) 이진트리 (binary tree) : 모든노드가 2 개의서브트리를가지고있는트리 - 서브트리는공집합일수있다. Ex) 그림 7.8 이진트리 (binary tree) 이진트리의노드에는최대 2 개까지의자식노드가존재 모든노드의차수가 2 이하가된다 -> 구현하기가편리함 이진트리에는서브트리간의순서가존재

7 이진트리 (binary tree) Representation of trees 차수가 2 인트리표현 왼쪽자식 - 오른쪽형제트리를 45 도시계방향으로돌린다. 왼쪽자식 - 오른쪽자식트리 이진트리 (binary tree)

8 이진트리 (binary tree) Representation of trees A B C D A E F G B tree E C A F D B C D G binary tree E F G left child-right sibling tree

9 이진트리 (binary tree) A A A B B B tree left child-right sibling tree binary tree A A A B B C B C C tree left child-right sibling tree tree representations binary tree

10 이진트리의성질 노드의개수가 n 개이면간선의개수는 n-1 높이가 h 인이진트리의경우, 최소 h 개의노드를가지며최대 2 h -1 개의노드를가진다.

11 이진트리의성질 n 개의노드를가지는이진트리의높이는최대 n 이거나최소

12 이진트리의분류 포화이진트리 (full binary tree): 트리의각레벨에노드가꽉차있는이진트리 * see 그림 7-14 완전이진트리 (complete binary tree): 높이가 h 일때레벨 1 부터 h 까지는노드가모두채워져있고마지막레벨 h 에서는왼쪽부터오른쪽으로노드가순서대로채워져있는이진트리

13 이진트리의분류 Are they different or same binary trees? A A B B

14 이진트리의표현 1) 배열표현법 : 모든이진트리를포화이진트리라고가정하고각노드에번호를붙여서그번호를배열의인덱스로삼아배열에저장하는방법 2) 링크표현법 : 포인터를이용하여부모노드가자식노드를가리키게하는방법

15 이진트리의표현

16 이진트리의표현 (1) 1) array representation of binary trees ( 배열사용 ) 모든이진트리를포화이진트리라고가 정하고각노드에번호를붙여서그 번호를배열의인덱스로삼아노드의 데이터를배열에저장하는방법 E D C B A [1] [2] [3] [4] [5] [6] [7] [8] [9] [16] A B - C D - E H [1] [2] [3] [4] [5] [6] [7] [8] [9] D B I A B C D E F G H I complete binary tree E A F C G skew binary tree

17 이진트리의표현 (2) 2) Link 표현 각노드의구성요소 : left_child, data, right_child typedef struct TreeNode { int data; strut TreeNode *left_child, *right_child; TreeNode; left_child data right_child 노드표현 left_child data right_child

18 이진트리의표현 (2) root A NULL root A B NULL B C C NULL D NULL E NULL NULL F NULL NULL G NULL D NULL NULL H NULL NULL I NULL NULL E NULL skewed binary tree complete binary tree 이진트리의링크연결

19 이진트리의표현 (2) 단말노드 :leaf node s link fields contain null pointer NULL data 단말노드 NULL 부모노드를알려면 4 번째필드첨가 parent parent left_child data right_child data left_child right_child

20 연습 링크법을이용한이진트리생성

21 트리자료구조만들기 연결리스트를이용한트리 먼저트리의기본자료타입을만들어보자. typedef struct tree_node { int data; struct tree_node *left_child, *right_child; tree_node;

22 트리생성 다음과같은트리를만들어보자 n1 n2 n3 우선 root node 만들기 tree_node *root;

23 트리에원소만들기연습 트리에원소생성 int main() { tree_node *n1, *n2, *n3; n1 = (tree_node *)malloc(sizeof(tree_node)); n2 = (tree_node *)malloc(sizeof(tree_node)); n3 = (tree_node *)malloc(sizeof(tree_node)); // 첫번쨰노드를설정한다. n1->data = 10; n1->left_child = n2; n1->right_child = n3; n2->data = 20; // 두번쨰노드를설정한다... 첫번쨰노드와같이설정 n3->data = 30; // 세번쨰노드를설정한다... 첫번쨰노드와같이설정 // 루트노드를 n1 으로한다. root = n1;

24 Binary Tree Traversal and Other Operations 이진트리순회

25 이진트리의순회 순회 (traversal): 트리의노드들을체계적으로방문하는것 L : 왼쪽이동 V : 노드방문 R : 오른쪽이동 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV

26 이진트리의순회 왼쪽을오른쪽보다먼저방문하는경우 3가지의기본적인순회방법 전위순회 (preorder traversal) : VLR 자손노드보다루트노드를먼저방문한다. 중위순회 (inorder traversal) : LVR 왼쪽자손, 루트, 오른쪽자손순으로방문한다. 후위순회 (postorder traversal) : LRV 루트노드보다자손을먼저방문한다.

27 전위순회 루트를먼저방문하는순회방법 루트 왼쪽서브트리 오른쪽서브트리 응용분야 :( 예 ) 구조화된문서출력 // 전위순회 preorder( TreeNode *root ){ if ( root ){ printf("%d", root->data ); // 노드방문 preorder( root->left ); // 왼쪽서브트리순회 preorder( root->right );// 오른쪽서브트리순회 1 자료구조 자료구조와알고리즘이란? 2. 기초적인자료구조 3. 고급자료구조 자료구조 1.2 알고리즘 2.1 스택 2.2 큐 2.3 리스트 3.1 트리 3.2 그래프

28 중위순회 왼쪽서브트리 루트 오른쪽서브트리순으로방문 // 중위순회 inorder( TreeNode *root ){ if ( root ){ inorder( root->left );// 왼쪽서브트리순회 printf("%d", root->data ); // 노드방문 inorder( root->right );// 오른쪽서브트리순회 * / a b c d 8

29 후위순회 왼쪽서브트리 오른쪽서브트리 루트순으로방문 ( 예 ) 디렉토리용량계산 // 후위순회 postorder( TreeNode *root ){ if ( root ){ postorder( root->left );// 왼쪽서브트리순회 postorder( root->right );// 오른쪽서브트리순회 printf("%d", root->data ); // 노드방문

30 트리연습 (2) 앞에서만들어본예제에순회함수를첨가한다 void inorder( tree_node *ptr ){ if ( ptr ){ inorder( ptr->left_child ); printf("%d ", ptr->data ); inorder( ptr->right_child ); // 좌측서브트리검사 // 노드방문 // 우측서브트리검사 중위순회 void preorder( tree_node *ptr ){ if ( ptr ){ printf("%d ", ptr->data ); // 노드방문 preorder( ptr->left_child ); // 좌측서브트리검사 preorder( ptr->right_child ); // 우측서브트리검사 전위순회

31 트리연습 (2) void postorder( tree_node *ptr ){ if ( ptr ){ postorder( ptr->left_child ); postorder( ptr->right_child ); printf("%d ", ptr->data ); 후위순회 // 좌측서브트리검사 // 우측서브트리검사 // 노드방문

32 트리순회연습 트리순회연습 int main() { tree_node *n1, *n2, *n3; // 루트노드를 n1 으로한다. root = n1; printf("\ninorder\n"); inorder(root); printf("\npreorder\n"); preorder(root); printf("\npostorder\n"); postorder(root); system("pause"); return 0;

33 수식트리 수식트리 : 산술식을트리형태로표현한것 예 ) 비단말노드 : 연산자 (operator) 단말노드 : 피연산자 (operand) 수식 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

34 수식트리계산 후위순회를사용 서브트리의값을순환호출로계산 비단말노드를방문할때양쪽서브트리의값을저장된연산자를이용하여계산 evaluate(exp) if exp = NULL then return 0; else x evaluate(exp->left); y evaluate(exp->right); op exp->data; return (x op y);

35 이진트리연산 : 노드개수 탐색트리안의노드의개수를계산 각각의서브트리에대하여순환호출한다음, 반환되는값에 1 을더하여반환 int get_node_count(treenode *node) { int count=0; if( node!= NULL ) count = 1 + get_node_count(node->left)+ return count; get_node_count(node->right);

36 이진트리연산 : 높이 서브트리에대하여순환호출하고서브트리들의반환값중에서최대값을구하여반환 int get_height(treenode *node) { int height=0; if( node!= NULL ) height = 1 + max(get_height(node->left), return height; get_height(node->right));

37 트리연습 (3) 트리노드수 트리높이 1. 파일 binarytree.c를열어실행해본다. 2. get_node_count 함수만들기 int get_node_count(tree_node *node) { int count=0; if( node!= NULL ) count = 1 + get_node_count(node->left_child)+ get_node_count(node->right_child); return count;

38 트리연습 (3) 트리노드수 트리높이 3. get_height 함수만들기 max 는두수중큰수를돌려주는함수 작성해보세요 int get_height(tree_node *node) { int height=0; if( node!= NULL ) height = 1 + max(get_height(node->left_child), get_height(node->right_child)); return height;

39 트리연습 (3) 트리노드수 트리높이 4. 테스트하기 int main() { tree_node *n1, *n2, *n3;... printf("\ 노드수 = %d\n", get_node_count(root) ); printf("\ 트리높이 = %d\n", get_height(root) ); return 0;

40 트리연습 (4) Binary Tree Operations 연습 후위순회를이용한수식계산 *

41 트리연습 (4) - 수식계산함수 int evaluate(tree_node *root) { if( root == NULL) return 0; if( root->left_child == NULL && root->right_child == NULL) return root->data; else { int op1 = evaluate(root->left_child); int op2 = evaluate(root->right_child); switch(root->data){ case '+': return op1+op2; case '-': return op1-op2; case '*': return op1*op2; case '/': return op1/op2; return 0;

42 트리연습 (4) - 수식계산프로그램 int main() { tree_node n1={1, NULL, NULL; tree_node n2={4, NULL, NULL; tree_node n3={'*', &n1, &n2; tree_node n4={16, NULL, NULL; tree_node n5={25, NULL, NULL; tree_node n6={'+', &n4, &n5; tree_node n7={'+', &n3, &n6; tree_node *exp= &n7; 즐겁게연습하세요 printf("%d \n", evaluate(exp)); return 0;