[자료구조] BST c

BST c

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

#pragma warning (disable : 4996)

typedef struct tree
{
    int value;
    struct tree* left;
    struct tree* right;
}tree;

tree* insertNodeTree(tree* t, int data);
tree* getMaxNode(tree* t);
tree* getMinNode(tree* t);
tree* getSearchNode(tree* t, int target);
void displayBST(tree* t);
void memoryFree(tree* t);
int getSumTreeNode(tree* t);
int getCountTreeNode(tree* t);
tree* removeNodeTree(tree* t, int target);

tree* insertNodeTree(tree* t, int data)
{
    // BST, 이진 검색 트리는 중복값을 허용하지 않는다.
    if(t == NULL)
    {
        t = (tree*)malloc(sizeof(tree));
        t->value = data;
        t->left = NULL;
        t->right = NULL;
    }
    else if(t->value < data)
    {
        //부모보다 큰 값은 오른쪽에 연결
        t->right = insertNodeTree(t->right, data); //오른쪽 값으로 재귀호출
    }
    else if(t->value > data)
    {
        //부모보다 작은 값은 왼쪽에 연결
        t->left = insertNodeTree(t->left, data); //왼쪽 값으로 재귀호출
    }
    return t; //생성된 노드의 주소를 리턴
}

tree* getMaxNode(tree* t)
{
    //반복문 이용 또는 재귀호춯
    //재귀호출
    /*
    if (t != NULL)
    {
        if(t->right != NULL) //오른쪽 자식 노드가 있다면?
            return getMaxNode(t->right); //재귀 호출
    }
    return t;
    */

    //반복문
    if (t != NULL)
    {
        while(t->right != NULL)    //오른쪽 자식 노드가 있다면?
            t = t->right; //오른쪽 자식 노드로 변경
    }
    return t;
}

tree* getMinNode(tree* t)
{
    //반복문 이용 또는 재귀호춯
    //재귀호출
    /*
    if (t != NULL)
    {
        if(t->left != NULL) //왼쪽 자식 노드가 있다면?
            return getMinNode(t->left); //재귀 호출
    }
    return t;
    */

    //반복문
    if (t != NULL)
    {
        while(t->left != NULL)    //왼쪽 자식 노드가 있다면?
            t = t->left; //왼쪽 자식 노드로 변경
    }
    return t;
}

tree* getSearchNode(tree* t, int target)
{
    if (t != NULL)
    {
        if(t->value == target)
            return t;
        else if(t->value < target)
            return getSearchNode(t->right, target);
        else
            return getSearchNode(t->left, target);
    }

    return t;
}

void displayBST(tree* t)
{
    //중위순회(왼쪽 - 부모 - 오른쪽): BST는 오름차순 정렬된다.
    if(t != NULL)
    {
        displayBST(t->left);//왼쪽 재귀호출
        printf("%d ", t->value);
        displayBST(t->right);//오른쪽 재귀호출
  
    }
}

void memoryFree(tree* t)
{
    //후위 순회로 메모리 제거
    if(t != NULL)
    {
        memoryFree(t->left);//왼쪽 재귀호출
        memoryFree(t->right);//오른쪽 재귀호출
        printf("%d 메모리 제거\n", t->value);
        free(t);
    }
}

int getSumTreeNode(tree* t)
{
    if(t != NULL)
        return getSumTreeNode(t->left) + getSumTreeNode(t->right) + t->value;
    return 0;
}

int getCountTreeNode(tree* t)
{
    if(t != NULL)
        return getCountTreeNode(t->left) + getCountTreeNode(t->right) + 1;
    return 0;
}

tree* removeNodeTree(tree* t, int target)
{
    tree* temp;
    if (t != NULL)
    {
        if(t->value == target) //삭제할 노드를 찾았다!!
        {
            //여기에서 삭제

            if(t->left == NULL && t->right == NULL) //case 1. 삭제할 노드의 자식 노드가 없는 경우
            {
                free(t); //노드 제거
                printf("\n\n\t\t/case 1. 삭제할 노드의 자식 노드가 없는 경우\n");
                return NULL; //부모에게 NULL리턴
            }
            else if(t->right == NULL) //case 2. 왼쪽 자식 노드만 있는 경우
            {
                //왼쪽 자식 노드의 주소를 저장
                temp = t->left;
                free(t);
                printf("\n\n\t\tcase 2. 왼쪽 자식 노드만 있는 경우\n");
                return temp;
            }
            else if(t->left == NULL) //case 3. 오른쪽 자식 노드만 있는 경우
            {
                //오른쪽 자식 노드의 주소를 저장
                temp = t->right;
                free(t);
                printf("\n\n\t\tcase 3. 오른쪽 자식 노드만 있는 경우\n");
                return temp;
            }
            else //case 4. 자식 노드가 2개 있는 경우
            {
                temp = getMaxNode(t->left); //왼쪽 자식 노드에서 최댓값을 구해 리턴
                t->value = temp->value; //왼쪽 자식 노드 중 최댓값을 삭제할 위치로 대입
                printf("\n\n\t\tcase 4. 자식 노드가 둘 다 있는 경우 => 삭제되는 것이 아니라 왼쪽 자식 중 최댓값을 대입\n");
                printf("\t\t왼쪽 자식 중 최댓값을 제거하러 다시 출발!(재귀호출)\n");
                t->left = removeNodeTree(t->left, temp->value);
            }
        }
        else if(t->value < target)
        {
            //노드 삭제시 새로운 노드와 연결되기 위해 리턴 값을 받는다.
            t->right = removeNodeTree(t->right, target);
        }
        else
        {
            //노드 삭제시 새로운 노드와 연결되기 위해 리턴값을 받는다.
            t->left = removeNodeTree(t->left, target);
        }
    }
    return t;
}

int main()
{
    tree* findNode = NULL;
    tree* root = NULL; //촤싱위 노드의 주소 저장하는 포인터(8byte)
    int data;

    while (1)
    {
        system("cls");
        printf("\n\n\t * Binary Search Tree, BST *\n");
        printf("1. 원소 삽입\n");
        printf("2. 원소 삭제\n");
        printf("3. 원소 검색\n");
        printf("4. 최댓값 구하기\n");
        printf("5. 최솟값 구하기\n");
        printf("6. 이진 검색 트리 출력\n");
        printf("7. 트리 노드의 합\n");
        printf("8. 트리 노드의 개수\n");
        printf("0. 프로그램 종료\n");

        printf("\n메뉴 선택: ");
        int choice;
        scanf("%d", &choice);

        switch (choice)
        {
        case 1:
            printf("\n\n삽입할 노드의 값 입력: ");
            scanf("%d", &data);
   
            //트리애 노드 삽입 후 루트의 주소를 리턴
            root = insertNodeTree(root, data);
            break;
        case 2:
            printf("\n\n제가할 노드의 값을 입력: ");
            scanf("%d", &data);
     
            //트리에서 노드 제거 후 루트의 주소를 리턴
            root = removeNodeTree(root, data);
            break;
        case 3:
            printf("\n\n검색 노드의 값을 입력: ");
            scanf("%d", &data);
            // 검색한 노드가 있는 경우 그 노드의 주소를 리턴, 검색 노드가 없는 경우 NULL을 리턴
            findNode = getSearchNode(root, data);
  
            if(findNode == NULL)
                printf("\n\n\t\t검색 노드는 존재하지 않습니다.\n");
            else
                printf("\n\n\t\t검색한 노드는 %p번지에 저장되어 있습니다.\n", findNode);
            break;
        case 4:
            //최댓값 노드를 찾아 그 노드의 주소를 리턴, 찾는 노드가 없는 경우 NULL을 리턴
            findNode = getMaxNode(root);

            if(findNode == NULL)
                printf("\n\n\t\t최댓값 노드를 찾을 수 없습니다.\n");
            else
                printf("\n\n\t\t최댓값 노드는 %d입니다.\n", findNode->value);
            break;
        case 5:
            //최솟값 노드를 찾아 그 노드의 주소를 리턴, 찾는 노드가 없는 경우 NULL을 리턴
            findNode = getMinNode(root);

            if(findNode == NULL)
                printf("\n\n\t\t최솟값 노드를 찾을 수 없습니다.\n");
            else
                printf("\n\n\t\t최솟값 노드는 %d입니다.\n", findNode->value);
            break;
        case 6:
            printf("\n\nBST Display: ");
            displayBST(root);
            break;
        case 7:
            printf("\n\n\t\tBST 노드의 합은 %d입니다.\n", getSumTreeNode(root));
            break;
        case 8:
            printf("\n\n\t\tBST 노드의 개수는 %d입니다.\n", getCountTreeNode(root));
            break;
        case 0:
            memoryFree(root);
            return 0;
        }

        printf("\n\n\t\t");
        system("pause");
    }
    return 0;
}