二叉搜索树插入多元素时节点覆盖问题求助

你的代码核心问题在于insert_tree函数的分支逻辑缺失返回语句，导致递归过程中出现未定义行为，进而引发节点被覆盖的现象。另外search_tree函数也存在类似的递归返回问题，同时main函数中手动创建节点的代码可以优化。

具体问题点： #

• insert_tree函数返回值缺失：在处理number < root->number和number > root->number的分支时，你正确递归插入了子节点，但没有返回当前的root节点。C语言中，有返回值的函数若某个分支无return语句，会返回随机垃圾值，破坏递归过程中的节点引用关系，导致后续插入的节点覆盖已有节点。
• search_tree函数递归返回错误：递归搜索左/右子树时，未返回递归调用的结果，导致搜索功能无法正确返回查找结果。
• main函数手动创建节点冗余：可直接使用new_node函数创建根节点，避免重复的内存分配和初始化代码。

修复后的代码： #

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>  // 补充头文件，支持bool类型

typedef struct node
{
    int number;
    struct node* left;  // 结构体内部需用struct node*，typedef在结构体定义后才生效
    struct node* right;
} node;

void print_tree(node* root);
void free_tree(node* root);
bool search_tree(node* root, int number);
node* insert_tree(node* root, int number);
node* new_node(int number);

int main(void)
{
    int number = 0;
    int size = 0;
    printf("请输入要添加到树中的数字数量：\n");
    scanf_s("%d", &size);
    printf("你要添加的数字数量是：%i\n", size);

    node* root = NULL;
    printf("请输入要添加到树中的数字：\n");
    for (int i = 0; i < size; i++)
    {
        scanf_s("%d", &number);
        root = insert_tree(root, number);  // 接收返回值，兼容根节点为空的情况
    }

    printf("树的中序遍历结果为：\n");
    print_tree(root);
    free_tree(root);
    return 0;
}

node* insert_tree(node* root, int number)
{
    if (root == NULL)
    {
        return new_node(number);  // 直接返回新节点，简化代码
    }
    else if (number < root->number)
    {
        root->left = insert_tree(root->left, number);
    }
    else if (number > root->number)
    {
        root->right = insert_tree(root->right, number);
    }
    // 数值相等时不做插入，直接返回原节点
    return root;  // 关键：所有分支都返回当前root节点，保证递归引用正确
}

node* new_node(int number)
{
    node* n = malloc(sizeof(node));
    if (n == NULL)
    {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    n->left = NULL;
    n->right = NULL;
    n->number = number;
    return n;
}

void print_tree(node* root)
{
    if (root != NULL)
    {
        print_tree(root->left);
        printf("%i\n", root->number);
        print_tree(root->right);
    }
}

void free_tree(node* root)
{
    if (root != NULL)
    {
        free_tree(root->left);
        free_tree(root->right);
        free(root);
    }
}

bool search_tree(node* root, int number)
{
    if (root == NULL)
    {
        return false;
    }
    else if (number < root->number)
    {
        return search_tree(root->left, number);  // 返回递归搜索结果
    }
    else if (number > root->number)
    {
        return search_tree(root->right, number);  // 返回递归搜索结果
    }
    else
    {
        return true;
    }
}

修复细节说明： #

1. insert_tree函数：所有分支末尾添加return root;，确保无论哪种情况都返回当前节点的正确引用，修复递归过程中的引用丢失问题，避免节点被覆盖。
2. search_tree函数：递归调用时添加return，保证子树的搜索结果能返回给上层调用，修复搜索功能逻辑错误。
3. main函数：将根节点初始化为NULL，直接通过insert_tree创建根节点，简化代码同时处理了size为0的边界情况。
4. 结构体指针修正：结构体内部的left和right需声明为struct node*，避免编译器报错。
5. 头文件与错误处理优化：补充<stdbool.h>头文件，优化内存分配失败时的错误提示与退出逻辑，使代码更规范。

内容的提问来源于stack exchange，提问作者RomanB