二叉树的遍历顺序
二叉树的遍历是指按照一定顺序访问树中所有节点的过程，常见的遍历顺序可分为深度优先遍历（DFS） 和广度优先遍历（BFS） 两大类，其中深度优先遍历又包含三种经典方式。以下是详细说明：
一、深度优先遍历（DFS）
深度优先遍历是沿着树的深度优先访问节点，通常使用递归或栈实现。根据访问根节点的时机不同，分为三种顺序：
1. 前序遍历（Preorder Traversal）
- 顺序：根节点 → 左子树 → 右子树（根在前）。
- 示例：对于二叉树
前序遍历结果为：
1
/ \
2 3
/ \
4 51 → 2 → 4 → 5 → 3。
2. 中序遍历（Inorder Traversal）
- 顺序：左子树 → 根节点 → 右子树（根在中）。
- 示例：同上二叉树，中序遍历结果为：
4 → 2 → 5 → 1 → 3。 - 特点：对于二叉搜索树（BST），中序遍历结果是升序排列的，这是其重要应用。
3. 后序遍历（Postorder Traversal）
- 顺序：左子树 → 右子树 → 根节点（根在后）。
- 示例：同上二叉树，后序遍历结果为：
4 → 5 → 2 → 3 → 1。 - 应用：常用于计算树的高度、删除节点等场景（需先处理子节点再处理根）。
二、广度优先遍历（BFS）
广度优先遍历（又称层序遍历）是沿着树的宽度逐层访问节点，通常使用队列实现。
- 顺序：从根节点开始，按层次依次访问每一层的节点（先访问第1层，再第2层，以此类推）。
- 示例：对于上述二叉树，层序遍历结果为：
1 → 2 → 3 → 4 → 5。 - 应用：适合解决“树的层次相关问题”，如求树的最小深度、打印二叉树的每一层等。
三、其他特殊遍历方式
除上述经典遍历外，还有一些针对特定场景的遍历方式：
- ** Morris 遍历**：一种空间复杂度为 O(1) 的遍历算法，通过修改树的指针（遍历后恢复）实现，适用于对空间敏感的场景。
- 逆序遍历：如“逆前序”“逆中序”等，即反向执行经典遍历顺序（例如逆中序遍历二叉搜索树可得到降序结果）。
各类遍历的对比表格
| 遍历方式 | 顺序规则 | 实现方式 | 典型应用场景 |
|---|---|---|---|
| 前序遍历 | 根 → 左 → 右 | 递归/栈 | 复制二叉树、前缀表达式求值 |
| 中序遍历 | 左 → 根 → 右 | 递归/栈/Morris | 二叉搜索树排序、中缀表达式求值 |
| 后序遍历 | 左 → 右 → 根 | 递归/栈 | 计算树的高度、删除节点、后缀表达式求值 |
| 层序遍历 | 按层次从左到右 | 队列 | 求树的宽度、层次相关问题 |
总结
二叉树的遍历顺序本质是对“根节点访问时机”或“访问方向（深度/广度）”的定义。实际应用中，需根据问题需求选择合适的遍历方式（例如判断二叉搜索树用中序遍历，层次打印用层序遍历）。掌握这些遍历的实现逻辑（递归/迭代）是解决二叉树问题的基础。