关于创建一个二叉排序树

乔治爱啃脚趾

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

#include<stdio.h>
#include<stdlib.h>
#define stack_init_size 100
#define OK 1 
#define ERROR 0
typedef int status;
typedef int KeyType;
typedef struct {
    KeyType  key;    // 关键字域
} TElemType;
typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode  *lchild, *rchild;    // 左右孩子指针
} BiTNode, *BiTree;
void initbitree(BiTree &t)
{
        t=(BiTNode*)malloc(sizeof(BiTNode));
        t->data.key=NULL;
        t->lchild=NULL;
        t->rchild=NULL;
}

status creatbitree(BiTree &t,int e)
{
        BiTree s,p;
        s=(BiTNode*)malloc(sizeof(BiTNode));
        s->data.key=e;s->lchild=s->rchild=NULL;
        if(!t){
                t=s;
        }
        else
        {
                if(e>t->data.key){
                        t->rchild=s;
                }
                else{
                        t->lchild=s;
                }
                return OK;
        }
        
}
void InOrder(BiTree t)
{
        if(t!=NULL)
        {
                InOrder(t->lchild);
                printf("%d ",t->data.key);
                InOrder(t->rchild);
        }
}
int main()
{
        BiTree t;
        int e=1;
        initbitree(t);
        printf("请输入一串数字，以数字0代表结束：");        
        scanf("%d",&e);
        while(e!=0){
                creatbitree(t,e);
                scanf("%d",&e);
        }
        InOrder(t);
        
}

FishC_GPT

代码中存在几个问题：

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

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

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

修改后的代码如下：

#include <stdio.h>#include <stdlib.h>#define stack_init_size 100#define OK 1 #define ERROR 0typedef int status;typedef int KeyType;typedef struct {    KeyType  key;    // 关键字域} TElemType;typedef struct BiTNode { // 结点结构    TElemType      data;    struct BiTNode  *lchild, *rchild;    // 左右孩子指针} BiTNode, *BiTree;void initbitree(BiTree &t){    t=(BiTNode*)malloc(sizeof(BiTNode));    t->data.key=0;    t->lchild=NULL;    t->rchild=NULL;}status creatbitree(BiTree &t,int e){    if(!t){        t=(BiTNode*)malloc(sizeof(BiTNode));        t->data.key=e;        t->lchild=NULL;        t->rchild=NULL;    }    else    {        if(e>t->data.key){            return creatbitree(t->rchild,e);        }        else{            return creatbitree(t->lchild,e);        }    }    return OK;}void InOrder(BiTree t){    if(t!=NULL)    {        InOrder(t->lchild);        printf("%d ",t->data.key);        InOrder(t->rchild);    }}int main(){    BiTree t;    int e=1;    initbitree(t);    printf("请输入一串数字，以数字0代表结束：");        scanf("%d",&e);    while(e!=0){        creatbitree(t,e);        scanf("%d",&e);    }    InOrder(t);}

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

以上回复来自 -- 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官方接口），如未能正确解答您的问题，请继续追问。