m0_51380098 2021-05-23 21:52 采纳率: 0%
浏览 32

菜狗请教一下这个节点删除哪里有问题

BiTNode* findr(BiTree &T)

{

    if(T==NULL)

        return NULL;

    else

    {

        while(T->rchild!=NULL)

        {

            T=T->rchild;

        }

        return T;

    }

}

BiTNode* del(BiTree &T)

{

    if(T->rchild==NULL&&T->lchild==NULL)

        return NULL;

    else if(T->rchild==NULL&&T->lchild!=NULL)

        return T->lchild;

    else if(T->rchild!=NULL&&T->lchild==NULL)

        return T->rchild;

    else

    {

        BiTree tem;

        tem=findr(T->lchild);

        tem->rchild=T->rchild;

        return T->lchild;

    }

}

status DeleteNode(BiTree &T,KeyType e)

//删除结点。此题允许通过增加务其它函数辅助实现本关任

{

    // 请在这里补充代码,完成本关任务

    /********** Begin *********/

    if(T==NULL)

        return ERROR;

    else

    {

        BiTree p,q,r,t;

        p=T;q=T->lchild;r=T->rchild;

        if(q->data.key==e)

        {

            p->lchild=del(q);free(q);

        }

        else if(r->data.key==e)

        {

            p->rchild=del(r);free(r);

        }

        DeleteNode(T->lchild,e);

        DeleteNode(T->rchild,e);

        return OK;

    }

    /********** End **********/

}

  • 写回答

1条回答 默认 最新

  • 芣苢的成长之路 2023-06-27 14:12
    关注

    节点删除的逻辑有一些问题。下面是代码中存在的问题和需要进行改进的地方:
    在函数findr中,找到右子树最右侧的节点后,直接返回该节点,但没有断开它与父节点的连接。这将导致在删除节点时破坏树的结构。解决方法是在找到最右侧节点后,将其父节点的右子树设置为NULL。
    在函数del中,当要删除的节点同时具有左子树和右子树时,将左子树中最右侧的节点与右子树连接后,返回的却是左子树的根节点。这将导致右子树丢失。解决方法是将左子树中最右侧的节点的右子树指向要删除节点的右子树。
    在函数DeleteNode中,对于要删除的节点的判断有问题。当前的判断条件是q->data.key==e和r->data.key==e,这假设了要删除的节点要么是左子树的根节点,要么是右子树的根节点。然而,实际上要删除的节点可能是根节点本身。在判断时应该考虑到这一点。
    以下是修改后的代码:

    
    BiTNode* findr(BiTree &T)
    {
        if (T == NULL)
            return NULL;
        else
        {
            while (T->rchild != NULL)
            {
                T = T->rchild;
            }
            // 断开找到的最右侧节点与父节点的连接
            T->parent->rchild = NULL;
            return T;
        }
    }
    
    BiTNode* del(BiTree &T)
    {
        if (T->rchild == NULL && T->lchild == NULL)
            return NULL;
        else if (T->rchild == NULL && T->lchild != NULL)
            return T->lchild;
        else if (T->rchild != NULL && T->lchild == NULL)
            return T->rchild;
        else
        {
            BiTree tem;
            tem = findr(T->lchild);
            // 将左子树中最右侧的节点的右子树指向要删除节点的右子树
            tem->rchild = T->rchild;
            return T->lchild;
        }
    }
    
    status DeleteNode(BiTree &T, KeyType e)
    {
        if (T == NULL)
            return ERROR;
        else
        {
            // 要删除的节点可能是根节点本身
            if (T->data.key == e)
            {
                BiTree root = T;
                T = del(T);
                free(root);
            }
            else
            {
                BiTree p, q, r, t;
                p = T;
                q = T->lchild;
                r = T->rchild;
                if (q != NULL && q->data.key == e)
                {
                    p->lchild = del(q);
                    free(q);
                }
                else if (r != NULL && r->data.key == e)
                {
                    p->rchild = del(r);
                    free(r);
                }
                DeleteNode(T->lchild, e);
                DeleteNode(T->rchild, e);
            }
            return OK;
        }
    }
    
    
    评论

报告相同问题?

悬赏问题

  • ¥15 office打开卡退(新电脑重装office系统后)
  • ¥300 FLUENT 火箭发动机燃烧EDC仿真
  • ¥15 【Hadoop 问题】Hadoop编译所遇问题hadoop-common: make failed with error code 2
  • ¥15 vb6.0+webbrowser无法加载某个网页求解
  • ¥15 RPA财务机器人采购付款流程
  • ¥15 计算机图形多边形及三次样条曲线绘制
  • ¥15 根据protues画的图用keil写程序
  • ¥200 如何使用postGis实现最短领规划?
  • ¥15 pyinstaller打包错误
  • ¥20 cesm的气溶胶排放文件