问题遇到的现象和发生背景
在用C语言编写二叉排序树的删除函数,输入数据为20 60 10 50,45、30,55和70和25,再调用删除函数Delete删除data为20的结点,最后中序遍历输出删除后的二叉排序树,但是只打印了头两个数据,为什么?
问题相关代码,请勿粘贴截图
#include <stdlib.h>
#include <stdio.h>
typedef int ElemType;
#define OK 1
typedef struct Node
{ ElemType data;
struct Node *lchild;
struct Node *rchild;
}BiTNode,*BiTree;
void insert(BiTree &bst,int key)
{
BiTree p;
if (bst==NULL)
{
p=(BiTree)malloc(sizeof(BiTNode));
p->data=key;
p->lchild=NULL;
p->rchild=NULL;
bst=p;
}
else
if (key<bst->data)
insert(bst->lchild,key);
else
if (key>bst->data)
insert(bst->rchild,key);
}
void creattree(BiTree &bst)
{
int key;
bst=NULL;
printf("请输入若干个元素的关键字,中间用空格分隔,以-1表示结束:\n");
scanf("%d",&key);
while (key!=-1)
{
insert(bst,key);
scanf("%d",&key);
}
}
BiTree search(BiTree bst,int key)
{
if (bst==NULL)
return NULL;
else
if (bst->data==key)
return bst;
else
if (key<bst->data)
return search(bst->lchild,key);
else
return search(bst->rchild,key);
}
BiTree FindMin(BiTree &t){
if(t!=NULL){
while(t->lchild !=NULL){
t=t->lchild ;
}
}
return t;
}
BiTree FindMax(BiTree &t){
if(t!=NULL){
while(t->rchild !=NULL){
t=t->rchild ;
}
}
return t;
}
void DeleteMin(BiTree &t){
if(t==NULL){
printf("EMPTY TREE!");
return ;
}
else if(t->lchild !=NULL){
DeleteMin(t->lchild );
}
else if(t->lchild ==NULL){
BiTNode *tmp=t;
t=t->rchild ;
delete tmp;
}
}
void Delete(BiTNode * &t,int key){
if(t==NULL){
printf("该数据不存在,无法删除!");
return ;
}
if(key<t->data ) Delete(t->lchild,key);
else if(key>t->data ) Delete(t->rchild,key);
else if(t->lchild !=NULL&&t->rchild !=NULL){
printf("查找成功,将元素从二叉排序树中删除!\n");
printf("被删除的元素为:%d",t->data );
t->data =FindMin(t->rchild )->data ;
DeleteMin(t->rchild );
}
else {
BiTNode *tmp=t;
t=(t->lchild !=NULL)?t->lchild :t->rchild ;
printf("查找成功,将元素从二叉排序树中删除!\n");
printf("被删除的元素为:%d",tmp->data);
delete tmp;
}
}
ElemType InOrderTraverse(BiTree T) {
if(T){
InOrderTraverse(T->lchild);
printf("%d ",T->data);
InOrderTraverse(T->rchild);
}
return OK;
}
int main(){
BiTree bst,pd;
ElemType num;
creattree(bst);
printf("中序遍历二叉排序树的结果如下:\n");
InOrderTraverse(bst);
printf("\n请输入要查找的元素值:");
scanf("%d",&num);
pd=search(bst,num);
if(!pd){
printf("查找失败,将元素插入二叉排序树!\n");
insert(bst,num);
printf("再次中序遍历二叉排序树!\n");
InOrderTraverse(bst);
}
else printf("该数据存在二叉排序树中!");
printf("\n请输入要查找的元素值:");
scanf("%d",&num);
Delete(bst,num);
printf("\n再次中序遍历二叉排序树!\n");
InOrderTraverse(bst);
printf("\n");
return 0;
}