Appearance
前序遍历
为什么需要前序遍历
二叉树是非线性结构，无法像线性表那样从头到尾逐个访问。遍历就是将树中所有节点按某种规则排成一个线性序列，使得每个节点恰好被访问一次。
前序遍历是三种基本深度优先遍历之一，它的特点是最先访问根节点，因此常用于：复制一棵二叉树、输出目录结构、前缀表达式求值等场景。408 考研中，前序遍历是二叉树章节的核心考点，也是理解中序、后序遍历的基础。
核心思想
前序遍历的访问顺序：根节点 → 左子树 → 右子树（NLR）。
对于下面这棵二叉树：
A
/ \
B C
/ \ \
D E F前序遍历序列为：A → B → D → E → C → F
递推过程：
- 访问根节点 A
- 前序遍历左子树（以 B 为根）：访问 B → 遍历 B 的左子树 D → 遍历 B 的右子树 E
- 前序遍历右子树（以 C 为根）：访问 C → C 无左子树 → 遍历 C 的右子树 F
前序遍历流程图
前序遍历的核心顺序：根 → 左 → 右。先访问根节点，再递归处理左子树，最后递归处理右子树。
交互可视化
通过下方的交互动画，你可以逐步观察前序遍历的执行过程：
操作详解
递归实现
递归实现直接对应前序遍历的定义，代码简洁直观。
关键步骤：
- 若当前节点为空，直接返回
- 访问当前节点（输出/处理数据）
- 递归遍历左子树
- 递归遍历右子树
c
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void PreOrder(BiTree T) {
if (T == NULL) return;
visit(T); // 访问根节点
PreOrder(T->lchild); // 递归遍历左子树
PreOrder(T->rchild); // 递归遍历右子树
}将
visit(T)的位置移到两次递归调用之间即为中序遍历，移到两次递归调用之后即为后序遍历。
非递归实现（栈）
递归本质上是系统帮我们维护了一个调用栈。手动使用栈可以消除递归，这也是 408 大题常考的写法。
关键思路：
- 将根节点入栈
- 循环：弹出栈顶节点并访问
- 先压右孩子、再压左孩子（保证左子树先被访问）
- 栈空时遍历结束
c
void PreOrderNonRecursive(BiTree T) {
if (T == NULL) return;
BiTree stack[MAXSIZE];
int top = -1;
stack[++top] = T; // 根节点入栈
while (top >= 0) {
BiTNode *p = stack[top--]; // 弹出栈顶
visit(p); // 访问节点
if (p->rchild != NULL)
stack[++top] = p->rchild; // 右孩子先入栈
if (p->lchild != NULL)
stack[++top] = p->lchild; // 左孩子后入栈（后进先出）
}
}以前面的示例树为例，栈的变化过程：
| 步骤 | 访问节点 | 栈内容（栈顶在右） |
|---|---|---|
| 1 | A | [C, B] |
| 2 | B | [C, E, D] |
| 3 | D | [C, E] |
| 4 | E | [C] |
| 5 | C | [F] |
| 6 | F | [] |
输出序列：A B D E C F，与递归结果一致。
复杂度分析
| 实现方式 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 递归 | O(n) | O(n) | 每个节点访问一次；栈深度最坏为 n（单支树） |
| 非递归（栈） | O(n) | O(n) | 每个节点入栈、出栈各一次；栈空间最坏为 n |
最好空间复杂度：O(log n)，当二叉树为完全二叉树时，栈深度等于树高。
考研高频考点
- ⭐ 根据前序 + 中序序列还原二叉树（大题/选择题高频）
- ⭐ 前序遍历的非递归实现（算法设计题常考）
- ⭐ 前序、中序、后序序列的相互推导（选择题必考）
- ⭐ 前序序列的第一个节点一定是根节点，后序序列的最后一个节点一定是根节点
- 前序遍历与 DFS（深度优先搜索）的关系
- 已知前序 + 后序不能唯一确定二叉树（除非是满二叉树）