编辑代码

#include <stdio.h>
#include <malloc.h>

typedef struct TreeNode *BinTree;
struct TreeNode{
    int Data;
    BinTree Left;
    BinTree Right;
};

void preOrderTraveser(BinTree t);
BinTree createBinTree();
BinTree FindMin(BinTree BST);
BinTree Delete(int X,BinTree BST);

void preOrderTraveser(BinTree t){
    if(t){
      printf("%d\n",t->Data);
      preOrderTraveser(t->Left);
      preOrderTraveser(t->Right);
    }else{
      return;
    } 
}

//递归查找最小元素
BinTree FindMin(BinTree BST){
    //空的二叉搜索树,返回NULL
    if(!BST){
        return NULL;
    }
    //找到最左叶结点并返回
    else if(!BST->Left){
       return BST;
    }
    //沿左分支继续查找
    else{
        return FindMin(BST->Left);
    }
}

//先序创建二叉树
BinTree createBinTree(){
    BinTree treeNode;
    int data;
    scanf("%d",&data);
    if(data){
        treeNode = (BinTree)malloc(sizeof(BinTree));
        treeNode->Data = data;
        treeNode->Left = createBinTree();
        treeNode->Right = createBinTree();
    }else{
        treeNode = NULL;
    }
    return treeNode;
}

BinTree Delete(int X,BinTree BST){
    BinTree Tmp;
    //树为空
    if(!BST){
        printf("要删除的元素未找到");
    }
    //要删除的元素在左子树,左子树递归删除
    else if(X < BST->Data){
        /*
          左子树删除完之后,左子树根节点可能会发生变化(与插入类似)
          1.有可能左子树的根节点不动,删除在下面(删除叶子结点)
          2.左子树只有一个结点,这个结点就是要删除的结点,所以删除
            之后左子树就变空了,这时返回NULL
          不管返回NULL,还是不动,都把结果return回来,所以这个Delete
          递归函数返回左子树删除了X这个结点之后新的左子树根节点的地址,
          然后赋给BST->Left(这个思想与插入是一样的)
        */
        BST->Left = Delete(X,BST->Left);
    }
        //要删除的元素在右子树,右子树递归删除
        else if(X > BST->Data){
            BST->Right = Delete(X,BST->Right);
        }
        //找到了要删除的结点,这时有两种情况
        else{
            //被删除结点有左右两个子结点(左右子树都不空)
            if(BST->Left && BST->Right){
                //在右子树中找最小的元素(必然只有一个孩子或者没有孩子)填充删除结点
                Tmp = FindMin(BST->Right);
                //把右子树中最小的元素拷贝到(替代)要删除的结点
                BST->Data = Tmp->Data;
                //然后把右子树的那个结点(最小元素结点)删掉
                BST->Right = Delete(BST->Data,BST->Right);
            }
            //被删除结点有一个或无子结点(这两个分支对于这两种情况都适用)
            else{
                Tmp = BST;
                //有右孩子或无子结点,即左边为空,无左孩子
                if(!BST->Left){
                    BST = BST->Right;
                }
                //有左孩子或无子结点,即右边为空,无右孩子
                else if(!BST->Right){
                    BST = BST->Left;
                }
                free(Tmp);
            }
        }
        return BST;
    }

int main () {
    int X;
    BinTree T = createBinTree();
    printf("请输入要删除的元素:\n");
    scanf("%d",&X);
    BinTree afterDeleteTree = Delete(X,T);
    printf("删除之后的二叉搜索树为:\n");
    preOrderTraveser(afterDeleteTree);
}