#6. 학생 정보를 관리하는 이진 탐색트리 구현

문제

이진 탐색트리의 삽입, 삭제, 탐색, 순회 및 출력 기능을 바탕으로 학생의 이름과 전화번호를 관리하는 이진탐색트리를 구현하라.

풀이

각 기능을 수행하는 함수는 책에서 학습 할 수 있지만 삭제 함수의 경우, 제가 갖고있는 2권의 자료구조책에는 삭제함수를 반복문으로 구현했는데, 물론 기능적인 면에서 순환방식보다 빠르고 효율적이지만 코드가 복잡하고, 혼자서 머릿속으로 구현하기가 힘든 것 같아 순환방법의 구현을 공부했습니다.

구현 면에서는 반복문보다 순환호출이 더 이해와 구현이 쉬운 것 같습니다.

주의할 것은 삭제함수에 if문이 많은데 각 경우를 if로 표현하면 학생 정보를 삭제하고 출력 시 원하지 않는 결과가 나올 수 있습니다. 

반드시 if~ else if ~ else 문으로 함수를 작성해야합니다. 

그리고 가끔 이런 학생정보 관리 프로그램이나 사전 프로그램 등을 구현하다보면 꼭 공백이나 엔터키가 말썽을 부렸는데

다행히 아래 코드처럼 작성하니 엔터키 관련해서는 오류가 뜨지않았습니다.

133~134행을 주석 처리 후 135~136행을 작성 후 실행 하면 원하는 기능의 알파벳 입력 시 한글을 입력하면 엔터키 오류가 뜹니다.

코드

// 이진 탐색 트리를 사용한 영어 사전
#pragma warning(disable:4996)
#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 name[MAX_WORD_SIZE];        // 키필드
    char number[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.name, e2.name);
}
// 이진 탐색 트리 출력 함수
void display(TreeNode* p)
{
    if (p != NULL) {
        //printf("(");
        display(p->left);
        printf("이름:%s\n전화번호%s\n", p->key.name, p->key.number);
        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);
    // 만약 키가 루트보다 크면 오른쪽 서브 트리에 있는 것임
    else 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("삽입(i), 탐색(s),프린트(p), 삭제(d): ");
}
// 이진 탐색 트리를 사용하는 영어 사전 프로그램 
int main(void)
{
    char command;
    element e;
    TreeNode* root = NULL;
    TreeNode* tmp;
 
    while(1){
        help();
        //command = getchar();
        //getchar();        // 엔터키 제거
        scanf(" %c", &command);
        getchar();
        switch (command) {
        case 'i':
            printf("친구의 이름: ");
            scanf(" %s", e.name);
            getchar();
            printf("친구의 전화번호: ");
            scanf(" %s", e.number);
            getchar();
            root = insert_node(root, e);
            break;
        case 'd':
            printf("이름:");
            scanf(" %s", e.name);
            getchar();
            root = delete_node(root, e);
            break;
        case 'p':
            display(root);
            printf("\n");
            break;
        case 's':
            printf("친구의 이름:");
            scanf(" %s", e.name);
            getchar();
            tmp = search(root, e);
            if (tmp != NULL)
                printf("%s의 전화번호:%s\n",tmp->key.name, tmp->key.number);
            else
                printf("데이터가 존재하지 않습니다.\n");
            break;
        case 'q':return 0;
        default: 
            printf("잘못입력습니다.재입력하세요\n");
 
        }
 
    }/* while (command != 'q');*/
    return 0;
}

결과