猴-儿
2016-09-15 11:10
采纳率: 40%
浏览 2.9k
已采纳

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

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

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

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

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • kes55 2016-09-15 11: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);       
        }
    }
    
    已采纳该答案
    打赏 评论
  • 猴-儿 2016-09-16 03: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的函数

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

    打赏 评论

相关推荐 更多相似问题