반응형
트리의 응용: 디렉토리 용량 계산
이진트리를 사용하기 때문에 하나의 디렉토리 안에는 다른 디렉토리가 2개를 초과하면 안 된다.
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
int calc_dir_size(TreeNode *root)
{
int left_size, right_size;
if (root == NULL) return 0;
left_size = calc_dir_size(root->left);
right_size = calc_dir_size(root->right);
return (root->data + left_size + right_size);
}
//
int main(void)
{
TreeNode n4 = { 500, NULL, NULL };
TreeNode n5 = { 200, NULL, NULL };
TreeNode n3 = { 100, &n4, &n5 };
TreeNode n2 = { 50, NULL, NULL };
TreeNode n1 = { 0, &n2, &n3 };
printf("디렉토리의 크기=%d\n", calc_dir_size(&n1));
}
스레드 이진 트리
NULL 링크에 중위 순회 시에 선행 노드인 중위 선행자(inorder predecessor)나 중위 순회 시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리가 스레드 이진트리(theaded binary tree)이다. 스레드(thread), 즉 실을 이용하여 노드들은 순회 순서대로 연결시켜 놓은 트리이다.
#include <stdio.h>
#define TRUE 1
#define FALSE 0
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
int is_thread; // 스레드이면 TRUE
} TreeNode;
// G
// C F
// A B D E
TreeNode n1 = { 'A', NULL, NULL, 1 };
TreeNode n2 = { 'B', NULL, NULL, 1 };
TreeNode n3 = { 'C', &n1, &n2, 0 };
TreeNode n4 = { 'D', NULL, NULL, 1 };
TreeNode n5 = { 'E', NULL, NULL, 0 };
TreeNode n6 = { 'F', &n4, &n5, 0 };
TreeNode n7 = { 'G', &n3, &n6, 0 };
TreeNode * exp = &n7;
TreeNode * find_successor(TreeNode * p)
{
// q는 p의 오른쪽 포인터
TreeNode * q = p->right;
// 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
if (q == NULL || p->is_thread == TRUE)
return q;
// 만약 오른쪽 자식이면 다시 가장 왼쪽 노드로 이동
while (q->left != NULL) q = q->left;
return q;
}
void thread_inorder(TreeNode * t)
{
TreeNode * q;
q = t;
while (q->left) q = q->left;// 가장 왼쪽 노드로 간다.
do {
printf("%c -> ", q->data);// 데이터 출력
q = find_successor(q); // 후속자 함수 호출
} while (q); // NULL이 아니면
}
int main(void)
{
// 스레드 설정
n1.right = &n3;
n2.right = &n7;
n4.right = &n6;
// 중위 순회
thread_inorder(exp);
printf("\n");
return 0;
}
이진 탐색 트리에서 삭제 연산
1. 삭제하려는 노드가 단말 노드일 경우
삭제하려는 노드가 단말 노드일 경우를 생각해보자. 이 경우에는 단말노드 아래에 더 이상의 노드가 없으므로 가장 쉽게 할 수 있다. 단말노드만 지우면 된다. 단말 노드를 지운다는 것은 단말노드의 부모노드를 찾아서 부모노드 안의 링크필드를 NULL로 만들어서 연결을 끊으면 된다. 다음으로 만약 노드를 동적으로 생성하였다면 이 단말노드를 동적 메모리 해제시키면 된다.
2. 삭제하려는 노드가 하나의 서브트리만 가지고 있는 경우
삭제되는 노드가 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우에는 자기 노드는 삭제하고 서브 트리는 자기 노드의 부모 노드에 붙여주면 된다.
3. 삭제하려는 노드가 두개의 서브트리를 가지고 있는 경우
왼쪽 서브트리에서 가장 큰 값은 왼쪽 서브트리의 가장 오른쪽에 잇는 노드이며 오른쪽 서브트리에서 가장 작은 값은 오른쪽 서브트리의 가장 왼쪽에 있는 노드가 된다. 또한 이들 노드는 이진 탐색 트리를 중위순회하였을 경우, 각각 선행노드와 후속노드에 해당한다.
이진 탐색 트리
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct TreeNode {
element key;
struct TreeNode *left, *right;
} TreeNode;
// 순환적인 탐색 함수
TreeNode * search(TreeNode * node, int key)
{
if (node == NULL) return NULL;
if (key == node->key) return node;
else if (key < node->key)
return search(node->left, key);
else
return search(node->right, key);
}
TreeNode * new_node(int item)
{
TreeNode * temp = (TreeNode *)malloc(sizeof(TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
TreeNode * insert_node(TreeNode * node, int key)
{
// 트리가 공백이면 새로운 노드를 반환한다.
if (node == NULL) return new_node(key);
// 그렇지 않으면 순환적으로 트리를 내려간다.
if (key < node->key)
node->left = insert_node(node->left, key);
else if (key > node->key)
node->right = insert_node(node->right, key);
// 변경된 루트 포인터를 반환한다.
return node;
}
TreeNode * min_value_node(TreeNode * node)
{
TreeNode * current = node;
// 맨 왼쪽 단말 노드를 찾으러 내려감
while (current->left != NULL)
current = current->left;
return current;
}
// 이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고
// 새로운 루트 노드를 반환한다.
TreeNode * delete_node(TreeNode * root, int key)
{
if (root == NULL) return root;
// 만약 키가 루트보다 작으면 왼쪽 서브 트리에 있는 것임
if (key < root->key)
root->left = delete_node(root->left, key);
// 만약 키가 루트보다 크면 오른쪽 서브 트리에 있는 것임
else if (key > root->key)
root->right = delete_node(root->right, key);
// 키가 루트와 같으면 이 노드를 삭제하면 됨
else {
// 첫 번째나 두 번째 경우
if (root->left == NULL) {
TreeNode * temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
TreeNode * temp = root->left;
free(root);
return temp;
}
// 세 번째 경우
TreeNode * temp = min_value_node(root->right);
// 중외 순회시 후계 노드를 복사한다.
root->key = temp->key;
// 중외 순회시 후계 노드를 삭제한다.
root->right = delete_node(root->right, temp->key);
}
return root;
}
// 중위 순회
void inorder(TreeNode * root) {
if (root) {
inorder(root->left);// 왼쪽서브트리 순회
printf("[%d] ", root->key); // 노드 방문
inorder(root->right);// 오른쪽서브트리 순회
}
}
int main(void)
{
TreeNode * root = NULL;
TreeNode * tmp = NULL;
root = insert_node(root, 30);
root = insert_node(root, 20);
root = insert_node(root, 10);
root = insert_node(root, 40);
root = insert_node(root, 50);
root = insert_node(root, 60);
printf("이진 탐색 트리 중위 순회 결과 \n");
inorder(root);
printf("\n\n");
if (search(root, 30) != NULL)
printf("이진 탐색 트리에서 30을 발견함 \n");
else
printf("이진 탐색 트리에서 30을 발견못함 \n");
return 0;
}
이진 탐색 트리의 응용: 영어사전
// 이진 탐색 트리를 사용한 영어 사전
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#define MAX_WORD_SIZE 100
#define MAX_MEANING_SIZE 200
// 데이터 형식
typedef struct {
char word[MAX_WORD_SIZE]; // 키필드
char meaning[MAX_MEANING_SIZE];
} element;
// 노드의 구조
typedef struct TreeNode {
element key;
TreeNode *left, *right;
} TreeNode;
// 만약 e1 < e2 이면 -1 반환
// 만약 e1 == e2 이면 0 반환
// 만약 e1 > e2 이면 1 반환
int compare(element e1, element e2)
{
return strcmp(e1.word, e2.word);
}
// 이진 탐색 트리 출력 함수
void display(TreeNode * p)
{
if (p != NULL) {
printf("(");
display(p->left);
printf("%s:%s", p->key.word, p->key.meaning);
display(p->right);
printf(")");
}
}
// 이진 탐색 트리 탐색 함수
TreeNode * search(TreeNode * root, element key)
{
TreeNode * p = root;
while (p != NULL) {
if (compare(key, p->key) == 0)
return p;
else if (compare(key, p->key) < 0)
p = p->left;
else if (compare(key, p->key) > 0)
p = p->right;
}
return p; // 탐색에 실패했을 경우 NULL 반환
}
TreeNode * new_node(element item)
{
TreeNode * temp = (TreeNode *)malloc(sizeof(TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
TreeNode * insert_node(TreeNode * node, element key)
{
// 트리가 공백이면 새로운 노드를 반환한다.
if (node == NULL) return new_node(key);
// 그렇지 않으면 순환적으로 트리를 내려간다.
if (compare(key, node->key)<0)
node->left = insert_node(node->left, key);
else if (compare(key, node->key)>0)
node->right = insert_node(node->right, key);
// 루트 포인터를 반환한다.
return node;
}
TreeNode * min_value_node(TreeNode * node)
{
TreeNode * current = node;
// 맨 왼쪽 단말 노드를 찾으러 내려감
while (current->left != NULL)
current = current->left;
return current;
}
// 이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고
// 새로운 루트 노드를 반환한다.
TreeNode * delete_node(TreeNode * root, element key)
{
if (root == NULL) return root;
// 만약 키가 루트보다 작으면 왼쪽 서브 트리에 있는 것임
if (compare(key, root->key)<0)
root->left = delete_node(root->left, key);
// 만약 키가 루트보다 크면 오른쪽 서브 트리에 있는 것임
if (compare(key, root->key)>0)
root->right = delete_node(root->right, key);
// 키가 루트와 같으면 이 노드를 삭제하면 됨
else {
// 첫 번째나 두 번째 경우
if (root->left == NULL) {
TreeNode * temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
TreeNode * temp = root->left;
free(root);
return temp;
}
// 세 번째 경우
TreeNode * temp = min_value_node(root->right);
// 중외 순회시 후계 노드를 복사한다.
root->key = temp->key;
// 중외 순회시 후계 노드를 삭제한다.
root->right = delete_node(root->right, temp->key);
}
return root;
}
//
void help()
{
printf("\n**** i: 입력, d: 삭제, s: 탐색, p: 출력, q: 종료 ****: ");
}
// 이진 탐색 트리를 사용하는 영어 사전 프로그램
int main(void)
{
char command;
element e;
TreeNode * root = NULL;
TreeNode * tmp;
do {
help();
command = getchar();
getchar(); // 엔터키 제거
switch (command) {
case 'i':
printf("단어:");
gets(e.word);
printf("의미:");
gets(e.meaning);
root = insert_node(root, e);
break;
case 'd':
printf("단어:");
gets(e.word);
root=delete_node(root, e);
break;
case 'p':
display(root);
printf("\n");
break;
case 's':
printf("단어:");
gets(e.word);
tmp = search(root, e);
if (tmp != NULL)
printf("의미:%s\n", e.meaning);
break;
}
} while (command != 'q');
return 0;
}
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 8장 연습문제 해설을 가져오도록 하겠습니다.
반응형