树结构，尤其是二叉树，是计算机科学中一种非常重要且常用的数据结构。为了访问或处理树中的每一个节点，我们需要遵循特定的顺序，这个过程被称为树的遍历（Traversal）。对于二叉树，最常见也是最基本的遍历方式就是前序、中序和后序遍历。理解它们的核心原理、实现方式以及各自的应用场景，是掌握树结构操作的基础。
什么是前中后序遍历？（核心概念）
前中后序遍历是二叉树的三种基本深度优先遍历方式。它们之间的区别仅仅在于访问（或处理）树中根节点的顺序相对于访问其左子树和右子树的顺序。对于树中的任意一个节点，其遍历顺序总是遵循以下模式：
- 左子树：先遍历左子树中的所有节点。
- 右子树：后遍历右子树中的所有节点。
- 根节点：在遍历左子树和右子树之间或之前或之后访问当前节点。
这三种遍历方式的具体规则定义如下：
- 前序遍历（Pre-order Traversal）： 根 -> 左 -> 右
- 中序遍历（In-order Traversal）： 左 -> 根 -> 右
- 后序遍历（Post-order Traversal）： 左 -> 右 -> 根
这里的“左”和“右”是指对当前节点的左子树和右子树进行递归的相同类型遍历。当子树为空时，该方向的遍历自然就跳过。
如何进行前中后序遍历？（实现方法）
实现树的遍历主要有两种方法：递归方法和迭代方法。递归方法通常直观且易于理解，而迭代方法则需要借助栈数据结构来模拟递归调用的过程，有时能避免深度过大的递归栈溢出问题。
递归实现思路
递归实现直接映射了前中后序遍历的定义，是理解它们最直接的方式。
前序遍历的递归实现：
根 -> 左 -> 右
- 如果当前节点非空，则访问（处理）当前节点的数据。
- 递归地对当前节点的左子树进行前序遍历。
- 递归地对当前节点的右子树进行前序遍历。
中序遍历的递归实现：
左 -> 根 -> 右
- 如果当前节点非空，则递归地对当前节点的左子树进行中序遍历。
- 访问（处理）当前节点的数据。
- 递归地对当前节点的右子树进行中序遍历。
后序遍历的递归实现：
左 -> 右 -> 根
- 如果当前节点非空，则递归地对当前节点的左子树进行后序遍历。
- 递归地对当前节点的右子树进行后序遍历。
- 访问（处理）当前节点的数据。
迭代实现思路（使用栈）
迭代实现通过显式地使用一个栈来管理待访问的节点。不同遍历方式的迭代实现逻辑有所差异，其中后序遍历的迭代实现相对复杂。
前序遍历的迭代实现：
前序遍历的迭代方法相对直观：
- 创建一个栈，并将根节点压入栈中。
- 当栈非空时，循环执行：
- 从栈中弹出一个节点（记为当前节点）。
- 访问当前节点。
- 如果当前节点的右子树非空，将右子节点压入栈中（先压右子是为了让左子先弹出）。
- 如果当前节点的左子树非空，将左子节点压入栈中。
这样做的原因是栈的“后进先出”特性，我们希望先处理左子树，所以后压入栈；希望后处理右子树，所以先压入栈。
中序遍历的迭代实现：
中序遍历的迭代方法需要先将左侧所有节点压入栈，直到遇到空节点：
- 创建一个栈，设置当前节点为根节点。
- 当当前节点非空或者栈非空时，循环执行：
- 沿着左子树向下，将所有遇到的非空节点压入栈中，直到当前节点为空。
- 从栈中弹出一个节点。访问该节点。
- 将当前节点设置为该节点的右子树，继续循环（转向处理右子树）。
后序遍历的迭代实现：
后序遍历的迭代实现通常比前序和中序更复杂，因为它要求先访问左右子树，最后访问根节点。常见的方法是使用两个栈，或者在一个栈中记录父子关系或访问状态。一种双栈方法如下：
- 创建一个栈 S1，将根节点压入 S1。
- 创建一个栈 S2，用于存储后序遍历的结果。
- 当 S1 非空时，循环执行：
- 从 S1 弹出一个节点（记为当前节点）。
- 将当前节点压入 S2。
- 如果当前节点的左子树非空，将左子节点压入 S1。
- 如果当前节点的右子树非空，将右子节点压入 S1。
- 当 S1 为空时，S2 中从栈顶到栈底的元素序列就是后序遍历的结果。
这种方法利用了先根后右左（根 -> 右 -> 左）的顺序，将其压入另一个栈 S2，通过 S2 的弹出顺序实现左 -> 右 -> 根的后序。
前中后序遍历的典型应用（在哪里使用，为什么需要它们）
这三种遍历方式不仅仅是理论上的概念，它们各自在实际问题和算法中有独特的用途。
前序遍历的应用场景：
由于前序遍历是“根 -> 左 -> 右”的顺序，它经常用于需要先处理父节点再处理子节点的场景。
- 复制一棵树：按照前序遍历的顺序创建新节点并连接起来，可以方便地复制一棵二叉树。新树的结构与原树完全相同。
- 表达和构建树的结构：前序遍历的序列可以用来表示树的结构（如果节点包含空子树的信息，例如用特殊标记表示空）。
- 文件系统目录遍历：许多文件系统的遍历方式类似前序遍历，先访问目录本身，再访问其下的子目录和文件。
- 将树转换为前缀表达式（波兰表示法）：对于表达式树，前序遍历可以得到对应表达式的前缀表示，操作符位于操作数之前。
中序遍历的应用场景：
中序遍历是“左 -> 根 -> 右”的顺序，其最著名的应用在于二叉搜索树（Binary Search Tree, BST）。
- 二叉搜索树的排序输出：对任何二叉搜索树进行中序遍历，得到的节点序列是按键值升序排列的。这是中序遍历最经典、最重要的应用。
- 将表达式树转换为中缀表达式：对表达式树进行中序遍历可以得到中缀表达式。通常需要在访问节点时注意添加括号来保持运算优先级。
后序遍历的应用场景：
后序遍历是“左 -> 右 -> 根”的顺序，这种顺序确保在访问父节点之前已经访问了其所有子节点。
- 删除或释放树的节点：在销毁一棵树或删除子树时，必须先释放子节点的内存，最后再释放父节点的内存，以避免出现悬空指针。后序遍历自然地提供了这种“自底向上”的处理顺序。
- 计算表达式树的值：对于表达式树，后序遍历可以得到对应表达式的后缀表达式（逆波兰表示法）。计算时可以按照后缀表达式的顺序方便地进行，因为操作符总是在其操作数之后出现。
如何利用前中后序遍历进行树的重建？
一个非常有意思且实用的问题是：给定一棵树的某种遍历序列，能否唯一确定这棵树的结构？答案是：仅凭一种遍历序列通常不能唯一确定一棵树（除非是特殊结构的树，比如已知是完全二叉树等）。但如果给定两种特定的遍历序列，通常就可以重建出唯一的二叉树。
关键原理：
- 前序遍历：序列中的第一个元素一定是整棵树的根节点。
- 后序遍历：序列中的最后一个元素一定是整棵树的根节点。
- 中序遍历：中序遍历的序列可以用来确定给定根节点的左子树和右子树包含哪些节点。根节点在中序序列中的位置将其左侧的序列划分为左子树，右侧的序列划分为右子树。
常见的树重建组合：
- 前序遍历序列 + 中序遍历序列：这是最常见和最易于实现的组合。
方法：以前序序列的第一个元素作为当前子树的根节点。在中序序列中找到这个根节点的位置。中序序列中根节点左边的所有元素都属于左子树，右边的所有元素都属于右子树。根据中序序列划分出的左右子树的节点集合，在前序序列中找到对应的子序列，它们分别是左右子树的前序序列。然后，递归地使用对应的子序列构建左右子树。 - 中序遍历序列 + 后序遍历序列：
方法：以后序序列的最后一个元素作为当前子树的根节点。在中序序列中找到这个根节点的位置，划分出左右子树的节点集合。根据中序序列确定的范围，在后序序列中划分出左右子树的后序序列。递归构建。
请注意，前序 + 后序遍历序列一般不能唯一确定一棵二叉树的结构（除非是只有叶子节点和单分支节点的树），因为缺少中序序列提供的根节点划分左右子树的信息，无法区分右子树为空左子树不空和左子树为空右子树不空的情况。
前中后序遍历的复杂度分析（多少时间/空间）
对树进行遍历，无论是哪种顺序，都需要访问树中的每一个节点恰好一次。
时间复杂度：
每种遍历方法都需要访问 N 个节点，并且在每个节点上执行常数次操作（检查子节点、访问数据、递归调用或栈操作）。因此，无论是递归还是迭代实现，前中后序遍历的时间复杂度都是线性的，即与树中节点的数量 N 成正比。
- 时间复杂度：O(N)
空间复杂度：
空间复杂度主要取决于实现方法和树的结构。
- 递归实现：空间复杂度由递归调用栈的最大深度决定。在最坏情况下（树是一个倾斜的链表），递归深度等于节点数量 N，空间复杂度为 O(N)。在最好情况下（树是一个平衡二叉树），递归深度等于树的高度 log N，空间复杂度为 O(log N)。
- 迭代实现（使用栈）：空间复杂度取决于栈在执行过程中的最大大小，这同样与树的高度相关。在最坏情况下（倾斜树），栈的最大大小为 N，空间复杂度为 O(N)。在最好情况下（平衡树），栈的最大大小为 log N，空间复杂度为 O(log N)。
总而言之，树遍历的渐近空间复杂度通常用 O(h) 表示，其中 h 是树的高度。
总结
前序、中序和后序遍历是处理二叉树数据的基本操作。它们通过改变根节点相对于左右子树的访问顺序，为我们提供了处理树结构的不同视角和工具。无论是递归的简洁优雅，还是迭代的内存可控性，理解它们的实现原理至关重要。更重要的是，认识到这些遍历方式在复制树、表达式处理、数据排序以及树结构重建等众多实际问题中的独特作用，才能真正掌握树结构的应用。它们是许多高级树算法和数据结构（如堆、Trie树等）的基础。
