C语言实现二叉搜索树插入5万以上数据崩溃无法输出到文件如何解决

问题根本原因 #

你判断的崩溃位置有误，当前插入逻辑本身是迭代实现，不会触发栈溢出，崩溃实际发生在调用递归中序遍历函数的阶段，核心诱因有两个：

• 插入序列为严格递增的正整数：普通无自平衡策略的二叉搜索树插入有序序列时会直接退化为单链表结构，树的高度等于节点总数，插入5万节点时树高就为5万。
• 递归实现的中序遍历触发栈溢出：函数递归调用时会将栈帧压入程序栈，而操作系统默认给程序分配的栈空间通常仅为1_{8MB，每层递归栈帧约为几十个字节，当递归深度达到4}5万时就会耗尽栈空间触发程序崩溃，和你观察到的插入到4~5万时崩溃的现象完全吻合。

可落地的解决方案 #

方案1：将中序遍历改为迭代实现（改造成本最低，最快满足10万节点需求） #

不需要修改BST结构和插入逻辑，只需要把递归遍历换成自己在堆上实现的栈来做遍历，堆空间足够支撑10万级别的节点存储，示例代码如下：

void inorderTraversalIterative(struct BSTREE* root, FILE *fp) {
    // 用动态数组模拟栈，堆上分配不会触发栈溢出
    struct BSTREE** stack = malloc(100000 * sizeof(struct BSTREE*));
    int top = -1;
    struct BSTREE* curr = root;

    while (curr != NULL || top != -1) {
        // 遍历到最左节点
        while (curr != NULL) {
            stack[++top] = curr;
            curr = curr->left;
        }

        curr = stack[top--];
        fprintf(fp, "%lld\n", curr->key);
        curr = curr->right;
    }
    free(stack);
}

替换原来的递归遍历函数即可，无需其他修改即可支持10万+节点的遍历。

方案2：替换为自平衡二叉搜索树（长期优化方案） #

普通BST插入有序序列的时间复杂度为O(n²)，当节点数到10万时插入效率会非常低，换成AVL树或红黑树等自平衡BST结构后，树高会稳定在log₂(n)级别，10万节点的树高仅为17左右，即使使用递归遍历也不会触发栈溢出，同时插入时间复杂度稳定为O(nlogn)，性能提升非常明显。

不推荐的临时方案：调整系统栈大小 #

部分操作系统允许在编译时调整程序栈大小，比如Linux下用gcc编译时加-Wl,--stack=16777216参数可以把栈大小调到16MB，可临时支撑5万层递归，但该方案可移植性差，不建议生产环境使用。

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