Appearance
前序遍历
前序就是"进门就记账"
树是递归定义的，所以遍历也只能递归地说：一棵二叉树由根、左子树、右子树三部分组成，把这三者排个先后就是一种遍历。三者全排列有 6 种，限定"先左后右"之后只剩三种——DLR、LDR、LRD，也就是前序、中序、后序。
前序取的是 DLR：根 → 左 → 右（也写作 NLR，N = Node）。对下面这棵树，前序序列是 A B D E C F：
A
/ \
B C
/ \ \
D E F"根在最前"这一条决定了前序的性格：你在还没看过任何子树的时候就要把根处理掉。所以凡是"信息从上往下流"的任务——建树、复制、给结点标层号、把深度传给孩子——都归前序；而"必须先知道子树结果才能算根"的任务——求高度、数结点、释放内存——一概归后序。这条判据后面还会用到。
三种遍历只差一行，因为路线本来就是同一条
这是整个遍历部分最省事的一个观察：三种深度优先遍历的递归代码，抹掉那一行 visit 之后完全相同，递归的执行路径也完全相同——都是"向左下走到底、回溯、向右下走"这条固定路线。
差别只在于：沿这条路线经过每个结点时，在第几次经过它的时候把它记下来。每个结点恰好被经过三次：
①第一次经过（下行进入） → 记下来就是【前序】
↙ A ↖
↙ ↑ ↖
②第二次经过（左子树返回、准备进右子树）→ 记下来就是【中序】
↑
③第三次经过（右子树返回、准备回到双亲）→ 记下来就是【后序】考场上的手工画法：从根出发，想象用笔沿树的外轮廓画一条闭合曲线绕一圈，每个结点会被"擦到"三次（左侧、下方、右侧）——前序只记左侧那次，中序记下方那次，后序记右侧那次。上图的绕行顺序是 A(左) B(左) D(左) D(下) D(右) B(下) E(左) …，只取"左侧"即得 A B D E C F。
这个方法真正的价值在于一次绕行同时得到三个序列。分开做三遍，很容易在深层结点处走错分支；绕一圈只走一次，三个序列同时落笔。
先看一眼
看完你应该确认：访问的时机是刚进入一个结点的时候，而不是从它的子树返回的时候。
递归实现：visit 的位置就是全部
c
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void PreOrder(BiTree T) {
if (T == NULL) return; // 递归出口：空子树什么都不做
visit(T); // 访问根结点 —— visit 在两次递归调用之前，这就是"前序"
PreOrder(T->lchild); // 递归遍历左子树
PreOrder(T->rchild); // 递归遍历右子树
}把 visit(T) 移到两次递归调用之间即为中序，移到之后即为后序。三份代码只有这一行的位置不同。
时间恒为 PreOrder 对每个结点恰好被调用一次（另有
空间是
注意"最好情况"不等于"平均情况"。随机插入建出的二叉树平均高度是
量级，但那是关于输入分布的结论，不能写成"前序遍历的空间复杂度是 "。给定一棵具体的树，空间就是它的高度。
非递归写法一：先压右孩子，后压左孩子
前序的访问发生在进入结点的第一时间，此后左右子树的处理互不依赖。所以只要用一个栈保存"待处理的子树根"，弹一个访问一个即可——这是三种遍历里最好写的一个。
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; // 左孩子后入栈
}
}为什么必须先压右：栈是后进先出，后入栈的先出栈。前序要求左子树整体先于右子树被访问，所以左孩子必须后入栈。
压反了会得到什么：先压左、后压右则每次都先展开右子树，得到 NRL 序列（根 → 右 → 左），上例输出 A C F B E D。这个序列本身也有用——它的逆序恰好是后序序列（D E B F C A），这正是后序遍历双栈法的原理。
栈的最大深度不超过
"它会装下整整一层"是一个常被写进笔记的误解——不会。 对完全二叉树验证一下：
弹栈版的逐步栈变化（想亲手验证栈深结论就展开）
以上文那棵树为例：
| 步骤 | 弹出并访问 | 压入 | 栈内容（栈顶在右） |
|---|---|---|---|
| 0 | — | A | [A] |
| 1 | A | C, B | [C, B] |
| 2 | B | E, D | [C, E, D] |
| 3 | D | — | [C, E] |
| 4 | E | — | [C] |
| 5 | C | F | [F] |
| 6 | F | — | [] |
输出序列 A B D E C F，与递归结果一致；栈最大只到 3 个元素（树高 3）。
非递归写法二：统一模板，栈里装的是当前路径
三种深度优先遍历有一个共用的非递归框架——沿左链一路入栈，走到头再回退向右。它的完整推导写在 中序遍历，这里只给前序变体：把访问动作从"出栈时"提前到"入栈时"。
c
void PreOrder_Template(BiTree T) {
Stack S; InitStack(S);
BiTree p = T;
while (p != NULL || !IsEmpty(S)) {
if (p != NULL) {
visit(p); // ← 与中序的唯一差别：入栈前就访问（根在最前）
Push(S, p);
p = p->lchild; // 一路向左
} else {
Pop(S, p); // 左边走到头，回退
p = p->rchild; // 转向右子树
}
}
}两种写法量级相同，选哪个取决于你要不要用到栈里的内容：
| 写法一（弹栈压右左） | 写法二（统一模板） | |
|---|---|---|
| 栈内容的含义 | 待处理的子树根集合（一堆并列的分支） | 从根到当前结点的路径 |
| 栈的最大深度 | 至多 | 至多 |
| 能否改写成中序／后序 | 不能，只适用于前序 | 能，改 visit 位置即得中序；后序还要加标记 |
需要"当前结点到根的路径"时只能用写法二——比如求某个结点的所有祖先。写法一的栈里存的是一堆并列的兄弟分支，不是路径。
前序序列的性质：两条决定了它能推出什么
| 性质 | 说明 |
|---|---|
| 首元素必是根 | 前序先访问根 |
| 子树占连续区间 | 任一子树的所有结点在前序序列中连续，且该子树的根在区间最前 |
| NRL 的逆序 = 后序 | "根→右→左"反过来读就是"左→右→根" |
| 前序 + 中序可唯一确定 | 前序定根、中序划分左右，见 构造二叉树 |
| 前序 + 后序不能唯一确定 | 结点只有一个孩子时无法判断左右 |
| BST 的前序可单独确定 | 中序序列由前序排序即得，等价于已知前序 + 中序 |
倒数第二条要单独说，因为它并不意味着前序 + 后序什么都推不出来。
设根为
- 若
有两个孩子，那么前序去根后的首元素是左子树的根，后序去根后的末元素是右子树的根，两者是不同结点，必然不相等； - 若
只有一个孩子，那么剩下的结点全在同一棵子树里，前序去根的首与后序去根的末都是那棵子树的根，必然相等。
所以"前序去根首
顺带一条：如果前序去根后与后序去根后完全逆序，那么每一层都不可能有两个孩子（有两个孩子时，左子树的结点在前序与后序里都排在右子树之前，相对方向一致，不会整体反转），整棵树必然是一条单链。
前序遍历与图的 DFS（对照图那一章时展开）
树的前序遍历就是图的深度优先搜索在树上的特例：都是"能往深处走就往深处走，走不动了回退"。差别只有两点：
- 图可能有环、可能有重复路径，DFS 必须维护
visited[]数组；树天然无环且路径唯一，所以不需要； - 图的邻接点没有"左右"之分，遍历次序取决于存储结构（邻接表的链接顺序）；树的左右子树次序是确定的。
前序驱动的任务：信息自顶向下流
1. 按前序序列建立二叉链表。 给定含空指针标记（# 表示空树）的前序字符序列，可以直接递归建树——读到一个字符时它就是当前子树的根，后面紧跟的正是它的左子树、再后面是右子树：
c
void CreateBiTree(BiTree *T) {
char ch;
scanf("%c", &ch);
if (ch == '#') { // '#' 表示空树，递归出口
*T = NULL;
} else {
*T = (BiTNode *)malloc(sizeof(BiTNode));
(*T)->data = ch; // 先生成根结点 —— 对应前序的 visit
CreateBiTree(&((*T)->lchild)); // 递归建左子树
CreateBiTree(&((*T)->rchild)); // 递归建右子树
}
}为什么建树必须用前序而不能用中序：读到一个字符时必须马上知道"它是谁的什么"。前序序列里根出现在子树之前，所以可以先造好根、再往下挂；中序序列里根夹在两棵子树中间，读到它时左子树已经读完，却还不知道该挂到谁下面。
补空标记 # 也是必要的——不加空标记，前序序列不能唯一确定二叉树；加上就可以，因为每个空位置都被显式记录了。
2. 把深度传给孩子。 凡是"进入结点时就能确定、并要往下传"的量，都写在 visit 的位置上：
c
// 输出每个结点的层号（根为第 1 层）
void PrintLevel(BiTree T, int level) {
if (T == NULL) return;
printf("%c:%d ", T->data, level); // 进入时即可确定层号（信息由双亲传下）
PrintLevel(T->lchild, level + 1);
PrintLevel(T->rchild, level + 1);
}这个骨架直接就是求带权路径长度 WPL 的算法：把 level 换成 depth，到叶结点时累加 weight × depth。代码题里出现"求 WPL""求根到各叶子的路径""给每个结点标层号"，用的都是这一个模板。
3. 复制一棵二叉树、输出前缀表达式。 复制的动作次序与前序完全同构（先复制根，再递归复制左右子树）。表达式树按前序输出即前缀表达式（波兰式），中序得中缀式（缺括号）、后序得后缀式。-*abc。
前序做不了什么：凡是需要先知道子树结果才能算根的任务都不适用，必须用后序——求树的高度、求结点总数、判断是否平衡、释放整棵树的内存（先释放根会丢掉子树指针）。判据只有一句：信息是从上往下流，还是从下往上汇。
考点速记
三条会被反复调用的结论：
- 三种深度优先遍历的唯一差别，是在结点被经过的三次里选了哪一次记录，递归路线完全相同。
- 前序非递归的入栈次序是"右先左后"；压反得到 NRL，其逆序即后序。弹栈版栈深至多
，与模板版同阶。 - 前序序列单独不能确定一棵二叉树，配中序才能，配后序仍然不能；补
#空标记后单独可以。
这一节在真题里被考过的形式（下方「真题练习」逐题对应）：
- 给前序 + 后序，问能推出什么。 这是前序最主要的考法，而且两道真题问的角度不同。一道问"根结点的孩子结点是谁"——用上面那条判据：去根后前序首
后序末就说明根只有一个孩子，且那个孩子就是它。另一道问"中序不可能是下列哪个"——先由"去根后前序与后序完全逆序"判定整棵树是单链，再枚举每条边挂左还是挂右（ 条边共 种），得到全部合法中序，不在其中的就是答案。枚举时记住：孩子挂左则中序里孩子在双亲之前，挂右则在双亲之后。 - 给树形 + 一种序列，求另一种序列。 树形已经画在题面上时，序列题就退化成"把名字填对位置"：先用给出的那个序列把字母对应到树的结点上，再按目标次序读一遍。这类题错在读序列而不是错在懂原理，慢一点画完整棵树比心算稳。
- 代码大题里的"传深度"骨架。 求二叉树带权路径长度 WPL 的那道大题，标准解法就是递归时把
depth作为参数传下去，到叶结点累加weight × depth——正是本篇"信息自顶向下流"的模板。 - 先序序列与中序序列相同的条件。 答案是所有非叶结点都只有右子树：先序是"根左右"、中序是"左根右"，差异全在"根"与"左"的相对位置，要让两者逐位相同，只能让"左"消失。
易错：非递归写法把左右孩子的入栈次序压反。 要左先出，就得左后入。
易错：以为前序 + 后序完全无法推理。 失效的只有"独生子的左右身份"，层级关系照样能定。
易错：把弹栈版的栈深记成"一整层"。 它至多
，与模板版同阶。
易错：用前序去做需要子树结果的计算。 求高度、数结点、释放内存都得用后序。
教材出处
- 遍历二叉树的定义、"DLR / LDR / LRD / DRL / RDL / RLD 六种方案，限定先左后右后只剩前三种"以及三种遍历的操作定义：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p122（5.5.1 节）
- "三种遍历算法不同处仅在于访问根结点和遍历左右子树的先后关系，抹去输出语句后三个算法完全相同"，以及递归执行过程中用三角形/圆形/方形标记前序/中序/后序访问时机的图示：印刷 p123
- 遍历的时间复杂度
、辅助空间为栈的最大容量即树的深度、最坏 ：印刷 p125 - 按先序次序输入字符序列建立二叉链表（以
#表示空树）的算法：印刷 p126 - 复制二叉树的算法及其"与先序遍历实现非常类似"的说明：印刷 p127
相关知识
中序遍历（统一模板在那篇讲透）｜后序遍历（末元素是根，与前序对称）｜层序遍历（BFS 对照）｜由遍历序列构造二叉树｜树与二叉树基本概念｜树与森林（先根遍历对应其二叉树表示的前序）｜图的深度优先搜索