# 7_BST(Binary Search Tree)

 

 

# The source code

#include <stdio.h>
#include <stdlib.h>
// 이해하자! 어렵다! cursive algorithm
struct node
{
    int i;
    struct node * left;
    struct node * right;
};
 
struct node * root = 0;
 
void addToBST(int n)
{
    struct node * cur = (struct node *)malloc(sizeof(struct node));
    cur->left = 0; 
    cur->right = 0; 
    cur->i = n;
 
    if (root == 0)
    {
        root = cur;
    }
    else
    {
        struct node * temp = root;
        while (1)
        {
            if (temp->i >= cur->i) //left
            {
                if (temp->left == 0)
                {
                    temp->left = cur;
                    return;
                }
                else
                {
                    temp = temp->left;
                }
            }
            else //right
            {
                if (temp->right == 0)
                {
                    temp->right = cur;
                    return;
                }
                else
                {
                    temp = temp->right;
                }
            }
        }
    }
}
struct node * findLeast(struct node * node)
{
    struct node * cur = node;
    while (cur->left != 0)
    {
        cur = cur->left;
    }
    return cur;
}
struct node * removeNode(struct node * node, int key)
{
    if (node == 0)
    {
        return 0;
    }
    if (key == node->i)
    {
        if (node->left == 0 && node->right == 0)
        {
            free(node);
            return 0;
        }
        else if (node->left == 0) // 오른쪽 자식만 있는 경우
        {
            struct node * ret = node->right;
            free(node);
            return ret;
        }
        else if (node->right == 0) // 왼쪽 자식만 있는 경우
        {
            struct node * ret = node->left;
            free(node);
            return ret;
        }
        else // 두쪽다 자식이 있는 경우
        {
            struct node * toReplace = findLeast(node->right);
            node->i = toReplace->i;
            node->right = removeNode(node->right, toReplace->i);
            return node;
        }
    }
    else if (key < node->i)
    {
        node->left = removeNode(node->left, key);
        return node;
    }
    else
    {
        node->right = removeNode(node->right, key);
        return node;
    }
}
 
void printBST(struct node * node)
{
    if (node == 0)
    {
        return;
    }
    printBST(node->left);
    printf("%d -> ", node->i);
    printBST(node->right);
}
void main()
{
    addToBST(10);
    addToBST(5);
    addToBST(20);
    addToBST(30);
    addToBST(7);
    addToBST(40);
    addToBST(3);
    addToBST(33);
 
    printBST(root);
    printf("\n");
 
    removeNode(root, 30);
    printf("BST after removing root 30 : ");
    printBST(root);
    printf("\n");
} 

 

 

 

# The result