C언어 - 이진탐색트리 과제

#include <stdio.h>
#include <stdlib.h>

struct tnode {
    int item;		/* number */
    struct tnode* left;	/* left child */
    struct tnode* right;	/* right child */
};

struct tnode* addtree(struct tnode*, int);  // 트리추가함수 선언
void deletetree(struct tnode **, int);      // 트리제거함수 선언
void treeprint(struct tnode*);              // 트리출력함수 선언

main()
{
    struct tnode* root;
    int cond, num;
    root = NULL;  // 초기화

    while (1) {
        printf("1 : 삽입   2 : 삭제   3 : 출력   4 : 종료\n");
        scanf_s("%d", &cond);
        if (cond == 1) {
            printf("Add Number\n");
            scanf_s("%d", &num);
            root = addtree(root, num);
        }
        else if (cond == 2) {
                printf("Delete Number\n");
        scanf_s("%d",&num);
        deletetree(&root, num);
                }
        else  if (cond == 3) {
            printf("------------출력---------\n");
            treeprint(root);
        }
        else  if (cond == 4)
            break;
        else {
            printf("Wrong Input\n");
            exit(1);
        }
        
    }
    return 0;
}



struct tnode* addtree(struct tnode* p, int num)
{
    if (p == NULL) {
        p = (struct tnode*)malloc(sizeof(struct tnode));
        p->item = num;
        p->left = p->right = NULL;
    }
    else if (num == p->item)
        printf("존재하는 숫자 입니다\n");
    else if (num < p->item)
        p->left = addtree(p->left, num);
    else
        p->right = addtree(p->right, num);
    return p;
}


void treeprint(struct tnode* p)
{
    if (p != NULL) {
        treeprint(p->left);
        printf("%d\n", p->item);
        treeprint(p->right);
    }
}

void deletetree(struct tnode** p, int num) {

    struct tnode* deleted= *p;
    struct tnode* prev = *p;
    struct tnode* parent = NULL;
    struct tnode* move = NULL;


    if (*p == NULL) { //트리에 숫자가 없을 경우
        printf("삭제 할 수 있는 숫자가 없습니다.\n");
        return;
    }

    if (deleted->item == num) { //지울 값이 루트 값일경우

        if (deleted->left == NULL && deleted->right == NULL) { //루트 값에 자식 데이터가 없으므로 루트값만 남은 상태
            *p = NULL;
            printf("숫자가 모두 삭제되었습니다.\n");
            return; // 초기화 상태로 리턴
        }
        else if (deleted->left == NULL) { // 오른쪽 값만 존재할 경우
            *p = deleted->right;  // 구조체가 가르키는 주소를 오른쪽 값으로 변경하여 오른쪽 값이 루트가 되게만듬
        }
    }

    while ((deleted->item != num)) { //숫자 값을 찾는 반복문

        prev = deleted; // 왼쪽 주소값이 없거나 둘 다 없는경우를 해결하기 위한 값

        if (deleted->item < num)   // 작으면 왼쪽
            deleted = deleted->right;
        else
            deleted = deleted->left; // 크면 오른쪽

        if (deleted == NULL) { // 트리에 삭제 할 숫자가 존재하지 않을경우
            printf("존재하지 않는 숫자입니다.\n");
            return;
        }
    }

    if (deleted->left) { // 왼쪽을 우선 검색

        move = deleted->left; // 먼저 왼쪽 주소값으로 들어간다.

        if (move->right) { //왼쪽의 숫자중 가장 큰 숫자를 검색
            while (move->right != NULL) {
                parent = move;
                move = move->right;
            }
            parent->right = move->left;  //주소를 연결시켜주기
        }
        else 
            parent = deleted;

        if (deleted == parent) 
            parent->left = move->left;  //주소를 연결시켜주기
        else
            parent->right = move->left; //주소를 연결시켜주기

        deleted->item = move->item; //삭제한 데이터에 이동할 숫자 입력
    }
    else if (deleted->right)        //전 주소를 다음 주소로 연결
        prev->right = deleted->right;
    else if(prev->item > num)        //자식 숫자값이 없는경우
        prev->left = NULL;          //부모값보다 작으니 왼쪽 연결해제
    else
        prev->right = NULL;         //부모값보다 크니 오른쪽 연결해제
    
}