2 sinat 36147557 sinat_36147557 于 2016.09.16 11:58 提问

C语言实现:二叉排序树结点的删除
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的函数

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

1个回答

Chorzen
Chorzen   2016.09.17 12:01

好像看到过一个解释,说的时候只有赋值了的变量才能置为null,本身为null的变量不能置为null,不知道是不是这个原因,
你可以试试判断只有左(右)孩子时清空左(右)孩子。

Chorzen
Chorzen 回复猴-: 又看了下语句,你前面几个else只是把空孩子赋给了*t,并没有进行其他操作
大约一年之前 回复
NeoTalen
NeoTalen 回复猴-: 是的,除了最后一个条件语句是真实操作在树上之外,其他三个语句都没有真实修改到树里面!
大约一年之前 回复
sinat_36147557
sinat_36147557 谢谢,不过我后面想了一下,这个代码应该只是把t变量置为NULL,而不是把主函数中的root的相应结点变成了NULL,也就是相当于没有实质性地改变了输出时用的root指针。不造这样理解对不对
大约一年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片