BST

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct element
{
    int id;
    char name[50];
    char address[100];
} element;
typedef struct node
{
    element data;
    struct node *left, *right;
} node;

void insert(element data);
node *allocate_node();
void add(node *current);
void initialize_node(struct node *current, element data);
void find(int id);
void deleten(int id);
node *find_prev_node();
void inorder(node *search, int type);
void clear_enter();
void dprocess(node *prev, node *curr, node *next);
void change(node *curr);
node *root = NULL;
int flag;
int main(void)
{
    element temp;
    char ctr = 0;
    int id = 0;
    for (;;)
    {
        printf("i<삽입>, d<삭제>, f<탐색>, r<전체읽기>, q<작업 종료>를 선택하시오.:");
        scanf("%c", &ctr);
        getchar();
        switch (ctr)
        {
        case 'i':
        {
            while (1)
            {
                printf("삽입할 자료(학번, 이름, 주소)를 입력하시오.:");
                scanf("%d %s", &temp.id, temp.name);
                fgets(temp.address, 100, stdin);
                clear_enter(temp.address);
                if (temp.id == 0)
                    break;
                insert(temp);
            }
            break;
        }
        case 'd':
        {
            printf("삭제할 자료의 학번을 입력하시오.:");
            scanf("%d", &id);
            fflush(stdin); //쓰지 않으면 표준입력스트림에 엔터키가 남아 ctr이 작동오류가 생기는 것 같다.
            deleten(id);
            id = 0;
            break;
        }
        case 'f':
        {
            printf("탐색할 자료의 학번을 입력하시오.:");
            scanf("%d", &id);
            fflush(stdin);
            inorder(root, id);
            if (!flag)
                printf("입력한 데이터가 존재하지 않습니다.");
            id = 0, flag = 0;
            break;
        }
        case 'r':
        {
            inorder(root, -1);
            break;
        }
        case 'q':
            break;
        }
        printf("\n");
        if (ctr == 'q')
            break;
        ctr = 0;
    }
}

void insert(element data)
{
    node *current, *search;
    current = allocate_node();
    initialize_node(current, data);
    if (root == NULL)
        root = current;
    else
        add(current);
}

node *allocate_node()
{
    node *temp;
    temp = (node *)malloc(sizeof(node));
    return temp;
}

void initialize_node(node *current, element data)
{
    current->data = data;
    current->left = NULL;
    current->right = NULL;
}

void add(node *current)
{
    node *search = root;
    while (1)
    {
        if (current->data.id < search->data.id)
        {
            if (search->left)
                search = search->left;
            else
            {
                search->left = current;
                break;
            }
        }
        else if (current->data.id > search->data.id)
        {
            if (search->right)
                search = search->right;
            else
            {
                search->right = current;
                break;
            }
        }
        else
        {
            printf("올바르지 않은 자료입니다.\n");
            exit(1);
        }
    }
}
void clear_enter(char *address)
{
    if (address[strlen(address) - 1] == '\n')
        address[strlen(address) - 1] = 0;
}

void inorder(node *search, int type) //inorder을 살짝 개조하여 탐색함수를 따로 만들지 않고 한꺼번에 사용했다.
{
    {
        if (search) //search가 null이 아니라면
        {
            inorder(search->left, type);
            if (type == -1) //전체읽기 모드
                printf("%d %s %s\n", search->data.id, search->data.name, search->data.address);
            else if (search->data.id == type) //학번 탐색 모드
            {
                printf("<%d %s %s>\n", search->data.id, search->data.name, search->data.address);
                flag++;
                return;
            }
            inorder(search->right, type);
        }
    }
}

void deleten(int id)
{
    node *prev = NULL, *curr; //curr : 지우고자 하는 노드
    curr = root;
    while (curr) //curr이 null이 아닌 동안
    {
        if (curr->data.id < id)
        {
            prev = curr;
            curr = curr->right;
        }
        else if (curr->data.id > id)
        {
            prev = curr;
            curr = curr->left;
        }
        else
            break;
    } //prev의 위치와 curr의 위치를 담기 위함.

    if (!curr) //만약 curr이 null이라서 while문이 종료된 경우
    {
        printf("삭제할 데이터가 존재하지 않습니다.\n");
        return;
    }
    /*****************************************************/
    if (curr->left == NULL && curr->right == NULL) //자식노드가 없을 때
        dprocess(prev, curr, NULL);

    //자식노드가 하나일 때
    else if (curr->left == NULL)
        dprocess(prev, curr, curr->right);
    else if (curr->right == NULL)
        dprocess(prev, curr, curr->left);

    //자식노드가 둘일 때
    else
        change(curr);
    printf("삭제되었습니다.\n");
    /*****************************************************/
}

void dprocess(node *prev, node *curr, node *next)
{
    if (prev)//부모가 있다면
    {
        if (prev->data.id > curr->data.id)
            prev->left = next;
        else
            prev->right = next;
    }
    else//부모가 없다면
        root = next;
    free(curr);
}

void change(node *curr)
{
    /*자식노드가 둘인 노드를 삭제할 땐 
    1. 왼쪽 노드(부모보다 작은 노드)들 중 가장 큰 값이나
    2. 오른쪽 노드(부모보다 큰 노드)들 중 가장 작은 값이 부모의 자리에 올 수 있다.
    아래 코드는 1번 경우를 구현한 것이다.
    */
    node *search, *prev;
    element temp;
    search = curr->left; //왼쪽 자식
    while (1)
    {
        if (search->right) //오른쪽 자식이 있으면 오른쪽 자식으로 간다.
        {
            prev = search;
            search = search->right;
        }
        else if (search->left) //오른쪽 자식이 없으면 왼쪽 자식에게 가고
        {
            prev = search;
            search = search->left;
        }
        else //둘 다 없으면 끝지점에 도달했으니
        {
            curr->data = search->data; //삭제하고자 하는 녀석과 데이터를 바꾸고
            //어차피 지울 녀석의 데이터는 옮겨줄 필요 없다.
            dprocess(prev, search, NULL); //바꾼 지점을 지워준다.
            break;
        }
    }
}