1. 트리
•
논리적 계층이 있는 구조이며, 트리를 구성하는 항목을 노드(node) 혹은 점(vertex)이라고함
•
특징
◦
검색의 편리함
◦
논리적 계층
◦
계급적 특성
2. 용어와 논리적 표현 방법
2.1. 트리의 구성
•
노드 - 트리의 항목/트리에 저장되는 데이터의 묶음
•
부모 노드 - 자식 노드
◦
상하 계층 구조가 존재하고 서로 직접적으로 연결된 노드
◦
상위 계층의 부모 노드와 하위 계층의 자식 노드
•
루트 노드
◦
트리의 최상위 노드 (부모가 없는 노드)
•
서브트리
◦
부모 노드를 삭제하면 생기는 트리들
•
리프(잎) 노드
◦
트리의 맨 끝(바닥)에 있으며 자신의 서브 트리를 갖지 않느 노드
2.2. 진입/진출 차수
•
루트 노드의 진입차수 : 0
•
루트를 제외한 모든 노드의 진입 차수: 1
•
리프 노드의 진출 차수: 0
2.3. 트리의 레벨
•
노드의 레벨
◦
루트로부터 그 노드까지 이어진 경로(선, 간선)의 길이
3. 이진 트리
3.1. 정의
•
모든 노드의 차수가 2 이하인 트리
•
수학적으로 이진트리의 구성에 관한 이론을 정리하기 쉬움
•
컴퓨터 내부에서 구현하기도 효율적
•
모든 노드가 2개 이하의 자식 노드를 가지므로 일반성을 잃지 않음
•
오른쪽, 왼쪽이라는 방향 개념을 부여할 수 있음
◦
오른쪽 노드, 왼쪽 노드의 개념적 접근도 가능
3.2. 포화 이진 트리
•
이진 트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리
3.3. 완전 이진 트리
•
높이가 k인 이진트리가 0레벨 부터 k-2레벨까지 다 채우고, 마지막 k-1레벨에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 이진 트리
4. 이진 트리의 구현
4.1. 배열을 이용한 이진 트리의 구현
•
트리가 완전 이진 트리 또는 포화 이진 트리인 경우 낭비되는 공간이 없어 효율적임
•
그러나 완전 이진 트리나 포화 이진 트리가 아닌 경우 공간이 비효율적으로 쓰임
◦
트리가 깊어질수록 기억저장소 낭비가 2의 거듭제곱에 비례하며 낭비가 심해짐
4.2. 포인터를 이용한 이진트리의 구현
struct node {
struct node *left;
struct node *right;
int info;
}
C
복사
5. 이진 트리 연산
5.1. 이진 트리의 순회
•
이진트리의 각 노드를 (빠짐없이 그리고 중복없이) 한번씩 방문 하는 것
5.2. 전위 순회 (PLR)
•
루트노드(P) → 왼쪽 자식 노드(L) → 오른쪽 자식 노드(R)
•
J → A → M → aM → V → P → C → Pi → Sh → Sc → E → N
struct node *nodeptr;
void preorder(struct node *tree_ptr){
if(tree_ptr) {
printf("%d", tree_ptr->info);
preorder(tree_ptr->left);
preorder(tree_ptr->right);
}
}
C
복사
5.3. 후위 순회 (LRP)
•
왼쪽 자식 노드(L) → 오른쪽 자식 노드(R) → 루트 노드(P)
struct node *nodeptr;
void preorder(struct node *tree_ptr){
if(tree_ptr) {
preorder(tree_ptr->left);
preorder(tree_ptr->right);
printf("%d", tree_ptr->info);
}
}
C
복사
5.3. 중위 순회(LPR)
•
왼쪽 자식 노드(L) → 루트 노드(P) → 오른쪽 자식 노드(R)
struct node *nodeptr;
void preorder(struct node *tree_ptr){
if(tree_ptr) {
preorder(tree_ptr->left);
printf("%d", tree_ptr->info);
preorder(tree_ptr->right);
}
}
C
복사
5.3. 이진 트리의 생성/삽입/삭제
•
일반적으로 이진 트리를 생성하는 것은 연결 리스트 연산을 사용함
•
첫 노드를 생성하면 루트 노트가 되고, 새로운 노드를 추가하려면 연결리스트의 삽입 연산을 사용함
5.4. 이진 트리의 노드 개수 count 연산
•
이진 트리의 노드 개수 세는 연산
int get_node_count(nodeptr* root){
if (root===null) return 0;
int result = 1;
result = get_node_count((nodeptr)*root->left)
+
get_node_count((nodeptr*)root->right);
return result;
}
C
복사
•
이진 트리의 리프 노드 개수 세는 연산
int get_node_count(nodeptr* root){
int result = 0;
if (root===null){
return 0;
}
else if (root->left == null && root -> right == null){ // left node
return 1;
}
result = get_node_count((nodeptr)*root->left)
+
get_node_count((nodeptr*)root->right);
return result;
}
C
복사
6. 일반 트리를 이진 트리로 변환
•
일반 트리에 대하여 각 노드의 형제들을 연결
◦
각 노드에 대하여 가장 왼쪽 링크만 남기고 모두 제거
•
루트 노드는 반드시 왼쪽 자식 노드 하나만 갖도록 함
