[자료구조] 트리

트리의 개념

트리의 정의

• 검색의 편리함
• 논리적 계층
• 계급적 특성

트리의 표현방법

트리의 구성

노드 : 트리의 항목/트리 에 저장되는 데이터의 묶음

부모노드 - 자식노드 : 상하 계층구조가 있고 직접적으로 연결된 노드들로서 상위계층의 부모노드와 하위계층의 자식노드를 의미함

• 루트노드

트리의 최상위 노드 (부모가 없는 노드)

• 서브트리

부모노드를 삭제하면 생기는 트리들

• 잎 노드

트리의 맨 끝(바닥)에 있으면서, 자신의 서브트리를 갖지 않는 노드

진입 / 진출 차수

• 루트노드 : 진입차수 = 0
• 루트를 제외한 모든 노드의 진입차수 = 1
• 잎노드 : 진출차수 = 0

내부 노드와 형제

• 내부 노드 : 루트, 잎 노드가 아닌 나머지 노드
• 형제 : 같은 부모를 갖는 노드들

트리의 레벨

• 노드의 레벨 : 루트로부터 그 노드까지 이어진 선(경로)의 길이
• 트리의 깊이 : 트리의 레벨에서 가장 큰 값에 1을 더한 것

추상 자료형

트리의 추상자료형

• 트리 객체의 정의 : 루트 노드를 갖는 유한 리스트
• 연산

연산 내용

Tree Create()	트리를 생성하고 루트 노드를 가리키는 포인터를 반환
Destroy(Tree)	더 이상 사용하지 않는 트리의 기억 장소를 시스템에 반환한다.
Tree Copy_Tree	트리를 복사하고 새로 생성한 트리의 루트 노드를 가리키는 포인터를 반환한다.
Insert(n)	트리에 노드n을 삽입한다.
Delete()	트리에서 노드를 삭제한다. 보통 재구성 단계를 포함한다.
Search()	트리에서 특정 키값을 갖는 노드를 찾는다 찾으면 true 아니면 false
Traverse()	트리를 순회하고 방문 순서대로 값을 반환한다.
Root()	루트 노드 값을 반환한다.
Parent(n)	노드 n의 부모(값 혹은 포인터)를 반환. n이 루트이면 오류를 반환한다.
Children()	노드 n의 자식(값 혹은 포인터)를 반환. n이 앞이면 오류를 반환한다.
IsRoot(n)	노드 n이 루트이면 true 아니면 false 를 반환
IsInternal(n)	노드 n이 내부 노드면 true 아니면 false 를 반환
IsLeaf(n)	노드 n이 잎이면 true 아니면 false 를 반환
IsEmpty()	트리가 비었으면 true 아니면 false 를 반환
replace(n,m)	노드 n을 노드 m으로 바꾼다.

이진 트리

이진트리의 정의

• 모든 노드의 차수가 2 이하인 트리
• 수학적으로 이진 트리의 구성에 관한 이론을 정리하기 쉽고, 컴퓨터 내부에서 구현하기도 효율적임
• 모든 노드가 2개 이하의 자식 노드를 가지므로 일반성을 잃지 않고 “오른쪽”, “왼쪽” 이라는 방향 개념을 부여할 수 있음
• 오른쪽 노드와 왼쪽 노드의 개념적 접근(의미적 관계)도 있음

가득찬 이진 트리(perfect binary tree) | 포화 이진트리

• 이진트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리

완전 이진트리(complete binary tree)

• 높이가 k인 이진 트리가 0 레벨 부터 k-2 레벨 까지 다 채우고 마지막 k-1 레벨에서 왼쪽 부터 오른쪽으로 노드들이 차례로 채워진 이진 트리

배열을 이용한 이진트리의 구현

• 트리가 완전 이진트리 또는 가득 찬 이진 트리인 경우 낭비되는 공간이 없어 효율적임.
• 트리가 깊어질수록 기억장소 낭비가 2의 거듭제곱에 비례하며 낭비가 심해짐.

포인터를 이용한 이진 트리의 구현

typedef struct node {
	struct node *left;
	char data;
	struct node *right;
}node;

이진 트리 연산

이진 트리의 순회

• 이진 트리의 각 노드를 (빠짐없이 그리고 중복없이) 한 번씩 방문하는 것

이진트리의 전위 순회

• 루트노드 - 왼쪽 자식노드(왼쪽 서브트리) - 오른쪽 자식노드(오른쪽 서브트리)

void preorder(node* root){
if(root != NULL){
		printf("%c",root -> data);
		preorder(root -> left);
		preorder(root -> right);
	}
};

이진트리의 후위 순회

• 왼쪽자식노드 - 오른쪽 자식노드 - 루트노드

void preorder(node* root){
if(root != NULL){
		preorder(root -> left);
		preorder(root -> right);
		printf("%c",root -> data);
	}
};

이진트리의 중위 순회

• 왼쪽자식노드- 루트 노드 - 오른쪽자식노드

void preorder(node* root){
if(root != NULL){
		preorder(root -> left);
		printf("%c",root -> data);
		preorder(root -> right);
	}
};

이진트리의 생성 / 삽입 / 삭제

• 일반적인 이진 트리를 생성하는 것은 연결 리스트 연산을 사용함
• 첫 노드를 생성하면 루트 노드가 되고, 새로운 노드를 추가하려면 연결 리스트의 삽입 연산을 사용함 노드를 삭제할 때, 삭제하려는 노드가 잎 노드인 경우는 해당 노드를 가리키는 포인터를 NULL로 지정하면 됨
• 잎 노드가 아닌 경우에는 삭제하려는 노드의 자식 노드에 대한 처리를 추가로 해주어야 함

일반트리를 이진트리로 변환

이진트리로 변환 방법

• 일반 트리에 대하여 각 노드의 형제들을 연결
• 각 노드에 대하여 가장 왼쪽 링크만 남기고 모두 제거
• 루트 노드는 반드시 왼쪽 자식 노드 하나만 갖도록 함