性質(zhì)：
設(shè)x為二叉搜索樹上的節(jié)點圈膏，如果y為x的左子樹上的節(jié)點，則有y.key<=x.key鸦采；如果y為x的右子樹上的節(jié)點宾巍，則有y.key>x.key。

二叉搜索樹的節(jié)點刪除
二叉搜索樹的節(jié)點z刪除大致可分為三種情況：
1渔伯、z沒有子節(jié)點顶霞，則簡單刪除z，并修改z父節(jié)點锣吼，用nil代替z稱為父節(jié)點的孩子
2选浑、z有一個孩子節(jié)點c，則用c替代z吐限。
3鲜侥、z有兩個孩子節(jié)點，則需找出z 的后繼節(jié)點诸典。z的后繼節(jié)點必然位于z的右子樹當(dāng)中描函，且為右子樹的最小關(guān)鍵字節(jié)點崎苗。

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

/******************************************************
 *              二叉搜索樹
 ******************************************************/

/******************************************************
 * data structure and definition
 ******************************************************/

typedef int ElemType;

typedef struct TNode
{
    ElemType key;
    struct TNode *parent;
    struct TNode *left;
    struct TNode *right;
}TNode,*Tree;

typedef enum{
    OK = 0,
    ERROR = -1
}Status;

/******************************************************
 * function     : tree_destroy
 * description  : 銷毀一個以T節(jié)點為根節(jié)點的樹
 * input        : Tree *T
 * output       : Tree *T
 * return value : Status(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-04-22
 *******************************************************/

Status tree_destroy(Tree *T){
    if (*T){
        TNode* left = (*T)->left;
        TNode* right = (*T)->right;
        free(*T);
        *T = NULL;
        tree_destroy(&left);
        tree_destroy(&right);
        return OK;
    }
    return ERROR;
}

/******************************************************
 * function     : tree_search
 * description  : 尋找關(guān)鍵字值為key的節(jié)點
 * input        : Tree T,ElemType key
 * output       : N/A
 * return value : TNode* T
 * author       : HanyoungXue
 * date         : 2018-04-22
 ******************************************************/

TNode* tree_search(Tree T,ElemType key){
    if(T==NULL || key==T->key){
        return T; 
    }
    if(key<T->key){
        return tree_search(T->left,key);
    }else{
        return tree_search(T->right,key);
    }
}

/*******************************************************
 * function     : tree_in_order_traverse
 * description  : 中序遍歷輸出以節(jié)點T為根節(jié)點的樹
 * input        : Tree T
 * output       : N/A
 * return value : Status(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-04-22
 *******************************************************/
Status tree_in_order_traverse(Tree T){
    if(T!=NULL){
        tree_in_order_traverse(T->left);
        printf("%d\t",T->key );
        tree_in_order_traverse(T->right);
        return OK;
    }
    return ERROR;
}

/************************************************************
 * function     : tree_min
 * description  : 尋找以節(jié)點T為根節(jié)點的二叉樹的最小關(guān)鍵字值的節(jié)點
 * input        : Tree T
 * output       : N/A
 * return value : TNode* T
 * author       : HanyoungXue
 * date         : 2018-04-22
 ************************************************************/


TNode* tree_min(Tree T){

    while(T->left){
        T = T->left;
    }
    return T;
}


/************************************************************
 * function     : tree_max
 * description  : 尋找以節(jié)點T為根節(jié)點的二叉樹的最大關(guān)鍵字值的節(jié)點
 * input        : Tree T
 * output       : N/A
 * return value : TNode* T
 * author       : HanyoungXue
 * date         : 2018-04-22
 ************************************************************/
TNode* tree_max(Tree T){
    while (T->right){
        T = T->right;
    }
    return T;
}

/************************************************************
 * function     : tree_successor
 * description  : 尋找節(jié)點T的后繼節(jié)點
 * input        : TNode* T
 * output       : N/A
 * return value : TNode* y
 * author       : HanyoungXue
 * date         : 2018-04-22
 ************************************************************/
TNode* tree_successor(TNode* T){
    if(T->right){
        return tree_min(T->right);
    }

    TNode* y = T->parent;
    while(y&&y->right == T){
        T = y->right;
        y = T->parent;
    }
    return y;
}

/************************************************************
 * function     : tree_insert
 * description  : 插入關(guān)鍵字為key的節(jié)點
 * input        : Tree *T,ElemType key
 * output       : N/A
 * return value : Status(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-04-22
 ************************************************************/
Status tree_insert(Tree *T,ElemType key){
    TNode *z = (TNode *)malloc(sizeof(TNode));
    z->key = key;
    z->left = NULL;
    z->right = NULL;

    TNode *y = NULL;
    TNode *x = *T;

    while(x){
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }

    z->parent = y;

    if(!y){
        *T = z;
    }else if(z->key < y->key){
        y->left = z;
    }else{
        y->right = z;
    }

    return OK;
}

/***********************************************************
 * function     : tree_translate
 * description  : 用一棵子樹替換另一棵子樹
 * input        : Tree *T,TNode *u,TNode *v
 * output       : Tree *T
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-04-22
 ***********************************************************/

void tree_translate(Tree *T,TNode *u,TNode *v){
    if(!(u->parent)){
        *T = v;
    }else if(u==u->parent->left){
        u->parent->left = v;
    }else{
        u->parent->right = v;
    }
    if(v){
        v->parent = u->parent;
    }
}

/*********************************************************
 * function     : tree_delete
 * description  : 刪除樹T的某個節(jié)點z
 * input        : Tree *T,TNode *z
 * output       : Tree *T,TNode *z
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-04-22
 *********************************************************/

void tree_delete(Tree *T,TNode *z){
    if(!(z->left)){
        tree_translate(T,z,z->right);
    }else if(!(z->right)){
        tree_translate(T,z,z->left);
    }else{
        TNode *y = tree_min(z->right);
        if(y->parent!=z){
            tree_translate(T,y,y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        tree_translate(T,z,y);
        y->left = z->left;
        y->left->parent = y;
        tree_destroy(&z);
    }
}

int main(int argc, char const *argv[])
{
    Tree T;
    int n;
    scanf("%d",&n);

    for (int i = 0; i < n; ++i){
        ElemType key = rand()%100;
        tree_insert(&T,key);
    }

    tree_in_order_traverse(T);
    printf("\n");

    // printf("%d\n", tree_successor(tree_min(T))->key);

    tree_delete(&T,tree_min(T));

    tree_in_order_traverse(T);
    printf("\n");

    tree_delete(&T,tree_search(T,78));

    tree_in_order_traverse(T);
    printf("\n");
    // tree_destroy(&T);

    // tree_in_order_traverse(T);
    return 0;
}