15.6二叉排序树删除实战

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


typedef int KeyType;
typedef struct BSTNode{
    KeyType key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;

//非递归的创建二叉查找数
int BST_Insert(BiTree &T,KeyType k)
{
    BiTree TreeNew=(BiTree) calloc(1,sizeof (BSTNode));//新节点申请空间
    TreeNew->key=k;  //把值放入
    if(NULL==T)      //树为空，新结点作为树的根
    {
        T=TreeNew;
        return 0;
    }
    BiTree p=T,parent;   //用来查找树
    while (p)
    {
        parent=p;    //parent用来存p的父亲
        if(k>p->key)
        {
            p=p->rchild;
        } else if(k<p->key)
        {
            p=p->lchild;
        } else
        {
            return -1;   //相等元素不放入查找树
        }
    }
    //判断放到父亲左边还是右边
    if(k>parent->key)
    {
        parent->rchild=TreeNew;
    } else{
        //放到父亲左边
        parent->lchild=TreeNew;
    }
    return 0;
}


void Creat_BST(BiTree &T,KeyType *str,int len)
{
    int i;
    for (i = 0; i < len; i++) {
        BST_Insert(T,str[i]);    // 把某一个结点放入二叉查找树
    }
}

void InOrder(BiTree T)
{
    if(T!=NULL)
    {
        InOrder(T->lchild);
        printf("%3d",T->key);
        InOrder(T->rchild);
    }
}

BiTree BST_Search(BiTree T,KeyType k,BiTree &parent)
{
    parent=NULL;
    while (T!=NULL&&k!=T->key)
    {
        parent=T;
        if(k>T->key)
        {
            T=T->rchild;
        } else{
            T=T->lchild;
        }
    }
    return T;
}

//二叉排序树删除
void DeleteNode(BiTree &root,KeyType x)
{
    if(NULL==root)
    {
        return;
    }
    if(root->key>x)
    {
        //当前结点大于要删除的结点，往左子树找
        DeleteNode(root->lchild,x);
    }else if(root->key<x)
    {
        //当前结点小于要删除的结点，往右子树找
        DeleteNode(root->rchild,x);
    } else{
        //找到了要删除的结点
        if(root->lchild==NULL)
        {
            //左子树为空，右子树直接顶上去
            BiTree tempNode=root;
            root=root->rchild;
            free(tempNode);
        } else if(root->rchild==NULL)
        {
            //右子树为空，左子树直接顶上去
            BiTree tempNode=root;
            root=root->lchild;
            free(tempNode);
        } else{
            //两边都不为空
            /*一般的删除策略是左子树的最大数据或者右子树的最小数据代替要删除的结点
            (这里采用查找左子树最大数据来代替，最大数据是左子树的最右结点)*/
            BiTree tempNode=root->lchild;
            while (tempNode->rchild!=NULL)
            {
                tempNode=tempNode->rchild;
            }
            root->key=tempNode->key;     //把tempNode对应的值替换到要删除的值的位置上
            DeleteNode(root->lchild,tempNode->key);   //在左子树中找到tempNode的值，把其删除
        }
    }
}

//二叉排序树的创建，中序遍历，查找
int main() {
    BiTree T = NULL;   //树根
    KeyType str[7] = {54, 20, 66, 40, 28, 79, 58};  //将要进入二叉排序树的元素值
    Creat_BST(T, str, 7);
    InOrder(T);    //中序二叉查找树，由小到大
    printf("\n");
    BiTree search, parent;
    search = BST_Search(T, 40, parent);
    if (search)
    {
        printf("find key %d\n",search->key);
    } else{
        printf("not find\n");
    }
    DeleteNode(T,54);
    InOrder(T);
    printf("\n");
    return 0;
}