摘要《大话数据结构》第6章讲树时把二叉树的遍历作为重点。书中主要给出了递归写法但对非递归实现只是点到为止。结合《C Primer Plus》里对指针、动态内存和栈的讲解本文把前序、中序、后序的递归与非递归版本都完整实现了一遍并重点分析了它们在空间复杂度和实现难度上的本质差异。文末附有完整的测试代码和运行结果可直接复制运行。1. 二叉树节点定义采用最经典的二叉链表结构每个节点包含数据域和左右孩子指针#include iostream #include stack #include vector using namespace std; struct BiNode { int data; BiNode *lchild, *rchild; BiNode(int d) : data(d), lchild(nullptr), rchild(nullptr) {} };这里用 C 的构造函数初始化列表来初始化成员这也是《C Primer Plus》第10章强调的最佳实践在进入构造函数体之前就完成初始化既高效又避免了未定义行为。左右孩子指针初始化为nullptr明确表示当前没有子节点。2. 递归遍历书中标准写法递归是最自然的表达方式本质是利用系统栈保存“回去的路”。三种递归遍历的代码非常简洁// 前序根 → 左 → 右 void PreOrder(BiNode* T) { if (T nullptr) return; cout T-data ; PreOrder(T-lchild); PreOrder(T-rchild); } // 中序左 → 根 → 右 void InOrder(BiNode* T) { if (T nullptr) return; InOrder(T-lchild); cout T-data ; InOrder(T-rchild); } // 后序左 → 右 → 根 void PostOrder(BiNode* T) { if (T nullptr) return; PostOrder(T-lchild); PostOrder(T-rchild); cout T-data ; }时间复杂度O(n)每个节点恰好访问一次。空间复杂度O(h)h 为树高。最坏情况退化为链表时为 O(n)平衡时为 O(log n)。递归写法虽然优雅但在树非常高时存在栈溢出风险而且无法直接中途停止或做更复杂的控制。因此非递归实现仍然有学习价值。3. 非递归前序遍历前序非递归相对简单只需要一个栈来模拟系统栈的行为void PreOrderNonRecursive(BiNode* T) { if (T nullptr) return; stackBiNode* s; s.push(T); while (!s.empty()) { BiNode* p s.top(); s.pop(); cout p-data ; // 先访问根 // 注意先压右再压左这样出栈时才是左先右后 if (p-rchild) s.push(p-rchild); if (p-lchild) s.push(p-lchild); } }核心思路前序是“根 → 左 → 右”栈是后进先出。为了让左孩子先出栈必须先把右孩子压入栈底再把左孩子压在栈顶。这样每次弹出栈顶时自然先访问左子树再访问右子树。4. 非递归中序遍历最经典中序非递归是理解“用栈模拟递归”的最佳例子void InOrderNonRecursive(BiNode* T) { stackBiNode* s; BiNode* p T; while (p || !s.empty()) { if (p) { s.push(p); // 一路向左走到底 p p-lchild; } else { p s.top(); s.pop(); cout p-data ; // 访问根 p p-rchild; // 转向右子树 } } }这个过程完美对应了递归中“先处理左子树 → 访问根 → 再处理右子树”的执行顺序。指针 p 一直沿着左孩子走把沿途节点全部压栈当 p 为空时说明左子树已经走完此时弹出栈顶节点访问然后把 p 指向其右孩子继续同样的流程。5. 非递归后序遍历难度最高后序需要知道“左子树和右子树都已经访问完毕”才能访问根因此通常需要额外记录上一次访问的节点void PostOrderNonRecursive(BiNode* T) { if (T nullptr) return; stackBiNode* s; BiNode* p T; BiNode* lastVisited nullptr; // 记录上一次访问的节点 while (p || !s.empty()) { if (p) { s.push(p); p p-lchild; // 优先走左边 } else { BiNode* top s.top(); // 如果右孩子存在且还没访问过就转向右孩子 if (top-rchild top-rchild ! lastVisited) { p top-rchild; } else { // 左右都访问完了可以访问自己 cout top-data ; lastVisited top; s.pop(); } } } }关键点后序非递归是三种遍历里实现最容易出错的。核心难点在于正确判断“右子树是否已经处理完毕”。引入lastVisited指针记录上一次被访问的节点当top-rchild lastVisited时说明右子树已经访问过了此时可以安全地访问根节点。6. 深度对比与思考三种遍历方式的多维度对比遍历方式递归实现难度非递归实现难度空间复杂度最坏实际使用频率前序低低O(n)高复制、序列化中序低中O(n)高BST有序输出后序低高O(n)中销毁、表达式树结合《C Primer Plus》的深度思考递归与栈帧递归版本本质上是编译器帮我们维护了一个隐式的栈帧。每次函数调用都会在系统栈上压入返回地址、局部变量等信息。非递归只是把这个栈显式写出来。在《C Primer Plus》第9章讲内存模型时我们了解了栈区和堆区的区别递归深度过大时栈区溢出就是这个原因。后序与析构后序遍历的访问顺序正好对应了“先析构孩子再析构自己”的销毁逻辑。在《C Primer Plus》第10-12章讲类和动态内存时我们强调了一个重要原则如果类中有new出来的子对象析构时必须先释放子对象再释放自己。后序遍历正是这种“自底向上”的销毁顺序因此很多树的销毁函数都用后序。父指针的权衡如果树的节点带有父指针非递归后序遍历可以写得更简洁但会增加空间开销和维护成本。在《C Primer Plus》中反复强调软件工程中没有银弹任何设计都是在时间、空间和复杂度之间做权衡。7. 完整测试代码下面构建一棵示例二叉树分别用六种遍历方式输出结果验证递归与非递归版本的一致性int main() { // 手动构建一棵简单二叉树 // 1 // / \ // 2 3 // / \ // 4 5 BiNode* root new BiNode(1); root-lchild new BiNode(2); root-rchild new BiNode(3); root-lchild-lchild new BiNode(4); root-lchild-rchild new BiNode(5); cout 前序递归: ; PreOrder(root); cout endl; cout 前序非递归: ; PreOrderNonRecursive(root); cout endl; cout 中序递归: ; InOrder(root); cout endl; cout 中序非递归: ; InOrderNonRecursive(root); cout endl; cout 后序递归: ; PostOrder(root); cout endl; cout 后序非递归: ; PostOrderNonRecursive(root); cout endl; return 0; }预期输出结果前序递归: 1 2 4 5 3 前序非递归: 1 2 4 5 3 中序递归: 4 2 5 1 3 中序非递归: 4 2 5 1 3 后序递归: 4 5 2 3 1 后序非递归: 4 5 2 3 1六种遍历输出完全一致验证了递归与非递归版本的正确性。8. 总结二叉树的遍历是数据结构最基础也最重要的操作之一几乎所有的树相关算法都建立在遍历的基础上。本文从递归到非递归、从代码到原理、从实现到对比系统地梳理了三种遍历方式。建议读者亲手敲一遍代码在调试器中观察栈的变化过程才能真正理解其中的精妙之处。