#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){
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){
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);
}