이진 탐색 트리(Binary Search Tree) C로 구현하기

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

typedef struct _Node
{
    int value;
    struct _Node *left_child;
    struct _Node *right_child;
}Node;

Node* search(Node *root, int x);

Node* insert(Node *root, int x);

Node* find_min(Node *root);

Node* delete(Node *root, int x);

int count = 0;


int main()
{
    Node *root;
    int N;
    int i, input;
    root = NULL;

    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%d", &input);
        root = insert(root, input);
        printf("%d \n", count);
    }

}


Node* search(Node *root, int x)
{
    if (root -> value == x)
        return root;
    
    else if (root -> value > x)
        return search(root -> left_child, x);
    else
        return search(root -> right_child, x);
    
}

Node* insert(Node *root, int x)
{
    if (root == NULL) {
        root = (Node*)malloc(sizeof(Node*));
        root -> value = x;
        root -> left_child = NULL;
        root -> right_child = NULL;
        
        return root;
    }
    else
    {
        count += 1;
        if (root -> value > x)
            root -> left_child = insert(root -> left_child, x);
        else
            root -> right_child = insert(root -> right_child, x);
    }
    return root; 
}

Node* find_min(Node *root)
{
    if (root == NULL)
        return NULL;
    else if (root -> left_child != NULL)
        return find_min(root -> left_child);
    return root;
}




Node* delete(Node *root, int x)
{
    if (root == NULL)
        return NULL;
    if (root -> value > x)
        root -> left_child = delete(root -> left_child, x);
    else if (root -> value < x)
        root -> right_child = delete(root -> right_child, x);
    else
    {
        if (root -> left_child == NULL && root -> right_child == NULL)
        {
            free(root);
            return NULL;
        }

        else if (root -> left_child == NULL || root -> right_child == NULL)
        {
            Node* temp;
            if (root -> left_child == NULL)
                temp = root -> right_child;
            else
                temp = root -> left_child;
            
            free(root);
            return temp;
        }

        else
        {
            Node* temp = find_min(root -> right_child);
            root -> value = temp -> value;
            root -> right_child = delete(root -> right_child, temp -> value);
        }
    }
    return root;
}