#include <stdio.h>

typedef struct _Node
{
    int value;
    _Node* parent;
    _Node* left;
    _Node* right;
}Node;

Node* root;
void BSTree_destroy(Node* node)
{
    if (node == NULL)
        return;
    BSTree_destroy(node->left);
    BSTree_destroy(node->right);
    delete node;
}

void BSTree_init()
{
    BSTree_destroy(root);
}

Node* BSTree_search(int value)
{
    Node* node = root;
    while (node)
    {
        if (node->value < value)
            node = node->right;
        else if (node->value > value)
            node = node->left;
        else
            return node;
    }
    return NULL;
}

void BSTree_insert(int value)
{
    Node* parent = NULL;
    Node* node = root;
    while (node)
    {
        parent = node;
        if (node->value < value)
            node = node->right;
        else if (node->value > value)
            node = node->left;
        else
            return;
    }

    Node* new_node = new Node;
    new_node->value = value;
    new_node->parent = NULL;
    new_node->left = new_node->right = NULL;
    if (!parent)
        root = new_node;
    else
    {
        if (parent->value < value)
            parent->right = new_node;
        else
            parent->left = new_node;
    }
    new_node->parent = parent;
}

void BSTree_delete(Node* node)
{
    Node* parent = node->parent;
    if (!node->left && !node->right)//node為葉子結(jié)點
    {
        if (!parent)
            root = NULL;
        else
        {
            if (parent->left == node)
                parent->left = NULL;
            else
                parent->right = NULL;
        }
        delete node;
    }
    else if (node->left && node->right)//node結(jié)點左右子樹均不為空
    {
        Node* pre_node= node->left;
        while (pre_node->right)
        {
            pre_node = pre_node->right;
        }
        node->value = pre_node->value; //找到直接前驅(qū),替換當(dāng)前節(jié)點
        if (pre_node->parent == node) //未執(zhí)行上述while循環(huán),重接左子樹
            pre_node->parent->left = pre_node->left;
        else                          //執(zhí)行上述while循環(huán),重接右子樹
            pre_node->parent->right = pre_node->left;
        if (pre_node->left)
            pre_node->left->parent = pre_node->parent;
        delete pre_node;
    }
    else//node結(jié)點的左子樹為空或者右子樹為空
    {
        Node* child = node->left ? node->left : node->right;
        if (!parent)
        {
            root = child;
            child->parent = root;
        }
        else
        {
            child->parent = parent;
            if (parent->left == node)
                parent->left = child;
            else
                parent->right = child;
        }
        delete node;
    }
}
int main(void)
{
    BSTree_init();
    BSTree_insert(8);
    BSTree_insert(3);
    BSTree_insert(10);
    BSTree_insert(1);
    BSTree_insert(6);
    BSTree_insert(14);
    BSTree_insert(4);
    BSTree_insert(7);
    BSTree_insert(13);

    Node* node = BSTree_search(100);
    if (!node || node->value != 100)
        printf("search error!\n");

    node = BSTree_search(10);
    if (!node || node->value != 10)
        printf("search error!\n");
    else
        BSTree_delete(node);

    node = BSTree_search(3);
    if (!node || node->value != 3)
        printf("search error!\n");
    else
        BSTree_delete(node);

    node = BSTree_search(8);
    if (!node || node->value != 8)
        printf("search error!\n");
    else
        BSTree_delete(node);

    return 0;
}