제 5 장 트 리 5.1 트리 5.2 이진 트리 5.3 스레드 이진 트리

1.트리의 정의 트리(Tree) ◀정의▶ 트리는 아래의 조건을 만족하는 하나 이상의 노드(node)들로 구성된 유한집합 T. ① 노드중에는 근노드(root)라고 하는 특정한 한 개의 노 드가 존재 ② 근노드를 제외한 나머지 노드들은 n개(n0)의 부분집합 T1, T2,…, Tn으로 나누어지며 가가 Ti는 하나의 트리이다. 이 때, 각 Ti들은 트리 T의 서브트리(subtree)라고 한다.

1-1트리의 예 대학 공과대학 기계과 이과대학 경상대학 전산학부 수학과 건축과 경제과 MIS과 물리과 무역과 전산과 컴공과

2. 트리의 용어 ①하나의 루트 노드 (root node) ②나머지 노드들은 n(0)개의 분리 집합(disjoint set) T1, T2, … , Tn으로 분할 (Ti : 서브트리) 노드의 차수(degree) : 노드의 서브트리 수 단말(terminal) 노드 : 차수 = 0, leaf 비단말 노드 : 차수  0 노드 레벨 : 루트의 레벨을 0으로 정의 트리의 차수 = max{노드의 차수} 자식(child), 형제(sibling) 선조(ancestor) : 루트까지의 경로상에 있는 모든 노드 후손(descendants) : 한 노드의 서브트리에 존재하는 모든 노드 트리의 높이 (height, depth) = max{노드 레벨} 숲(forest) : 트리에서 루트를 제거하여 만듬

2. 트리의 용어 레벨(level) A B C D 1 E F H G I J 2 K L M 3 4 N 예제 트리

노드의 차수(degree) A의 차수 : 3 B의 차수 : 2 C의 차수 : 1 단말(terminal) 노드 : 차수 = 0, leaf F, G, I, J, K, L, N 트리의 차수 = max{노드의 차수} : 3 sibling(형제노드) of D = {B, C} childeren(자식노드) of D = { H, I ,J } ancestor(조상노드) of M = { H, D, A } descendentor(후손노드) of D = { H, I, J, M, N} 트리의 높이 (height, depth) = max{노드 레벨}+1 = 5

숲(forest) : 트리에서 루트를 제거하여 만듬 B C D E F H G I J K L M N

◆ 트리의 종류 순서 트리 (ordered tree) : 레벨이 같은 노드들의 좌우 배열 순서의 위치가 고정되어 노드들의 위치가 중요한 트리. 비순서 트리 (nonordered tree) : 계층상 의미가 중요, 형제 노드들의 위치는 중요하지 않음. 닮은 트리 (similar tree): 트리의 노드와 위치는 같으나 내용만 다른 트리. 이진 트리 (binary tree) : 자식 노드가 2개 이하인 트리. (차수가 2이하인 트리) 경사 트리 (skewed tree) : 좌측 또는 우측의 서브트리만 존재하는 트리.

3. 트리의 표현 • 개념적 표현구조 • 집합을 이용한 트리 표현 • 연결리스트를 이용한 표현

개념적 표현 (A(B(E(K,L),F),C(G),D(H(M(N)),I,J))) A B E K L D H M N F J C I

트리 표현(1) 리스트 표현 : 차수가 k인 트리의 노드 구조 level A B C D 1 E F G H I J 2 K L M B C D 1 E F G H I J 2 K L M 3 sibling childeren of D 샘플 트리 리스트 표현 : 차수가 k인 트리의 노드 구조

리스트 트리 표현(2) data CHILD1 CHILD2 ... CHILDk A B C D E F G H I 각각의 노드는 가변적인 포인터 수를 가지므로 효율적인 표현 방법이 되지 못한다. 이 문제를 해결하기 위해 포인터 수를 2개로 고정한 방법이 left child, right sibling 표현 방법과 이진 트리 표현 방법이다.

left child, right sibling 표현방법 고정된 포인터 수를 가지는 표현 방법으로 다음과 같은 노드 구조. left child right sibling data (정의)left child-right sibling 노드 struct child_siling { char data; struct child_sibling *first_child; struct child_sibling *next_sibling; }; 하나의 포인터를 자신의 첫번째 child 노드를 가리키고, 또 하나의 포인터는 인접한 sibling 노드를 가리키도록 한다.

트리 표현(3) 왼쪽 자식-오른쪽 형제 표현 A B E K L F G C D H I J M A B C D E F H G I J

4. 이진트리의 정의 * 가장 중요하고 자주 사용되는 트리 * 이진 트리는 모든 노드의 차수가 2를 넘지 않는 특수한 트리 * 하나의 노드는 2개의 자식 노드를 가질 수 있다 ( 왼쪽 자식 노드와 오른쪽 자식 노드) * 일반 트리에서는 자식 노드들의 순서를 구별하지 않지만 * 이진 트리에서는 자식 노드의 순서를 구별

이진 트리와 일반트리의 차이 이진 트리와 일반 트리의 차이점 서로 다른 두 이진 트리 공백 이진 트리 존재 서브트리의 순서 중요 서로 다른 두 이진 트리 A B empty right subtree empty left

: 오른쪽 또는 왼쪽 서브트리가 모두 공백인 트리 경사이진트리 : 오른쪽 또는 왼쪽 서브트리가 모두 공백인 트리 A A B B C C D D E E 오른쪽경사이진트리 왼쪽경사이진트리

이진트리의 성질 • i번째 레벨은 최대 2i개의 노드를 가질 수 있다. • 레벨이 0인 루트노드는 2개의 자식노드를 가진다. 따라서 레벨 1 노드에는 21, 즉 2개의 노드가 올 수 있다. • 각 레벨은 이전 레벨의 최대 노드 수보다 2배 많은 노드를 가질 수 있다. • 따라서 i번째 레벨에는 2i개의 노드가 존재할 수 있다.

이진 트리의 특성 보조정리 [최대 노드수] (1) 레벨 i에서의 최대 노드수 : 2i(i  0) (2) 깊이가 k인 이진 트리가 가질수 있는 최대 노드수 : 2k - 1(k  1) 보조정리 [단말노드 수와 차수가 2인 노드 수와의 상관관계] 공백이 아닌 모든 이진 트리 T에 대하여, n0 : 단말 노드수 n2 : 차수가 2인 노드 수 n0 = n2 + 1 ∵ n : 전체 노드수, B :전체 간선수(n1+2n2) n1: 차수가 1인 노드수 n=n0+ n1+ n2 n=B+1=n1 + 2n2 +1 n0 =n2 +1

이진트리 경사 이진 트리와 완전 이진 트리 # 트리는 모두 2진 트리로 표현 가능 # 완전이진트리 A B D E C F G H I level 1 2 3 4 (a) (b) # 트리는 모두 2진 트리로 표현 가능 # 완전이진트리 * 트리를 구성하고 있는 임의의 두 단말 노드의 레벨 차수가 1 이하 * 마지막 레벨을 제외한 모든 레벨은 존재할 수 있는 모든 노드를 가짐 * 왼쪽에서 오른쪽으로 채워지는 이진 트리

포화이진트리 포화 이진 트리(full binary tree) 깊이가 k이고 노드수가 2k-1 인 이진 트리 순차적 노드 번호를 붙인 깊이 4의 포화 이진 트리 1 2 4 8 9 5 10 11 3 7 12 13 14 15 level 0 level 1 level 2 level 3 depth 4

5. 이진 트리의 표현 연속 배열 저장법 포인터를 이용한 노드 표현

연속 배열 저장법 1차원의 배열에 이진 트리를 저장시킴 모든 이진 트리에 대해 사용할 수 있음 완전 이진 트리의 경우 낭비되는 공간이 전혀 없음 경사 이진 트리의 경우 낭비가 심함 이진 트리의 깊이가 k일 때 최대 2k-1개의 연속적인 공간이 필요 근노드부터 레벨 순으로 좌우 노드를 차례로 저장함

이진 트리의 배열 표현 1 A 1 1 A 3 A 2 3 B 2 3 B C 7 B C 7 C 5 6 4 4 7 15 D E D F G D (a) n=7 이진 트리 (b) n=15 이진 트리 (c) n=7 이진 트리 [1] [2] [3] [4] [5] [6] [7] [1] [2] [3] [4] [5] [6] [7] A B C D E A B C D E F G n=7인 (a)의 배열 n=7인 (c)의 배열 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] A B C D n=15인 (b) 배열

이진 트리가 1차원 배열 T에 저장된 경우 T[i]에 저장된 I번째 노드의 부모,왼쪽 및 오른쪽자식 노드 결정 n개의 노드로 구성된 완전이진 트리가 배열을 이용하여 표현 (i번째 노드의 부모와 자식노드) 부모노드(i) = if i≠1 i/2 if I =1 i번째 노드가 루트노드임 왼쪽 자식노드(i) = if 2i ≤ n , 2i if 2i > n , 왼쪽 자식노드 없음 오른쪽 자식노드(i) = if 2i +1 ≤ n , 2i +1 if 2i +1 > n , 오른쪽 자식노드 없음

포인트를 이용한 노드표현

링크 표현(연결 리스트) 노드 표현 left child right child data data LeftChild struct binary_tree_node{ struct binary_tree_node *lchild; char data; struct binary_tree_node *rchild; };

A B D E C F G H I (a) (b) A B C D E root H I G F

일반 트리를 이진 트리로 변환하는 방법 일반 트리보다는 기억장소의 효율성뿐만 아니라 노드의 가지(branch)를 얼마나 많이 갖게될지 알 수 없기 때문에 구성면에서 용이하지 않다는 점 때문에 이진 트리를 많이 이용 일반 트리를 이진 트리로 바꾼다는 것은 모든 노드들의 차수(degree)가 2로 제한될 수 있도록 만들어져야 한다는 것이다. (예) n개의 노드를 갖는 일반 트리의 차수를 k라 하자 * 일반 트리가 가질 수 있는 링크 필드의 수 : nk개 * null이 아닌 링크 필드의 수 : 전체 노드의 수 – 루트 수 = n-1 * null인 링크 필드의 수 = nk-(n-1) = n(k-1) + 1

(1) 각각의 모든 형제 노드(sibling node)들를 수평선으로 연결 (2) 부모노드에서 자식 노드로 연결된 가지 중 맨 좌측 가지만 제외하고 제거 (3) 왼쪽과 오른쪽 부트리를 구별하기 위하여 맨 좌측 가지를 중심으로 시계 방향으로 45도 회전 A A B C D B E C E F G H I J A F G D H B C D I J E F G H I J

이진 트리의 순회 완전한 순회는 노드의 선형 순서를 생성. 순회 방법 : LDR, LRD, DLR, DRL, RDL, RLD LDR (inorder) : infix DLR (preorder) : prefix LRD (postorder) : postfix note : "Data"의 위치 산술식의 이진트리 표현

순회 방법 I 중위 순회(inorder traversal) : LDR 알고리즘(순환함수에 의한) (1) 왼쪽 서브트리 방문 (2) 루트 노드를 방문 (3) 오른쪽 서브트리 방문 알고리즘(순환함수에 의한) void recu_inorder(current_node) struct binary_tree_node *current_node; { if(current_node != NULL){ recu_inorder(current_node->llink); printf(“%d”, current_ode->data); recu_inorder(current_node->rlink); }

알고리즘(반복함수에 의한) void rep_inorder(T) struct binary_tree_node *T; /* 이진트리의 루트노드를 가리키는 포인터*/ { struct binary_tree_node *current_node=T; /* 루트노드로 현재 포인터 초기화*/ while(1){ while(current_node != NULL){ push(current_node); /* 스택에 현재 노드의 주소 데이터 삽입 */ current_node = current_node->llink; /*current_node를 현재노드의 왼쪽노드 주소로 변경 */ } if(top != NULL){ /* 스택이 비어 있지 않은 경우 */ current_node = pop(); printf(“%d”, current_ode->data); current_node = current_node->rlink); else break;

순회 방법 II 전위 순회(preorder traversal) : DLR 알고리즘(순환함수에 의한) (1) 루트 노드를 방문 (2) 왼쪽 서브트리 방문 (3) 오른쪽 서브트리 방문 알고리즘(순환함수에 의한) void recu_preorder(current_node) struct binary_tree_node *current_node; { if(current_node != NULL){ printf(“%d”, current_ode->data); recu_preorder(current_node->llink); recu_preorder(current_node->rlink); }

알고리즘(반복함수에 의한) void rep_preorder(T) struct binary_tree_node *T; /* 이진트리의 루트노드를 가리키는 포인터*/ { struct binary_tree_node *current_node=T; /* 루트노드로 현재 포인터 초기화*/ while(1){ while(current_node != NULL){ printf(“%d”, current_node->data); if(current_node->rlink != NULL) push(current_node->rlink, ‘r’); /* 왼쪽 서브트리의 순회 후 방문 할 오른쪽 노드의 주소를 스택에 저장 */ current_node = current_node->llink; /*current_node를 현재노드의 왼쪽노드 주소로 변경 */ } if(top != NULL){ /* 스택이 비어 있지 않은 경우 */ current_node = pop(); printf(“%d”, current_ode->data); /* 오른쪽 노드들의 주소를 pop하여 데이터에 출력*/ else break;

순회 방법 III 후위 순회(postorder traversal) : LRD 알고리즘(순환함수에 의한) (1) 왼쪽 서브트리 방문 (2) 오른쪽 서브트리 방문 (3) 루트 노드를 방문 알고리즘(순환함수에 의한) void recu_postorder(current_node) struct binary_tree_node *current_node; { if(current_node != NULL){ recu_postorder(current_node->llink); recu_postorder(current_node->rlink); printf(“%d”, current_ode->data); }

알고리즘(반복함수에 의한) void rep_postorder(T) struct binary_tree_node *T; /* 이진트리의 루트노드를 가리키는 포인터*/ { struct binary_tree_node *current_node=T; /* 루트노드로 현재 포인터 초기화*/ while(1){ /* (1) */ while(current_node != NULL){ push(current_node, ‘l’); /* 왼쪽 노드임을 ‘l’로 표시하여 저장 */ if(current_node ->rlink != NULL) push(current_node, ‘r’); /* 왼쪽 서브트리의 순회 후 방문 할 오른쪽 노드의 주소를 스택에 오른쪽 노드임을 ‘r’로 표시하여 저장 current_node = current_node->llink); } else if(top != NULL){ /* 스택이 비어 있는 경우 */ current_node = pop(); if(right_node == ‘r’) break; /* 스택의 포인터 노드가 오른쪽 노드이면, 알고리즘 (1)에서 다시 시작한다 */ printf(“%d”, current_ode->data); else break;

중위 순회 : DBHEAJFCIG 전위 순회 : ABDEHCFJGI 후위 순회 : DHEBJFIGCA D A L R D D B

중위 순회 : A*B+C/D+E 전위 순회 : ++*AB/CDE 후위 순회 : AB*CD/+E+ 산술식을 이진 트리로 표현하여 순회 방법을 이용하여 순회 * 중위 순회 : 중위 표기법 * 전위 순회 : 전위표기법 * 후위 순회 : 후위 표기법 중위 순회 : A*B+C/D+E 전위 순회 : ++*AB/CDE 후위 순회 : AB*CD/+E+ + + E * / A B C D

이진트리의 순회알고리즘 void in_order(Node p) if (p!=null) in_order(p.lnext); System.out.println(p.key+","); in_order(p.rnext); void pre_order(Node p) System.out.println(p.key+","_; pre_order(p.lnext); pre_order(p.rnext); void post_order(Node p)

스레드 이진 트리 연결 리스트 표현 이진 트리의 문제점 스레드 이진 트리(thread binary tree) 실제로 사용하는 링크수보다 사용하지 않는 널(null)링크가 더 많음 n개의 노드를 가진 이진 트리의 총 링크수: 2n개 실제 사용되는 링크수: n-1개 널 링크수: n+1개 스레드 이진 트리(thread binary tree) 널 링크들을 낭비하지 않고 스레드(thread) 저장해 활용 스레드: 트리의 어떤 다른 노드에 대한 포인터 트리를 순회하는 정보로 활용 스레드 이진 트리 생성 방법 노드 p의 Rchild가 널이면: 중위 순회에서 중위 후속자에 대한 포인터 저장 노드 p의 Lchild가 널이면: 중위 순회에서 중위 선행자에 대한 포인터 저장

만일 ptr -> llink == NULL이면, ptr -> llink는 순회순서에 따라 선행노드를 가리키는 왼쪽 스레드가 된다. 만일 ptr -> rlink == NULL 이면, ptr -> rlink는 순회순서에 따라 선행노드를 가리키는 오른쪽 스레드가 된다 + + E * / A B C D

스레드이진트리표현 LeftThread LeftChild data RightChild RightThread TRUE FALSE 스레드 이진 트리의 표현 LeftThread == F : LeftChild  pointer == T : LeftChild  thread RightThread == F : RightChild  pointer == T : RightChild  thread 공백 이진 트리 : 헤드 노드 LeftThread LeftChild data RightChild RightThread TRUE FALSE 스레드 이진 트리 노드 struct thread_node{ char leftthread; struct thread_node *llink; char data; struct thread_node *rlink; char rightthread; };

이진 트리의 노드를 연결리스트로 표현 (중위 순회) A B C D E F G H I

스레드 이진 트리의 표현 주의 : 헤드 노드의 왼쪽 서브트리 f - A C B D t E F G I H 스레드 이진 트리의 표현 주의 : 헤드 노드의 왼쪽 서브트리 f - A C B D t E F G I H f = FALSE; t = TRUE root

알고리즘(스레드 이진 트리의 중위 순회) { struct thread_node *current_node; current_node = T; while(1){ current_node = insucc(current_node); if(current_node == T) break; printf(“%3c”, current_node->data); } struct thread_node *insucc(tree) struct thread_node *tree; struct thread_node *temp; temp = tree -> rchild; if(!tree ->right_thread ) while((!tree ->left_thread ) temp = temp -> left_child; return temp;