struct BSTree()
{
int data;
struct BSTree *lchild;
struct BSTree *rchild;
};
void deletet(struct BSTree **t)
{
if(((*t)->lchild==NULL)&&((*t)->rchild==NULL))
(*t)=NULL;
else if((*t)->lchild==NULL)
(*t)=(*t)->rchild;
else if((*t)->rchild==NULL)
(*t)=(*t)->lchild;
else
{
struct BSTree *q=(*t),*s=(*t)->lchild;
while(s->rchild!=NULL)
{
q=s;
s=s->rchild;
}
(*t)->data=s->data;
if(q!=(*t))
q->rchild=s->lchild;
else
q->lchild=s->lchild;
}
}
在主函数中:
t=search(root,key); //已经找到要删除的结点,为t
deletet(&t); //调用删除结点t的函数
上述代码可以成功删除左右孩子结点都不为空的结点,但是不能删除只有左孩子结点的结点,也不能删除只有右孩子的结点,没有孩子结点的结点也不能删除,这是为什么?