C++实现的BST插入递增数值时运行失败是什么原因？

核心原因是递归实现的二叉搜索树在插入有序序列时发生栈溢出，具体逻辑如下：

1. 普通二叉搜索树插入完全有序的递增/递减序列时，会直接退化成单链表结构：你插入的每个新元素都比当前树中所有元素大，只会不断向右子树延伸，树的深度等于节点总数。
2. 你的insert函数是递归实现的，每插入一个节点就会触发等于当前树深度的递归调用层级：插入第50000个节点时，需要递归调用insert函数50000层。
3. 操作系统默认给程序分配的栈空间非常有限，Windows下默认栈大小为1MB，Linux下通常为8MB，每层递归调用需要存储参数、返回地址等栈帧数据，大约到4万~5万层递归就会耗尽栈空间，触发程序崩溃，自然不会执行到打印done的逻辑。

为什么修改后的代码可以正常运行？ #

修改后的插入逻辑是交替插入q+i和q-i，构建出的二叉搜索树是近似平衡的结构：根节点是40000，左右子树的节点数几乎相等，8万个节点的树深度仅为log₂(80000) ≈ 17层，递归调用深度最高只有17层，完全不会触及栈空间上限，因此可以正常运行结束。

• 优先将递归实现的insert、find函数改为迭代实现，完全不依赖栈空间，从根源避免栈溢出问题
• 如果你需要维持递归实现，可以将普通二叉搜索树替换为自平衡二叉搜索树（如AVL树、红黑树），保证树的深度始终维持在O(logn)级别，递归深度不会超过30层（即使节点数达到10亿）
• 不推荐修改编译器配置扩大栈大小，该方案不跨平台，且会带来额外的资源浪费

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