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

乔治爱啃脚趾

求帮我看看哪里有问题

1. status delectbitree(BiTree &t,int e)
   
2. {
   
3.         if(searchbitree(t,e))
   
4.         {
   
5.                 Delect(t);
   
6.                 return OK;
   
7.         }
   
8.         else if(t->data.key>e)
   
9.         {
   
10.                 delectbitree(t->lchild,e);
    
11.         }
    
12.         else
    
13.         {
    
14.                 delectbitree(t->rchild,e);
    
15.         }
    
16.         return OK;
    
17. }
    
18. void Delect(BiTree &p)
    
19. {
    
20.         BiTree q,s;
    
21.         if(!p->rchild){
    
22.                 q=p;
    
23.                 p=p->lchild;
    
24.                 free(q);
    
25.         }
    
26.         else if(!p->lchild){
    
27.                 q=p;
    
28.                 p=p->rchild;
    
29.                 free(q);
    
30.         }
    
31.         else
    
32.         {
    
33.                 q=p->lchild;
    
34.                 s=q->rchild;
    
35.                 while(s!=NULL)
    
36.                 {
    
37.                         q=s;
    
38.                         s=s->rchild;
    
39.                 }
    
40.                 p->data.key=s->data.key;
    
41.                 if(s->lchild){
    
42.                         q->rchild=s->lchild;
    
43.                 }
    
44.                 free(s);
    
45.         }       
    
46. }
    

复制代码

最佳答案

月排行榜 / 总排行榜

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);` 递归调用中，没有进行对函数返回值的处理。应该使用一个变量来接收递归调用的返回值，并根据返回值判断是否需要终止递归。

下面是修改后的代码：

1. status delectbitree(BiTree &t,int e)
2. {
3.     if(!searchbitree(t,e))
4.         {
5.             return OK;
6.         }
8.     return removeNode(t, e);
9. }
11. status removeNode(BiTree &p, int e)
12. {
13.     if(p == NULL)
14.     {
15.         return ERROR; // 找不到要删除的节点
16.     }
17.     else if(p->data.key > e)
18.     {
19.         return removeNode(p->lchild, e); // 递归在左子树中删除节点
20.     }
21.     else if(p->data.key < e)
22.     {
23.         return removeNode(p->rchild, e); // 递归在右子树中删除节点
24.     }
25.     else
26.     {
27.         Delect(p); // 找到了要删除的节点，执行删除操作
28.         return OK;
29.     }
30. }
32. void Delect(BiTree &p)
33. {
34.     BiTree q, s;
36.     if(p->rchild == NULL)
37.     {
38.         q = p;
39.         p = p->lchild;
40.         free(q);
41.     }
42.     else if(p->lchild == NULL)
43.     {
44.         q = p;
45.         p = p->rchild;
46.         free(q);
47.     }
48.     else
49.     {
50.         q = p;
51.         s = q->lchild;
52.         while(s->rchild != NULL)
53.         {
54.             q = s;
55.             s = s->rchild;
56.         }
57.         p->data.key = s->data.key;  
58.         if(q != p)  // 如果 q 不是 p 的直接左孩子，则将 q 的右孩子指向 s 的左孩子
59.         {
60.             q->rchild = s->lchild;
61.         }
62.         else
63.         {
64.             q->lchild = s->lchild;  
65.         }
66.         free(s);
67.     }   
68. }

复制代码

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

以上回复来自 -- 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);` 递归调用中，没有进行对函数返回值的处理。应该使用一个变量来接收递归调用的返回值，并根据返回值判断是否需要终止递归。

下面是修改后的代码：

1. status delectbitree(BiTree &t,int e)
2. {
3.     if(!searchbitree(t,e))
4.         {
5.             return OK;
6.         }
8.     return removeNode(t, e);
9. }
11. status removeNode(BiTree &p, int e)
12. {
13.     if(p == NULL)
14.     {
15.         return ERROR; // 找不到要删除的节点
16.     }
17.     else if(p->data.key > e)
18.     {
19.         return removeNode(p->lchild, e); // 递归在左子树中删除节点
20.     }
21.     else if(p->data.key < e)
22.     {
23.         return removeNode(p->rchild, e); // 递归在右子树中删除节点
24.     }
25.     else
26.     {
27.         Delect(p); // 找到了要删除的节点，执行删除操作
28.         return OK;
29.     }
30. }
32. void Delect(BiTree &p)
33. {
34.     BiTree q, s;
36.     if(p->rchild == NULL)
37.     {
38.         q = p;
39.         p = p->lchild;
40.         free(q);
41.     }
42.     else if(p->lchild == NULL)
43.     {
44.         q = p;
45.         p = p->rchild;
46.         free(q);
47.     }
48.     else
49.     {
50.         q = p;
51.         s = q->lchild;
52.         while(s->rchild != NULL)
53.         {
54.             q = s;
55.             s = s->rchild;
56.         }
57.         p->data.key = s->data.key;  
58.         if(q != p)  // 如果 q 不是 p 的直接左孩子，则将 q 的右孩子指向 s 的左孩子
59.         {
60.             q->rchild = s->lchild;
61.         }
62.         else
63.         {
64.             q->lchild = s->lchild;  
65.         }
66.         free(s);
67.     }   
68. }

复制代码

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

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

sfqxx

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

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

6