1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
// 이진 탐색 트리를 사용한 영어 사전
#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;
}
cs