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递归完全安全单边斜树最坏场景所有节点只有左孩子退化成单链表plaintext1 / 2 / 3 / 4 ... / 100此时递归深度 100每一层都压栈栈帧层层叠加很快占满栈内存直接硬崩溃。举个量化例子STM32假设一次InOrder栈帧占用 20 字节栈总大小 1KB1024B 最大安全递归深度 ≈ 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.sasmStack_Size EQU 0x0400 ; 原0x200(512字节)改成1024字节Keil C51 8 位单片机修改栈大小编译选项 缺陷RAM 资源宝贵加大栈会挤占全局变量、缓冲区内存遇到深度极大的斜树依然有溢出风险治标不治本。四、补充单片机开发规范深度不确定的树、链表、递归逻辑一律禁止用递归递归只允许用于固定极小深度场景深度 10所有深度不可控的遍历二叉树、深度优先搜索 DFS强制手动栈 / 队列迭代实现栈溢出故障极难调试无报错、随机死机、硬件异常中断。极简总结递归二叉树遍历深度越大栈占用越高单边链式二叉树会让递归深度等于节点数单片机小栈必然溢出单片机正式项目必须替换为非递归迭代写法用全局数组手动模拟栈规避栈溢出。
