如何通过命令行输入构建C语言二叉搜索树并实现前序遍历

原有代码问题梳理 #

• 相等判断语法错误：search函数中if (root=NULL、main函数中if (num_count = 0)两处把相等判断运算符==写成了赋值运算符=，直接导致逻辑失效
• 终止循环逻辑错误：不能通过判断输入的数值等于EOF结束循环，需要读取scanf的返回值判断是否输入结束
• 指针未初始化：root指针定义时未赋值为NULL，存在野指针崩溃风险
• 输出逻辑错误：打印输入值时错误传入了变量地址，前序遍历输出无分隔符导致所有数字粘连无法识别
• 插入逻辑错误：未接收insert函数的返回值，根节点为空时插入的第一个节点无法正确赋值给root

修复后完整代码 #

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data; //存储整数的节点
    struct node *left_child; // 左子节点
    struct node *right_child; // 右子节点
};

struct node* search(struct node *root, int x)
{
    // root为空或者当前节点值等于查找值，返回当前节点
    if (root == NULL || root->data == x)
        return root;
    else if (x > root->data)
        return search(root->right_child, x);
    else
        return search(root->left_child, x);
}

struct node* find_minimum(struct node *root)
{
    if(root == NULL)
        return NULL;
    else if(root->left_child != NULL)
        return find_minimum(root->left_child);
    return root;
}

struct node* new_node(int x)
{
    struct node *p;
    p = malloc(sizeof(struct node));
    p->data = x;
    p->left_child = NULL;
    p->right_child = NULL;

    return p;
}

struct node* insert(struct node *root, int x)
{
    if(root == NULL)
        return new_node(x);
    else if(x < root->data)
        root->left_child = insert(root->left_child,x);
    else
        root->right_child = insert(root->right_child, x);
    return root;
}

void preorder(struct node *root)
{
    if(root != NULL)
    {
        printf("%d ", root->data);
        preorder(root->left_child);
        preorder(root->right_child);
    }
}


int main()
{
    struct node *root = NULL;
    int number;
    // 循环读取输入直到结束
    while(scanf("%d", &number) != EOF)
    {
        printf("输入值：%d\n", number);
        root = insert(root, number);
    }
    printf("前序遍历结果：");
    preorder(root);
    printf("\n");
    return 0;
}

使用说明 #

编译运行程序后，直接在命令行输入整数，用空格或者换行分隔多个数值即可；输入结束后按Ctrl+D（Linux/macOS系统）或者Ctrl+Z（Windows系统），程序就会输出二叉搜索树的前序遍历结果。

内容的提问来源于stack exchange，提问作者이건웅