2 sinat 36147557 sinat_36147557 于 2016.09.15 19:10 提问

C语言实现:二叉排序树结点的删除

struct BSTree
{
int data;
struct BSTree *lchild;
struct BSTree *rchild;
};

若p为二叉排序树t中的一个叶子结点,如何在t中把p结点删除??
t为BST的根结点,要求最后遍历t得到的树中不含p

我知道结点的删除在结构体中加一个struct BSTree *parents; 可以成功实现,但想知道如果没有定义指向双亲结点的指针,如何删除叶子节点?

2个回答

kes55
kes55   2016.09.15 19:46
已采纳

void DeleTree(BTree T,int data)
{
BTree *p=T,*f=T,temp;
/
寻找需要删除的点*/
while(*p)
{
if((*p)->key==data)
break;
else if(data>(*p)->key)

{
f=p;
(*p)=(*p)->rchild;
}
else if(data<(*p)->key)
{
f=p;
(*p)=(*p)->lchild;
}
}/*找到后,p为目标结点,f为其父结点*/

if(!(*p))                          //找不到
    printf("错误,无此数据");
//以下为找到的情况
else if( (*p)->lchild==NULL )      //情况1:p无左子树  
{
    if( (*f)->rchild=(*p) )        //p为f的右子树
        (*f)->rchild=(*p)->rchild; //直接将p的右子树连接在f的右子树上
    else if( (*f)->lchild=(*p) )   //p为f的左子树
        (*f)->lchild=(*p)->rchild; //直接将p的右子树连接在f的右子树上
    free(*p);
}
else if( (*p)->rchild==NULL )      //情况2:p无右子树
{
    if( (*f)->rchild=(*p) )        //p为f的右子树
        (*f)->rchild=(*p)->lchild; //直接将p的左子树连接在f的右子树上
    else if( (*f)->lchild=(*p) )   //p为f的左子树
        (*f)->lchild=(*p)->lchild; //直接将p的左子树连接在f的右子树上
    free(*p);
}
else if( (*p)->lchild==NULL && (*p)->rchild==NULL )//情况3:p无左子树和右子树
{
    if( (*f)->rchild=(*p) )                        //p为f的右子树
        (*f)->rchild=NULL;                         //f的右子树直接置空
    else if( (*f)->lchild=(*p) )                   //p为f的左子树    
        (*f)->lchild=NULL;                         //f的右子树直接置空
    free(*p);
}
else if( (*p)->lchild!=NULL && (*p)->rchild!=NULL )//情况4:p有左子树和右子树
{
    if( (*f)->rchild=(*p) )                        //p为f的右子树
    {
        temp=(*p)->lchild;                         //temp为p的左子树
        while(temp->rchild)                        //在temp的右支寻找空位
            temp=temp->lchild;
        temp->rchild=(*p)->rchild;                 //将p的右子树连接在temp的右子树上
        (*f)->rchild=(*p)->lchild;                 //再将p的左子树连接在f的左子树上
        free(*p);
    }
    else if( (*f)->lchild=(*p) )
    {
        temp=(*p)->lchild;
        while(temp->rchild)
            temp=temp->lchild;
        temp->rchild=(*p)->rchild;
        (*f)->lchild=(*p)->lchild;
        free(*p);       
    }
}
sinat_36147557
sinat_36147557   2016.09.16 11:54

追问:

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的函数

上述代码可以成功删除左右孩子结点都不为空的结点,但是不能删除只有左孩子结点的结点,也不能删除只有右孩子的结点,没有孩子结点的结点也不能删除,这是为什么?

Csdn user default icon
上传中...
上传图片
插入图片