关于创建一个二叉排序树

乔治爱啃脚趾

创建一颗二叉排序树后中序输出，可以帮我看看哪里出问题了吗？

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #define stack_init_size 100
   
4. #define OK 1
   
5. #define ERROR 0
   
6. typedef int status;
   
7. typedef int KeyType;
   
8. typedef struct {
   
9.     KeyType  key;    // 关键字域
   
10. } TElemType;
    
11. typedef struct BiTNode { // 结点结构
    
12.     TElemType      data;
    
13.     struct BiTNode  *lchild, *rchild;    // 左右孩子指针
    
14. } BiTNode, *BiTree;
    
15. void initbitree(BiTree &t)
    
16. {
    
17.         t=(BiTNode*)malloc(sizeof(BiTNode));
    
18.         t->data.key=NULL;
    
19.         t->lchild=NULL;
    
20.         t->rchild=NULL;
    
21. }
    
22. 
    
23. status creatbitree(BiTree &t,int e)
    
24. {
    
25.         BiTree s,p;
    
26.         s=(BiTNode*)malloc(sizeof(BiTNode));
    
27.         s->data.key=e;s->lchild=s->rchild=NULL;
    
28.         if(!t){
    
29.                 t=s;
    
30.         }
    
31.         else
    
32.         {
    
33.                 if(e>t->data.key){
    
34.                         t->rchild=s;
    
35.                 }
    
36.                 else{
    
37.                         t->lchild=s;
    
38.                 }
    
39.                 return OK;
    
40.         }
    
41.        
    
42. }
    
43. void InOrder(BiTree t)
    
44. {
    
45.         if(t!=NULL)
    
46.         {
    
47.                 InOrder(t->lchild);
    
48.                 printf("%d ",t->data.key);
    
49.                 InOrder(t->rchild);
    
50.         }
    
51. }
    
52. int main()
    
53. {
    
54.         BiTree t;
    
55.         int e=1;
    
56.         initbitree(t);
    
57.         printf("请输入一串数字，以数字0代表结束：");       
    
58.         scanf("%d",&e);
    
59.         while(e!=0){
    
60.                 creatbitree(t,e);
    
61.                 scanf("%d",&e);
    
62.         }
    
63.         InOrder(t);
    
64.        
    
65. }
    

复制代码

FishC_GPT

代码中存在几个问题：

1. 在`#include`后缺少头文件名。

2. `initbitree()`函数中，初始化树时应该将`data.key`赋值为0，而不是`NULL`。

3. 在`creatbitree()`函数中，在插入结点时忽略了对当前结点的更新。

修改后的代码如下：

1. #include <stdio.h>
2. #include <stdlib.h>
3. #define stack_init_size 100
4. #define OK 1
5. #define ERROR 0
6. typedef int status;
7. typedef int KeyType;
8. typedef struct {
9.     KeyType  key;    // 关键字域
10. } TElemType;
11. typedef struct BiTNode { // 结点结构
12.     TElemType      data;
13.     struct BiTNode  *lchild, *rchild;    // 左右孩子指针
14. } BiTNode, *BiTree;
16. void initbitree(BiTree &t)
17. {
18.     t=(BiTNode*)malloc(sizeof(BiTNode));
19.     t->data.key=0;
20.     t->lchild=NULL;
21.     t->rchild=NULL;
22. }
24. status creatbitree(BiTree &t,int e)
25. {
26.     if(!t){
27.         t=(BiTNode*)malloc(sizeof(BiTNode));
28.         t->data.key=e;
29.         t->lchild=NULL;
30.         t->rchild=NULL;
31.     }
32.     else
33.     {
34.         if(e>t->data.key){
35.             return creatbitree(t->rchild,e);
36.         }
37.         else{
38.             return creatbitree(t->lchild,e);
39.         }
40.     }
41.     return OK;
42. }
44. void InOrder(BiTree t)
45. {
46.     if(t!=NULL)
47.     {
48.         InOrder(t->lchild);
49.         printf("%d ",t->data.key);
50.         InOrder(t->rchild);
51.     }
52. }
54. int main()
55. {
56.     BiTree t;
57.     int e=1;
58.     initbitree(t);
59.     printf("请输入一串数字，以数字0代表结束：");   
60.     scanf("%d",&e);
61.     while(e!=0){
62.         creatbitree(t,e);
63.         scanf("%d",&e);
64.     }
65.     InOrder(t);
66. }

复制代码

请尝试运行代码，看是否解决了问题。

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

乔治爱啃脚趾

FishC_GPT 发表于 2023-12-6 20:36
代码中存在几个问题：

1. 在`#include`后缺少头文件名。

这里的return creatbitree(t->rchild,e)是什么意思啊

FishC_GPT

乔治爱啃脚趾 发表于 2023-12-06 20:55
这里的return creatbitree(t->rchild,e)是什么意思啊

`return creatbitree(t->rchild,e)`的意思是在当前结点的右子树上继续递归调用`creatbitree()`函数，将插入节点的值和右子树作为参数传入。这样可以将新节点插入到正确的位置上。

在二叉排序树中，比当前结点值大的元素需要插入到右子树上，因此需要递归调用`creatbitree()`函数，并将当前节点的右子树和待插入元素作为参数传入。

同理，`return creatbitree(t->lchild,e)`的意思是在当前结点的左子树上继续递归调用`creatbitree()`函数，将插入节点的值和左子树作为参数传入。

通过不断地递归调用`creatbitree()`函数，并根据比较结果选择递归调用的方向，最终将新节点插入到正确的位置上，实现了二叉排序树的构建。

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