CHAP 7: 트 리 (1) 한 성 대 학 교 정보통신공학과 봉 정 식.

Presentation on theme: "CHAP 7: 트 리 (1) 한 성 대 학 교 정보통신공학과 봉 정 식."— Presentation transcript:

1 CHAP 7: 트 리 (1) 한 성 대 학 교 정보통신공학과 봉 정 식

2 트리(TREE) 트리: 계층적인 구조를 나타내는 자료구조 트리는 부모-자식 관계의 노드들로 이루어진다. 응용분야:
트리: 계층적인 구조를 나타내는 자료구조 트리는 부모-자식 관계의 노드들로 이루어진다. 응용분야: 계층적인 조직 표현 파일 시스템 인공지능에서의 결정트리

3 트리의 용어 노드(node): 트리의 구성요소 루트(root): 부모가 없는 노드(A)
서브트리(subtree): 하나의 노드와 그 노드들의 자손들로 이루어진 트리 A B C D E F G H I J 단말노드(terminal node): 자식이 없는 노드(A,B,C,D) 비단말노드: 적어도 하나의 자식을 가지는 노드(E,F,G,H,I,J) 자식, 부모, 형제, 조상, 자손 노드: 인간과 동일 레벨(level): 트리의 각층의 번호 높이(height): 트리의 최대 레벨(3) 차수(degree): 노드가 가지고 있는 자식 노드의 개수

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

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

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

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

8 이진트리의 분류

9 이진트리의 표현 배열표현법: 모든 이 진트리를 포화이진트리 라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법

10 이진트리의 표현 링크표현법: 포인터를 이용하여 부모노드가 자식 노드를 가리키게 하는 방법

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

12 전위순회 1 2 5 9 3 4 6 7 8 10 11 루트를 먼저 방문하는 순회방법 응용분야: (예) 구조화된 문서출력
// 전위 순회 preorder( TreeNode *root ){   if ( root ){     printf("%d", root->data ); // 노드 방문     preorder( root->left ); // 왼쪽서브트리 순회     preorder( root->right );// 오른쪽서브트리 순회     } } 1 2 5 9 3 4 6 7 8 10 11

13 중위순회 왼쪽서브트리->루트->오른쪽 서브트리 순으로 방문 + * / a b c d 4 2 6 1 3 5 7
// 중위 순회 inorder( TreeNode *root ){   if ( root ){     inorder( root->left );// 왼쪽서브트리 순회     printf("%d", root->data );  // 노드 방문     inorder( root->right );// 오른쪽서브트리 순회     } } 4 + 2 6 * / 1 3 5 7 a b c d

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

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

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

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

18 이진트리연산: 단말 노드 개수 트리안의 노드들을 전체적으로 순회
트리안의 노드들을 전체적으로 순회 순회하면서 만약 왼쪽자식 과 오른쪽 자식이 동시에 0 이 되면 단말노드이므로 1 을 반환하며, 만약 그렇지 않으면 비단말 노드이므로 각각의 서브 트리에 대하여 순환 호출한 다음, 반환값 을 서로 더한다. int get_leaf_count(TreeNode *node) { int count = 0; if( node != NULL ) { if( node->left == NULL && node->right == NULL) return 1; else count = get_left_count(node->left) + get_left_count(node->right); } return count; 1 3 2 6

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

20 @ To be continue...