关于二叉排序树的删除算法
求帮我看看哪里有问题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);
}
}
这段代码存在两个问题：
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 发表于 2023-12-7 10:25
这段代码存在两个问题：
1. 在 `if(searchbitree(t,e))` 的条件判断中，应该使用 `if(!searchbitree(t,e)) ...
6
页:
[1]