Microsoft PowerPoint - 자료구조2008Chap07

Size: px

Start display at page:

Download "Microsoft PowerPoint - 자료구조2008Chap07"

재연 정
6 years ago
Views:

1 제 7 장트리 7.1 트리의정의 1 Tree 비선형구조, 다차원적구조 원소마다다음에여러개의원소가존재 하나이상의노드로구성된유한집합 정의1 : 루트 (root) 라는특별한노드를가지는사이클이존재치않는그래프 (acyclic graph) 정의 2 : 하나이상의노드로구성된유한집합 루트 (root) 라는특별한노드존재 나머지노드들은다시각각의트리이면서교차하지않는분리집합 (disjoint set) T 1, T 2,, T m (m 0) 으로분할 (partition) 분할된이들은루트의부트리 (subtree) 라고한다.

2 7.1 트리의정의 (2) 2 J J K L M K L M 그림 7-1 트리의구조 그림 7-2 트리가아닌구조 트리구조와가족관계도 3 할아버지할머니 큰아버지큰어머니 아버지어머니 고모 사촌형 나아내동생 아들 그림 7.1 가족관계도

7.2 트리에사용되는용어들 (1) 4 진짜나무와자료구조의트리를비교하면나무를거꾸로세워놓은격이다.

에서,, 등 leaf( 잎 ) 단말노드 (Leaf Node) : 차수가 0 인노드 or 하부에가지가없는노드 x) Tree T 에서 K, L,,,,, M 등 비단말노드 (Non-Terminal Node) :

3 7.2 트리에사용되는용어들 (1) 4 진짜나무와자료구조의트리를비교하면나무를거꾸로세워놓은격이다. root( 뿌리 ) branch( 가지 ) 루트 (Root) : 트리의노드중하나, 가장상위레벨 x) Tree T 에서 Level 1 노드 (Node) : 정보가저장되는곳, 자료구조의원소 x) Tree T 에서,, 등 leaf( 잎 ) 단말노드 (Leaf Node) : 차수가 0 인노드 or 하부에가지가없는노드 x) Tree T 에서 K, L,,,,, M 등 비단말노드 (Non-Terminal Node) : 차수가 0 이아닌노드 x) Tree T 에서,,,,, J 등 7.2 트리에사용되는용어들 (2) 5 부트리 (Subtree) : 루트와루트에연결된가지들을제거한다면한개의큰트리구조는몇개의작은트리구조로나뉨. 이런트리들을부트리라고함. Level 1 x) Tree T 에서 T 1, T 2, T 3 노드, 노드, 노드 는 T 1, T 2, T 3 의루트 Level 2 차수 (egree) : 각노드를루트노드로하는부트리의수 or 각노드가지닌아래쪽가지의숫자차수 = 노드의차수 x) Tree T 에서노드 의차수는 3, 노드 의차수는 1, 노드 의차수는 0 트리의차수 : 각노드의차수중최대치 x) Tree T 에서트리의차수는 3 인트리 J K L M Subtree T 2 Subtree T 1 Subtree T 3 Tree T Level 3 Level 4

4 7.2 트리에사용되는용어들 (3) 6 자식노드 (hild Node) : 임의의노드에연결된바로밑레벨의노드, 이임의의노드는자식노드쪽에서보다면부모노드 x) Tree T에서 와 는 의자식노드 형제노드 (Sibling Node) : 동일한부모노드를갖는노드 x) Tree T 에서 와, 와 와 J 에서의관계 조상노드 (ncestor Node) : 루트노드에서부터임의노드에까지 path( 경로 ) 를형성하는노드들의집합 x) Tree T 에서 M 의조상노드는,, J 부모노드 (Parent Node) : 임의노드가연결된레벨의높은노드, 자신을파생시킨노드 x) Tree T 에서, 에대하여 는부모노드 숲 (orest) : 분리된트리들의집합. Tree T 에서루트를삭제한다면 3 개의부트리로이루어진 forest. 후손노드 (escendant Node) : 임의의노드를루트로하는부트리의모든노드의집합 x) Tree T 에서노드 의후손은,, J, M J 레벨 (Level) : 루트를최상위레벨인 1 로하고, 레벨 L 인노드의자식노드레벨은 L+1. x) Tree T 에서노드 의자식노드레벨은 3 K L M 트리의레벨 7 Level 1 Level 2 J Level 3 K L M Level 4 그림 7-6 트리의레벨

5 7.3 트리를표현하는법 8 표현하는방법계층구조로표현하는법 루트노드로부터시작해서노드와가지들로표현 가장일반적인표현중첩된괄호 (nested parenthesis) 집합으로표현 (nested set) 들여쓰기 (indentation) 7.3 트리를표현하는법 (2) 9 ( ( ( (K L) ) () ( J (M)))) (1) 괄호로표현하는방법 K L J M... K. L J. M. (2) 집합으로표현하는방법 (3) 들여쓰기로표현하는방법 그림 7.9 트리를표현하는여러가지방법들

6 7.3 트리를표현하는법 (3) 10 컴퓨터에서트리표현 2 가지 배열에의한방법 연결리스트에의한방법 7.4 이진트리 ( 정의 ) 11 inary Tree 정의 노드의유한집합 공집합이거나 루트와왼쪽부트리및오른쪽부트리라고불리는 2개의서로분리된이진트리로구성 모든차수가 2를넘지않는특수한트리, 자식노드의순서를구별 오른쪽부트리가공집합인이진트리 왼쪽부트리가공집합인이진트리 서로다른이진트리

7 7.4.1 이진트리의종류 (1) 12 포화이진트리 (ull inary Tree) 모든레벨의노드가꽉차있는상태의트리. 레벨이 k일때 2 k 1 개의노드를갖는다. 레벨이 3인포화이진트리 레벨 3에서는 = 2 2 = 4개의노드를 레벨 2에서는 = 2 1 = 2개의노드를가진다. 이진트리노드의개수 13 레벨 해당레벨의노드개수 전체노드개수 k 2 k 1 2 k -1

8 이진트리의성질 14 inary Tree의성질이진트리의레벨 k에서의최대노드의수는 2 k-1 이다. 루트는레벨 1, 최대노드수는 =2 0 =1이다. 레벨 2에서의최대노드수는 2 1 =2개, 레벨 3에서는 4개 높이가 k 인이진트리의최대노드의수는 2 k 1 이다. 이진트리에서리프노드의수를 n, 차수가 2 인노드의수를 m 이라할때 n=m+1 은항상성립 이진트리의종류 (2) 15 완전이진트리 (omplete inary Tree) 포화이진트리중에서마지막레벨 (leaf level) 에서의노드는꽉차있지않고왼쪽에서부터어느정도까지는차례대로채워져있는상태의트리. 높이가 k일때 1부터 k-1까지의노드는모두차있고 k레벨은왼쪽부터차례로차있는이진트리모든포화이진트리는완전이진트리라고할수있다. but, 그역은성립하지않는다. J K

9 7.4.1 이진트리의종류 (3) 16 사향이진트리 (Skewed inary Tree) 분명이진트리의특성을가지고있으나, 공교롭게한쪽의모든노드가공백인상태. 단일연결리스트와같은모양, 검색시간도 O(n) 으로같다. 왼쪽사향트리 (left skewed binary tree) 오른쪽링크가 null, 왼쪽방향으로기울어진모양 오른쪽사향트리 (right skewed binary tree) 왼쪽링크가 null, 오른쪽방향으로기울어진모양 이진트리의표현 17 배열에의한표현 어떠한이진트리도배열로표현, 배열의임의노드를쉽게 access 가능 단점 이진트리를배열로표현하면공간의낭비심하다 but, 포화트리 or 완전트리일경우에는낭비가없다. k레벨의트리는 2 k -1개의기억공간이필요 사향트리의경우는이중에서사용되는것은 k개뿐 (worst case) 배열자체가가진단점 노드의삽입과삭제시배열의원소들이이동되어야만한다.

10 배열을표현한포화이진트리 J K J K 배열을표현한완전이진트리 N

11 배열을표현한일반이진트리 20 N 배열을이용한구현 (2) 21 n개의노드로구성된완전이진트리의배열표현시특성 i번노드의부모의위치는 floor((i-1)/2) i번째노드의왼쪽자식노드의위치는 2i+1 i번째노드의오른쪽자식노드의위치는 2(i+1)

12 연결리스트로구현 (1) 22 Linked List 로표현 하나는데이터필드, 두개는포인터필드 포인터필드는각각왼쪽자식노드와오른쪽자식노드를가리킨다. struct tnode { char data; struct tnode *left, *right; ; typedef struct tnode TNO; left data right left data right 연결리스트로포화이진트리 23 포화이진트리를연결리스트로표현

13 연결리스트로완전이진트리 24 완전이진트리를연결리스트로표현 J K J K 연결리스트로사향이진트리 25 사향이진트리를연결리스트로표현

14 7.5 일반트리를이진트리로전환 26 일반트리를이진트리로변환 형제노드들을수평으로연결 부모노드에서자식노드로연결된가지들중맨왼쪽의가지만을제외하고는연결을끊는다이진트리모양으로재구성숲 (forest) 를이진트리로변환 각루트노드를수평으로연결 각트리의형제노드들을수평으로연결 부모노드에서자식노드로연결된가지들중에서맨왼쪽의가지만을제외하고는연결을끊는다이진트리모양으로재구성 7.5 일반트리를이진트리로전환 (2) 27 일반트리를이진트리로변환하기 J J K L M K L M 일반트리 Sibling 들을연결하고, 부모노드와의연결을끊는다

15 7.5 일반트리를이진트리로전환 (2) 28 일반트리를이진트리로변환하기 J J K L M N K L M N 일반트리 형제노드들을연결하고, 부모노드와의연결을끊는다 7.5 일반트리를이진트리로전환 (3) 29 K L M J N 이진트리로재구성

16 일반트리를이진트리로전환 (4) 숲 (forest) 을이진트리로변환하기 숲 (forest) Root 와 Sibling 들을연결하고, 부모노드와의연결을끊는다 N O J L K M N O J L K M 일반트리를이진트리로전환 (5) 숲 (forest) 을이진트리로변환하기 (2) J K N L M O N O J L K M 이진트리로재구성

17 7.6 이진트리운행 32 Tree Traverse 트리의각노드를한번씩방문한다는것순서적으로트리를방문해서리스트로만든다는것 2 차원적비선형구조를 1 차원적선형구조로만들수있음을뜻함. 루트노드를어떤순서로방문하는가에따른 3가지운행방법전위운행법 (preorder traversal) 중위운행법 (inorder traversal) 후위운행법 (postorder traversal) 운행방법의수 (3!) 순서고려시운행방법 (preorder) -- (inorder) --(postorder) 7.6 (1) 전위운행법 33 Preorder traversal 특정한노드에서자기자신이위치한노드 ( 루트노드 ) 를방문왼쪽서브트리를모두방문오른쪽서브트리들을방문 모든노드에재귀적으로적용, 모든노드를한번씩방문 void preorder(tno *p) { if(p!= NULL) { printf( %c, p->data); preorder(p->left); preorder(p->right); ; 1 2 J K 3 4 L M N O

18 7.6 (2) 중위운행법 34 norder traversal 특정한노드에서자신의왼쪽서브트리를모두방문자기자신이위치한노드 ( 루트노드 ) 를방문오른쪽서브트리들을방문 모든노드에재귀적으로적용, 모든노드를한번씩방문 4 void inorder(tno *p) { if(p!= NULL) { inorder(p->left); printf( %c, p->data); inorder(p->right); ; J K L M N O 7.6 (3) 후위운행법 35 Postorder traversal 특정한노드에서자신의왼쪽서브트리를모두방문오른쪽서브트리들방문자기자신이위치한노드 ( 루트노드 ) 를방문 모든노드에재귀적으로적용, 모든노드를한번씩방문 void postorder(tno *p) { if(p!= NULL) { postorder(p->left); postorder(p->right); printf( %c, p->data); ; J K L M N O

19 7.6 (4) 레벨운행법 36 Levelorder traversal 전위, 중위, 후위운행법과는차별되는운행법레벨순위에따라운행하는방법루트로시작해서각레벨을순차적으로방문 각레벨에서는왼쪽에서오른쪽으로순차적으로방문 전위, 중위, 후위운행법이 Stack 형태이용 레벨운행법은 Queue 형태이용 그래프에서는너비우선검색 (breadth first search) 와비슷하게운행되어진다. 7.6 (5) 레벨운행법 37 예제 inorder traverse: */-*+ preorder traverse: */*-+ postorder traverse: *-/+* * / + * -

20 중위법을이용해서트리그리기 e -2 c f -3 b d g -4 a h 이진검색트리 (ST) 39 inary Search Tree의특성이진트리중모든노드의값이다르다임의의노드의키값>왼쪽서브트리의노드들의키값임의의노드의키값<오른쪽서브트리의노드들의키값모든노드에대하여재귀적으로적용

21 이진검색트리 40 그림 7.30 이진검색트리 그림 7.30 이진검색트리 노드 를찾아가는과정 이진검색트리의예

22 ST 소스코드 ( 비재귀적 ) 42 /*************************************************** /* ST search function /***************************************************/ TNO *search(tno *p, char key) { TNO *temp; temp = p; while( temp!= NULL){ if(temp->data == key) return(temp); else if(temp->data > key) temp = temp->left; else temp = temp->right; return(null); ST 소스코드 ( 재귀적 ) 43 /*************************************************** /* ST search function /***************************************************/ TNO search(tno ptr, data key){ if(ptr == NULL)exit(0) // 검색실패 if(key == ptr->data)return ptr; // 검색성공 if(key < ptr->data) return search(ptr->left, key); else return search(ptr->right, key);

23 7.8 노드삽입 (1) 44 inary Search Tree 의노드삽입 트리를탐색, 동일한키값을갖는원소가트리내에있는지확인탐색이실패하면탐색이실패한끝지점에해당원소삽입 노드 9 삽입전 10 노드 9 삽입후 루트원소 10 > 노드 9 2. 노드 9 > 왼쪽서브트리의루트노드 노드 9 > 오른쪽자식노드인 7, 오른쪽서브트리로이동 노드 7 은터미널노드, 노드 7 의오른쪽자식노드에노드 9 를삽입 7.8 노드삽입소스코드 45 // 트리 1.c -- inary Search Tree 삽입 #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <conio.h> struct tnode{ char data; struct tnode *left, *right; ; typedef struct tnode TNO; /*************************************************** /* insert /***************************************************/ TNO *insert(tno *p, char data) { TNO *temp1,*temp2; if(p == NULL) { p = (TNO *) malloc(sizeof(tno)); // 루트생성 if(p == NULL) { printf("memory rror! n"); exit(0); p->data = data; p->left = NULL; p->right = NULL; else{ temp1 = p; while(temp1!= NULL){ temp2 = temp1; if( temp1 ->data > data) temp1 = temp1->left; else temp1 = temp1->right;

24 7.8 노드삽입소스코드 (2) 46 if( temp2->data > data) { temp2->left =(TNO*)malloc(sizeof(TNO)); // 왼쪽자식생성 temp2 = temp2->left; if(temp2 == NULL) { printf("memory rror! n"); exit(0); temp2->data = data; temp2->left=temp2->right = NULL; else { temp2->right=(tno*)malloc(sizeof(tno)); // 오른쪽자식생성 temp2 = temp2->right; if(temp2 == NULL){ printf("memory rror! n"); exit(0); temp2->data = data; temp2->left = NULL; temp2->right = NULL; return(p); 7.8 노드삽입소스코드 (3) 47 /*************************************************** /*************************************************** /* ST search function /* inorder를변형하여괄호로트리를표현한다. /***************************************************/ /***************************************************/ TNO *search(tno *p, char key) { TNO *temp; temp = p; while( temp!= NULL){ if(temp->data == key) return(temp); else if(temp->data > key) temp = temp->left; else temp = temp->right; return(null); void inorder1(tno *p) { if(p!= NULL){ printf(" ("); inorder1(p->left); printf("%c",p->data); inorder1(p->right); printf(") ");

25 7.8 노드삽입소스코드 (4) 48 /*************************************************** /* ST search function /***************************************************/ TNO *search(tno *p, char key) { TNO *temp; temp = p; while( temp!= NULL){ if(temp->data == key) return(temp); else if(temp->data > key) temp = temp->left; else temp = temp->right; return(null); /*************************************************** /* main /***************************************************/ void main() { TNO *root = NULL; char ch; int n; printf("nter the number of nodes n"); scanf("%d",&n); while (n > 0) { printf("nter the data value n"); ch = getche(); printf(" n"); root = insert(root,ch); n--; printf(" n inorder : "); inorder(root); printf(" n inorder : "); inorder1(root); printf(" n"); 7.4 노드삽입실행결과 49 교과서예제문제를이용하여실행시킨결과화면

26 7.9 노드삭제 (1) 50 /* 자식노드의개수가 0 인경우 */ if(current->left == NULL && current->right == NULL){ if(parent->left == current) parent->left = NULL ; else parent->right = NULL; free(current); 그림 7.34 자식노드의개수가 0 이며부모노드의왼쪽자식인노드의삭제 그림 7.34 자식노드의개수가 0 이며부모노드의왼쪽자식인노드의삭제 7.9 노드삭제 (2) 51 /* 왼쪽자식 1개만있는경우 */ if(current->left!= NULL && current->right == NULL){ if(parent->left == current) // 부모의왼쪽자식 (1) 번경우 parent->left = current->left ; else // 부모의오른쪽자식 (2) 번경우 parent->right = current->left; current->left = NULL; free(current); 그림 7.35 왼쪽자식 1 개만있고부모노드의왼쪽자식인노드의삭제 그림 7.36 왼쪽자식 1 개만있고부모노드의오른쪽자식인노드의삭제

27 7.9 노드삭제 (3) 52 /* 오른쪽자식 1개만있는경우 */ if(current->left == NULL && current->right!= NULL){ if(parent->left == current) // 부모의왼쪽자식 (3) 번경우 parent->left = current->right; else // 부모의오른쪽자식 (4) 번경우 parent->right = current->right; current->right = NULL; free(current); 그림 7.37 오른쪽자식 1 개만있고부모노드의왼쪽자식인노드삭제 그림 7.38 오른쪽자식 1 개만있고부모노드의오른쪽자식인노드삭제 7.9 노드삭제 (4) 53 그림 7.39 자식노드의개수가 2 이며부모노드의왼쪽자식인노드를삭제 그림 7.39 자식노드의개수가 2 이며부모노드의왼쪽자식인노드를삭제

28 7.9 노드삭제 (5) 54 그림 7.40 자식노드의개수가 2 이며부모노드의오른쪽자식인노드를삭제 그림 7.40 자식노드의개수가 2 이며부모노드의오른쪽자식인노드를삭제 삭제실행화면 55

29 노드삭제 ( 치환에의한 ) 56 그림 7.41 자식노드의개수가 2 인경우 (2) 그림 7.41 자식노드의개수가 2 인경우 노드삭제프로그램 57 Modified Version Tree 가공백이거나 Key 가존재하지않으면 NULL 을반환하고, 그렇지않으면제거될노드와부모노드에대한포인터를반환한다. tree_pointer modified_search1(tree_pointer ptr, tree_pointer parent, int key) { while(ptr) { if(key == ptr->data) return ptr; parent = ptr; if(key < ptr->data) ptr = ptr->left_child; else ptr = ptr->right_child; return NULL;

30 노드삭제프로그램 58 void delete_node(tree_pointer *node, int key) { tree_pointer parent, child, substitute, temp; int x; temp = modified_search1(node, parent, key); /* 제거되는노드의부모노드에대한포인터반환 */ if(!temp) { fprintf(stderr, key is not in the tree n ); exit(1); if((temp->left_child == NULL) && (temp->right_child == NULL)) { /* ase 1 */ if(parent->left_child == temp) parent->left_child = NULL; else parent->right_child = NULL; free(temp); 노드삭제프로그램 59 else { if((temp->left_child == NULL) (temp->right_child == NULL)) { /* case 2 */ child = findchild(node, temp); if(parent->left_child == temp) parent->left_child = child; else parent->right_child = child; free(temp); else { /* ase 3-2 */ substitute = insucc(node, temp); x = temp->data; temp->data = substitute->data; substitute->data = x; delete_node(temp->right_child, substitute->data);

31 7.10 스레드이진트리 60 Thread inary Tree 널포인터를트리의운행에이용하는것 n개의노드를가진이진트리의경우왼쪽링크와오른쪽링크를가지므로총 2n개의링크가존재 트리의특성상이중 n-1개의링크만필요, 나머지 n+1개의링크는널포인터가된다. 스레드구성을위한규칙 임의의노드의널포인터가왼쪽포인터이면그노드이전에운행할노드의주소를지적하도록그포인터값을설정 임의의노드의널포인터가오른쪽포인터이면그노드이후에운행할노드의주소를지적하도록그포인터값을설정 7.10 스레드이진트리 (2) 61 중위운행법을위해서스레드된이진트리 중위운행법을위해서스레드된이진트리

32 7.10 스레드이진트리 (3) 62 전위운행법을위해서스레드된이진트리 그림 7.43 전위운행법을위해서스레드된이진트리 7.10 스레드이진트리 (4) 63 후위운행법을위해서스레드된이진트리 그림 7.44 후위운행법을위해서스레드된이진트리

33 7.10 스레드이진트리 (5) 64 일반포인터와스레드포인터의구별 left_thread 와 right_thread 라는변수를선언하면구별가능 left_thread와 right_thread가참일경우스레드포인터 left_thread와 right_thread가거짓일경우일반포인터 left_threa d left_child ata right_child 위의노드구조 언어로표현 typedef struct thread_tree *thread_pointer typedef struct thread_tree { int left_thread; thread_pointer left_child; int data; thread_pointer right_child; int right_thread; ; right_thre ad 7.10 스레드이진트리 (6) 65 그림 7.45 중위운행스레드이진트리의포인터 그림 7.45 중위운행스레드이진트리의포인터

34 7.10 스레드이진트리 (7) 66 어떤노드 ptr 에서 ptr->right_thread = TRU 이면 ptr 의 inorder successor 는 ptr->right_child 가된다. 만일어떤노드 ptr 에서 ptr->right_thread = LS 이면 ptr 의 inorder successor 는 ptr 의오른쪽자식에서시작하여왼쪽자식링크를따라 left_thread = TRU 인노드에도달할때까지찾으면된다 스레드이진트리 (8) 67 thread_pointer insucc(thread_pointer tree) { thread_pointer temp; temp = tree->right_child; if(!tree->right_thread) while(!temp->left_thread) temp = temp->left_child; return temp; void thread_inorder(thread_pointer tree) { thread_pointer temp = tree; for(;;) { temp = insucc(temp); if(temp == tree) break; printf( %c, temp->data);

35 7.10 스레드이진트리의노드삽입 68 Threaded binary tree의임의의노드에새로운오른쪽자식노드의삽입 ase 1: parent의오른쪽 sub tree가공백인경우 parent->right_thread를 LS로변경한다. child->left_child와 child->right_child를 TRU로치환한다. child->left_child가 parent를가리키게한다. child->right_child를 parent->right_child로치환한다. parent->right_child가 child를가리키게한다. ase 2: parent 의오른쪽 Sub tree 가공백이아닌경우 child의중위선행자는parent가된다. child는 parent의전중위후속자였던노드의중위선행자가된다 스레드이진트리의노드삽입 69 root root parent parent child child [ 삽입전 ] [ 삽입후 ]

36 7.10 스레드이진트리의노드삽입 70 root root parent parent child X [ 삽입전 ] child X [ 삽입후 ] 7.10 스레드이진트리의노드삽입 71 void insert_right(thread_pointer parent, thread_pointer child) { thread_pointer temp; child->right_child = parent->right_child; child->right_thread = parent->right_thread; child->left_child = parent; child->left_thread = TRU; parent->right_child = child; parent->right_thread = LS; if(!child->right_thread) { temp = insucc(child); temp->left_child = child;

chap 5: Trees

chap 5: Trees 5. Threaded Binary Tree 기본개념 n 개의노드를갖는이진트리에는 2n 개의링크가존재 2n 개의링크중에 n + 1 개의링크값은 null Null 링크를다른노드에대한포인터로대체 Threads Thread 의이용 ptr left_child = NULL 일경우, ptr left_child 를 ptr 의 inorder predecessor 를가리키도록변경