void InOrder(BinTree root) { if (root == NULL)// 递归出口 return; InOrder(root->lchild); // 自己调用自己，处理左子树 printf("%d ", root->data); InOrder(root- >rchild); // 自己调用自己，处理右子树 }递归的两个必备条件，这里全部具备：
- 递归终止条件（基线条件）：
if(root == NULL) return;当走到空节点时，直接返回，不再继续调用，防止无限循环死递归、栈溢出。 - 递推公式（自己调用自己，缩小问题规模）整棵树的中序遍历 = 左子树中序遍历 + 打印根 + 右子树中序遍历 把 “遍历整棵大树” 拆成 “遍历更小的左、右小树”。
一、根本原理：递归使用的是「系统栈（栈帧）」
递归遍历：
c
运行
void InOrder(BinTree root) { if (root == NULL) return; InOrder(root->lchild); printf("%d ", root->data); InOrder(root->rchild); }每一次InOrder()自调用，单片机都会在全局栈 Stack里分配一块栈帧，保存：
- 形参
root指针 - 函数返回地址
- 函数内部临时变量（printf 缓存、寄存器备份）
栈的致命限制（单片机特性）
PC 电脑栈通常几 MB；单片机栈极小：常见 STM32、8051 默认栈只有512 字节 / 1KB / 2KB。 栈空间是启动文件预先固定分配，不能动态扩容。
二、二叉树深度决定栈占用，不是节点总数
栈消耗只和树的深度有关，和总节点数量无关：
- 平衡完全二叉树：深度很小，比如 1000 个节点深度≈10，递归完全安全；
- 单边斜树（最坏场景）：所有节点只有左孩子，退化成单链表
plaintext
1 / 2 / 3 / 4 ... / 100此时递归深度 = 100，每一层都压栈，栈帧层层叠加，很快占满栈内存，直接硬崩溃。
举个量化例子（STM32）
假设一次InOrder栈帧占用 20 字节，栈总大小 1KB（1024B）： 最大安全递归深度 ≈ 1024 / 20 = 50 层。 如果二叉树深度超过 50，直接栈溢出：程序跑飞、死机、HardFault 硬件错误。
三、单片机中两种解决方案（工程必用）
方案 1：改用非递归遍历（手动堆模拟栈，推荐量产使用）
自己用数组 / 堆内存手动实现栈，不占用系统栈，深度随便多大都不怕。 中序非递归代码（单片机可直接用）：
c
运行
#define MAX_TREE_DEPTH 200 void InOrder_NoRecursion(BinTree root) { BinTreeNode* stack[MAX_TREE_DEPTH]; // 手动栈，放全局/堆，不占函数栈 int top = 0; BinTreeNode* cur = root; while (cur != NULL || top > 0) { // 一路往左压节点 while (cur != NULL) { stack[top++] = cur; cur = cur->lchild; } // 弹出访问 cur = stack[--top]; printf("%d ", cur->data); // 切换右子树 cur = cur->rchild; } }优势：
stack数组定义为全局变量，存在.bss 段，完全不消耗系统栈；- 容量自己定义 200/500，深度再大也不会溢出；
- 无递归调用，无栈帧叠加，嵌入式稳定。
方案 2：加大单片机栈容量（临时折中，不推荐长期）
- STM32：修改启动文件
startup_stm32xxxx.s
asm
Stack_Size EQU 0x0400 ; 原0x200(512字节)改成1024字节- Keil C51 8 位单片机：修改栈大小编译选项 缺陷：
- RAM 资源宝贵，加大栈会挤占全局变量、缓冲区内存；
- 遇到深度极大的斜树，依然有溢出风险，治标不治本。
四、补充单片机开发规范
- 深度不确定的树、链表、递归逻辑，一律禁止用递归；
- 递归只允许用于固定极小深度场景（深度 < 10）；
- 所有深度不可控的遍历（二叉树、深度优先搜索 DFS），强制手动栈 / 队列迭代实现；
- 栈溢出故障极难调试：无报错、随机死机、硬件异常中断。
极简总结
- 递归二叉树遍历深度越大，栈占用越高；
- 单边链式二叉树会让递归深度等于节点数，单片机小栈必然溢出；
- 单片机正式项目必须替换为非递归迭代写法，用全局数组手动模拟栈，规避栈溢出。
