二叉搜索树非递归插入代码无输出，请求问题排查帮助

你的代码没有输出的核心原因有三个，下面逐一分析并修复：

1. 根节点传递方式错误 #

insert函数的参数struct node *root是值传递，函数内部对root的修改不会影响main函数里的根节点指针。当初始root为NULL时，第一次插入操作在函数内部创建了新节点，但main里的root依然是NULL，后续所有插入都基于这个无效的空指针，最终中序遍历自然没有输出。

修复方案：让insert函数返回更新后的根节点，或者使用指针的指针传递参数。这里采用返回根节点的方式更简洁直观。

2. 内存分配大小错误 #

getnode函数中malloc(sizeof(struct node *))分配的是指针的大小，而非整个struct node结构体的大小。这会导致内存分配不足，后续访问节点成员时可能出现内存越界，破坏程序数据。

修复方案：改为malloc(sizeof(struct node))，分配正确的结构体内存空间。

3. 插入逻辑遗漏重复值处理 #

原代码中当插入的值与树中已有节点值相等时，循环会无限执行（因为ptr不会移动）。虽然本次测试用例没有重复值，但这是二叉搜索树插入逻辑的必要漏洞修复。

修复方案：添加相等值的判断分支，直接返回原根节点（二叉搜索树通常不允许重复节点）。

修复后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int val;
    struct node *lc, *rc;
};

struct node *getnode(int x)
{
    struct node *new = (struct node *)malloc(sizeof(struct node));
    new->lc = NULL;
    new->rc = NULL;
    new->val = x;
    return new;
}

void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->lc);
        printf("%d ", root->val);
        inorder(root->rc);
    }
}

struct node *insert(struct node *root, int x)
{
    if (root == NULL)
    {
        return getnode(x);
    }
    else
    {
        struct node *ptr1 = NULL;
        struct node *ptr = root;
        while (ptr != NULL)
        {
            if (x < ptr->val)
            {
                ptr1 = ptr;
                ptr = ptr->lc;
            }
            else if (x > ptr->val)
            {
                ptr1 = ptr;
                ptr = ptr->rc;
            }
            else
            {
                // 重复值，直接返回原根节点
                return root;
            }
        }
        struct node *temp = getnode(x);
        if (ptr1->val > temp->val)
            ptr1->lc = temp;
        else
            ptr1->rc = temp;
        return root;
    }
}

int main()
{
    struct node *root = NULL;
    root = insert(root, 75);
    root = insert(root, 85);
    root = insert(root, 25);
    root = insert(root, 12);
    root = insert(root, 13);
    root = insert(root, 15);
    root = insert(root, 100);
    root = insert(root, 105);
    printf("Inorder notation of tree is\n");
    inorder(root);
    return 0;
}

运行结果 #

执行后会输出预期的中序遍历结果：

Inorder notation of tree is
12 13 15 25 75 85 100 105 

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