C语言——二叉搜索树

性质：
设x为二叉搜索树上的节点，如果y为x的左子树上的节点，则有y.key<=x.key；如果y为x的右子树上的节点，则有y.key>x.key。

二叉搜索树的节点删除
二叉搜索树的节点z删除大致可分为三种情况：
1、z没有子节点，则简单删除z，并修改z父节点，用nil代替z称为父节点的孩子
2、z有一个孩子节点c，则用c替代z。
3、z有两个孩子节点，则需找出z 的后继节点。z的后继节点必然位于z的右子树当中，且为右子树的最小关键字节点。

#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节点为根节点的树
 * 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  : 寻找关键字值为key的节点
 * 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  : 中序遍历输出以节点T为根节点的树
 * 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  : 寻找以节点T为根节点的二叉树的最小关键字值的节点
 * 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  : 寻找以节点T为根节点的二叉树的最大关键字值的节点
 * 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  : 寻找节点T的后继节点
 * 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  : 插入关键字为key的节点
 * 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的某个节点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;
}