[已解决]关于二叉排序树的删除算法

乔治爱啃脚趾

求帮我看看哪里有问题

status delectbitree(BiTree &t,int e)
{
        if(searchbitree(t,e))
        {
                Delect(t);
                return OK;
        }
        else if(t->data.key>e)
        {
                delectbitree(t->lchild,e);
        }
        else
        {
                delectbitree(t->rchild,e);
        }
        return OK;
}
void Delect(BiTree &p)
{
        BiTree q,s;
        if(!p->rchild){
                q=p;
                p=p->lchild;
                free(q);
        }
        else if(!p->lchild){
                q=p;
                p=p->rchild;
                free(q);
        }
        else
        {
                q=p->lchild;
                s=q->rchild;
                while(s!=NULL)
                {
                        q=s;
                        s=s->rchild;
                }
                p->data.key=s->data.key;
                if(s->lchild){
                        q->rchild=s->lchild;
                }
                free(s); 
        }        
}

最佳答案

月排行榜 / 总排行榜

FishC_GPT

2023-12-7 10:25:24

这段代码存在两个问题：

1. 在 `if(searchbitree(t,e))` 的条件判断中，应该使用 `if(!searchbitree(t,e))`。因为如果 `searchbitree(t,e)` 返回 `true`，表示找到了要删除的节点，所以应该执行删除操作，并返回 `OK`；而如果返回 `false`，则需要继续递归地在左子树或右子树中查找。所以应该使用取反操作 `!` 来判断是否需要继续查找。

2. 在 `delectbitree(t->lchild,e);` 和 `delectbitree(t->rchild,e);` 递归调用中，没有进行对函数返回值的处理。应该使用一个变量来接收递归调用的返回值，并根据返回值判断是否需要终止递归。

下面是修改后的代码：

status delectbitree(BiTree &t,int e){    if(!searchbitree(t,e))        {            return OK;        }    return removeNode(t, e);}status removeNode(BiTree &p, int e){    if(p == NULL)    {        return ERROR; // 找不到要删除的节点    }    else if(p->data.key > e)    {        return removeNode(p->lchild, e); // 递归在左子树中删除节点    }    else if(p->data.key < e)    {        return removeNode(p->rchild, e); // 递归在右子树中删除节点    }    else    {        Delect(p); // 找到了要删除的节点，执行删除操作        return OK;    }}void Delect(BiTree &p){    BiTree q, s;    if(p->rchild == NULL)    {        q = p;        p = p->lchild;        free(q);    }    else if(p->lchild == NULL)    {        q = p;        p = p->rchild;        free(q);    }    else    {        q = p;        s = q->lchild;        while(s->rchild != NULL)        {            q = s;            s = s->rchild;        }        p->data.key = s->data.key;          if(q != p)  // 如果 q 不是 p 的直接左孩子，则将 q 的右孩子指向 s 的左孩子        {            q->rchild = s->lchild;        }        else        {            q->lchild = s->lchild;          }        free(s);     }   }

这样就修复了上述问题，删除操作应该正常运行了。希望对你有帮助！

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC_GPT

这段代码存在两个问题：

1. 在 `if(searchbitree(t,e))` 的条件判断中，应该使用 `if(!searchbitree(t,e))`。因为如果 `searchbitree(t,e)` 返回 `true`，表示找到了要删除的节点，所以应该执行删除操作，并返回 `OK`；而如果返回 `false`，则需要继续递归地在左子树或右子树中查找。所以应该使用取反操作 `!` 来判断是否需要继续查找。

2. 在 `delectbitree(t->lchild,e);` 和 `delectbitree(t->rchild,e);` 递归调用中，没有进行对函数返回值的处理。应该使用一个变量来接收递归调用的返回值，并根据返回值判断是否需要终止递归。

下面是修改后的代码：

status delectbitree(BiTree &t,int e){    if(!searchbitree(t,e))        {            return OK;        }    return removeNode(t, e);}status removeNode(BiTree &p, int e){    if(p == NULL)    {        return ERROR; // 找不到要删除的节点    }    else if(p->data.key > e)    {        return removeNode(p->lchild, e); // 递归在左子树中删除节点    }    else if(p->data.key < e)    {        return removeNode(p->rchild, e); // 递归在右子树中删除节点    }    else    {        Delect(p); // 找到了要删除的节点，执行删除操作        return OK;    }}void Delect(BiTree &p){    BiTree q, s;    if(p->rchild == NULL)    {        q = p;        p = p->lchild;        free(q);    }    else if(p->lchild == NULL)    {        q = p;        p = p->rchild;        free(q);    }    else    {        q = p;        s = q->lchild;        while(s->rchild != NULL)        {            q = s;            s = s->rchild;        }        p->data.key = s->data.key;          if(q != p)  // 如果 q 不是 p 的直接左孩子，则将 q 的右孩子指向 s 的左孩子        {            q->rchild = s->lchild;        }        else        {            q->lchild = s->lchild;          }        free(s);     }   }

这样就修复了上述问题，删除操作应该正常运行了。希望对你有帮助！

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

sfqxx

FishC_GPT 发表于 2023-12-7 10:25
这段代码存在两个问题：

1. 在 `if(searchbitree(t,e))` 的条件判断中，应该使用 `if(!searchbitree(t,e)) ...

6