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

Question

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 **********/

}

Answer 1

节点删除的逻辑有一些问题。下面是代码中存在的问题和需要进行改进的地方：
在函数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;
    }
}