💡 彻底搞懂二叉树的前序、中序、后序遍历
温馨提示：
本文最后更新于 2025年07月20日，已超过 5 天没有更新。若文章内的图片失效（无法正常加载），请留言反馈或直接联系我。
一、为什么要学二叉树遍历？
遍历就是“访问每个节点一次”的算法方式。在二叉树中，深度优先搜索（DFS） 包含三种遍历：前序、中序、后序，再加上层次遍历（BFS）。
- 深度遍历适合递归结构，也常出现在编程面试中(codeanddebug.in)。
- 不同遍历顺序能产生不同用途：如中序能得到排序结果，前后序常用于表达式与复制、销毁树操作(维基百科, GeeksforGeeks)。
二、前、中、后序遍历完全解析
📌 1. 前序遍历（Pre-order：根→左→右）
访问步骤：
- 访问根节点；
- 前序遍历左子树；
- 前序遍历右子树。
特点与用途：
- 可生成前缀表达式，用于构造树或表达式转换(维基百科, GeeksforGeeks)；
- 复制整棵树时非常有用。
Python 示例：
def preorder(root):
if not root: return
print(root.val)
preorder(root.left)
preorder(root.right)
图示说明：先递归“采访”根→左→右，再逐层展开子树(xiaogd.net)alt="Illustration of Preorder traversal sequence"
📌 2. 中序遍历（In-order：左→根→右）
访问步骤：
- 中序遍历左子树；
- 访问根节点；
- 中序遍历右子树。
特点与用途：
- 对 BST（Binary Search Tree）得到递增排序序列(GeeksforGeeks)；
- 常用于中序表达式构建。
Python 示例：
def inorder(root):
if not root: return
inorder(root.left)
print(root.val)
inorder(root.right)
图示说明：先左后根再右，典型“中插式”访问顺序alt="Diagram showing Inorder traversal on a binary tree"
📌 3. 后序遍历（Post-order：左→右→根）
访问步骤：
- 后序遍历左子树；
- 后序遍历右子树；
- 访问根节点。
特点与用途：
- 常用于释放/删除节点，因先访问子节点后访问节点本身(Go Further, 维基百科)；
- 构建后缀表达式非常实用。
Python 示例：
def postorder(root):
if not root: return
postorder(root.left)
postorder(root.right)
print(root.val)
图示说明：子节点先遍历，最后访问根节点alt="Postorder traversal diagram of a binary tree"
三、对比总结表
| 遍历方式 | 访问顺序 | 典型用途 |
|---|---|---|
| 前序（Root） | 根 → 左 → 右 | 构建树、前缀表达式 |
| 中序（In） | 左 → 根 → 右 | 排序输出，BST 应用 |
| 后序（Post） | 左 → 右 → 根 | 销毁节点、后缀表达式 |
四、递归与迭代对比
- 递归 简洁直观，适合初学者掌握基础概念；
- 迭代 用栈实现，能避免函数栈深度限制，适用于大数据偏瘦树结构(Şahin Arslan, GeeksforGeeks, Go Further, GeeksforGeeks)。
建议先从递归理解，再逐步练习迭代。
五、小结与练习建议
逻辑记忆：
- 前序把“根”第一个记住 → 先根；
- 中序是“中间位置”，先左后根再右；
- 后序把“根”最后记住 → 送走孩子后自己离开。
图帮助理解：
- 推荐画出小树模拟三种方式；
- 用图像记忆遍历步骤，提升印象。
上机练习：
- 试写简单遍历并运行；
- 拓展表达式树构建、BST 排序操作；
- 尝试将递归改为迭代，用栈模拟。
🎯 这些结构化的遍历思想，是理解二叉树数据结构、算法设计和面试题库的基础。初学者结合图、代码和练习，能迅速入门并打好根基。
声明：本文为原创，通过整合近 30 天技术资料与权威指南撰写。欢迎转载，但请注明出处，感谢支持！
正文到此结束
- 本文标签： 二叉树遍历 非递归遍历 前序遍历
- 本文链接： https://code.itptg.com/article/78
- 版权声明： 本文由老魏原创发布，转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
