论坛 › 数据结构与算法 › 关于创建一个二叉排序树

乔治爱啃脚趾 发表于 2023-12-6 20:36:01

关于创建一个二叉排序树

创建一颗二叉排序树后中序输出，可以帮我看看哪里出问题了吗？
#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 {
    KeyTypekey;    // 关键字域
} 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 发表于 2023-12-6 20:36:55

代码中存在几个问题：

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 0
typedef int status;
typedef int KeyType;
typedef struct {
    KeyTypekey;    // 关键字域
} 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官方接口），如未能正确解答您的问题，请继续追问。

乔治爱啃脚趾 发表于 2023-12-6 20:55:26

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

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

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

FishC_GPT 发表于 2023-12-6 20:58:13

乔治爱啃脚趾 发表于 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官方接口），如未能正确解答您的问题，请继续追问。

查看完整版本: 关于创建一个二叉排序树