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

typedef int TElement;

typedef struct TNode {
    TElement data;
    struct TNode* left;
    struct TNode* right;
} TNode;

TNode* create_tree(TElement data, TNode* left, TNode* right)
{
    TNode* n = (TNode*)malloc(sizeof(TNode));
    n->data = data;
    n->left = left;
    n->right = right;
    return n;
}
//
#define Visitnode(n) (printf("%d ", (n)->data))
#define KEY(n) ((n)->data)

Node* search_bst(Node* root, int key){
    if(root == NULL){
        return NULL;
    }

    if(KEY(n) == key){
        return root;
    }
    else if(KEY(n) > key){
        return search_bst_bst(root->left, key);
    }
    else{
        return search_bst_bst(root->right, key);
    }
    
}

void insert_bst(Node* root, Node* n){
    if(KEY(n) < KEY(root)){
        if(root->left == NULL){
            root->left = n;
        }
        else{
            insert_bst(root->left, n);
        }
    }
    else if(KEY(n) > KEY(root)){
        if(root->right == NULL){
            root->right = n;
        }
        else{
            insert_bst(root->right, n);
        }
    }
}

void delete_bst(Node* root, int key){
    if(root == NULL){
        return NULL;
    }

    if(key < KEY(root)){
        root->left = delete_bst(root->left, key);
    }
    else if(key > KEY(root)){
        root->right = delete_bst(root->right, key);
    }
    else{
        Node* n = root;

        if(n->left == NULL){
            root = n->right;
            free(n);
        }
        else if(n->right == NULL){
            root = n->left;
            free(n);
        }
        else{
            Node* succ = n->right;

            while(succ->left == NULL){
                succ = succ->left;
            }

            n->data = succ->data;
            n->right = delete_bst(n->right, succ->data);
        }
    }
}
//
int main()
{
    int keys[] = { 35, 18, 7, 26, 12, 3, 68, 22, 30, 99 };

    TNode* root = create_tree(keys[0], NULL, NULL);

    for (int i = 1; i < 10; i++) {
        TNode* n = create_tree(keys[i], NULL, NULL);
        insert_bst(root, n);

        printf("\n 삽입 %2d: ", keys[i]);
        preorder(root);
    }

    printf("\n");

    TNode* n = search_bst(root, 26);
    printf("26 탐색: %s\n", (n != NULL) ? "성공" : "실패");

    n = search_bst(root, 25);
    printf("25 탐색: %s\n", (n != NULL) ? "성공" : "실패");

    root = delete_bst(root, 3);
    printf("\n 삭제  3: ");
    preorder(root);

    root = delete_bst(root, 68);
    printf("\n 삭제 68: ");
    preorder(root);

    root = delete_bst(root, 18);
    printf("\n 삭제 18: ");
    preorder(root);

    return 0;
}