考研全科复习资料

408

数据结构

DS-04-03 二叉树的遍历（先序/中序/后序/层序）

一、定位信息

项目	内容
圈层	核心层（大纲考点）
前置知识	二叉树的定义与性质、二叉链表存储结构、递归思想、栈和队列
知识网络定位	遍历是二叉树最核心的操作，是构造、查找、线索化等算法的基础，贯穿整章
考点热度	H级（高频重点）：近5年每年必考，选择题+大题均有出现，累计分值≥10分

二、知识点讲解

2.1 遍历的概念

二叉树的遍历是指按某条搜索路径访问树中每个节点，使得每个节点被访问一次且仅被访问一次。"访问"的含义很广，可以是输出节点信息、修改节点数据等。

遍历的本质是将非线性结构转化为线性序列，不同的遍历方式产生不同的线性序列。

2.2 三种深度优先遍历（递归定义）

先序遍历（Pre-order，根左右）：

访问根节点
先序遍历左子树
先序遍历右子树

中序遍历（In-order，左根右）：

中序遍历左子树
访问根节点
中序遍历右子树

后序遍历（Post-order，左右根）：

后序遍历左子树
后序遍历右子树
访问根节点

直观理解：三种遍历的区别仅在于"根"被访问的时机——先序先访问根，中序中间访问根，后序最后访问根。左右子树的相对顺序始终是先左后右。

2.3 递归实现

// 先序遍历（递归）
// 参数 T：当前子树的根节点
void PreOrder(BiTree T) {
    if (T == NULL) return;     // 递归终止：空树直接返回
    visit(T);                  // 1. 访问根节点
    PreOrder(T->lchild);       // 2. 递归遍历左子树
    PreOrder(T->rchild);       // 3. 递归遍历右子树
}

// 中序遍历（递归）
void InOrder(BiTree T) {
    if (T == NULL) return;     // 递归终止：空树直接返回
    InOrder(T->lchild);        // 1. 递归遍历左子树
    visit(T);                  // 2. 访问根节点
    InOrder(T->rchild);        // 3. 递归遍历右子树
}

// 后序遍历（递归）
void PostOrder(BiTree T) {
    if (T == NULL) return;     // 递归终止：空树直接返回
    PostOrder(T->lchild);      // 1. 递归遍历左子树
    PostOrder(T->rchild);      // 2. 递归遍历右子树
    visit(T);                  // 3. 访问根节点
}

复杂度分析：三种递归遍历的时间复杂度均为 $O(n)$ （每个节点恰好被访问一次），空间复杂度为 $O(h)$ （递归栈的最大深度等于树高 $h$ ，最坏 $O(n)$ ）。

2.4 中序遍历的非递归实现（栈）

核心思想：用显式栈模拟递归调用栈。沿左分支一路入栈到底，然后出栈访问，再转向右子树。

// 中序遍历（非递归，使用栈）
// 参数 T：二叉树的根节点
void InOrder_NonRecursive(BiTree T) {
    InitStack(S);              // 初始化空栈
    BiTree p = T;              // p 为当前遍历指针
    
    // 当 p 不为空 或 栈不为空时继续
    while (p != NULL || !IsEmpty(S)) {
        if (p != NULL) {       // 当前节点不为空
            Push(S, p);        // 将当前节点入栈
            p = p->lchild;     // 沿左子树深入
        } else {               // 当前节点为空，说明左子树已遍历完
            Pop(S, p);         // 出栈一个节点
            visit(p);          // 访问该节点（中序：左根右，此时"左"已完成）
            p = p->rchild;     // 转向右子树
        }
    }
}

算法步骤详解：

从根节点开始，沿左子树一直走到底，沿途节点全部入栈
当左子树为空时，弹出栈顶节点并访问（该节点是当前子树的"根"）
转向该节点的右子树，重复步骤1
当栈空且当前指针为空时，遍历结束

2.5 先序遍历的非递归实现（栈）

// 先序遍历（非递归）
void PreOrder_NonRecursive(BiTree T) {
    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(p) 还是出栈后 visit(p) 的位置不同。

2.6 后序遍历的非递归实现（栈）

后序遍历的非递归实现较复杂，因为节点需要在左右子树都访问完后才能被访问。

// 后序遍历（非递归）
void PostOrder_NonRecursive(BiTree T) {
    InitStack(S);
    BiTree p = T;
    BiTree r = NULL;           // r 记录上次访问的节点
    
    while (p != NULL || !IsEmpty(S)) {
        if (p != NULL) {       // 沿左子树深入
            Push(S, p);
            p = p->lchild;
        } else {               // 左子树为空，看栈顶
            GetTop(S, p);      // 取栈顶节点（不出栈）
            // 如果右子树存在且未被访问过
            if (p->rchild != NULL && p->rchild != r) {
                p = p->rchild; // 转向右子树
            } else {           // 右子树为空或已访问过
                Pop(S, p);     // 出栈
                visit(p);      // 访问节点
                r = p;         // 记录已访问节点
                p = NULL;      // 置空，避免重复进入左子树
            }
        }
    }
}

关键点：用变量 $r$ 记录上一个被访问的节点。当栈顶节点的右孩子等于 $r$ 时，说明右子树已访问过，可以访问当前节点。

2.7 层序遍历（队列）

// 层序遍历（使用队列）
void LevelOrder(BiTree T) {
    InitQueue(Q);              // 初始化队列
    if (T != NULL) Enqueue(Q, T);  // 根节点入队
    
    while (!IsEmpty(Q)) {
        Dequeue(Q, p);         // 出队一个节点
        visit(p);              // 访问该节点
        if (p->lchild != NULL) Enqueue(Q, p->lchild);  // 左孩子入队
        if (p->rchild != NULL) Enqueue(Q, p->rchild);  // 右孩子入队
    }
}

层序遍历的本质：BFS（广度优先搜索），利用队列的先进先出特性保证按层访问。

2.8 由遍历序列唯一确定二叉树

已知遍历组合	能否唯一确定	说明
先序 + 中序	✅ 能	先序首元素为根，在中序中划分左右子树，递归处理
后序 + 中序	✅ 能	后序末元素为根，在中序中划分左右子树，递归处理
先序 + 后序	❌ 不能	无法确定左右子树的划分（除非是满二叉树）
层序 + 中序	✅ 能	类似先序+中序的方法

关键结论：先序+中序或后序+中序可以唯一确定一棵二叉树。先序+后序一般不能。

2.9 三种遍历对比表

对比项	先序遍历	中序遍历	后序遍历	层序遍历
访问顺序	根→左→右	左→根→右	左→右→根	逐层从左到右
递归实现	简单	简单	简单	不用递归
非递归实现	栈（较简单）	栈（经典）	栈（较复杂，需记录r）	队列
应用场景	复制二叉树、前缀表达式	BST有序序列、中缀表达式	释放空间、后缀表达式	按层处理、求树宽
表达式树	前缀（波兰式）	中缀	后缀（逆波兰式）	—

三、记忆与理解辅助

技巧1：遍历顺序口诀

"先根中根后根，根在前中后"
先序：根左右（根在最前）
中序：左根右（根在中间）
后序：左右根（根在最后）

技巧2：非递归遍历通用框架

while (p不空 || 栈不空) {
    if (p不空) {
        [先序：visit(p)]   // 先序在此访问
        p 入栈
        p = p->lchild
    } else {
        p = 出栈
        [中序：visit(p)]   // 中序在此访问
        p = p->rchild
    }
}
// 后序需额外记录上次访问节点 r

技巧3：已知两种遍历还原二叉树的步骤

"先/后序定根，中序分左右，递归重复"
先序首元素（或后序末元素）是根
在中序中找到根的位置，左边是左子树，右边是右子树
根据左右子树的长度，在先序/后序中截取对应子序列
对左右子树递归执行上述步骤

技巧4：遍历序列的快速识别

特征	对应遍历
第一个访问根	先序
最后一个访问根	后序
BST的遍历结果是有序的	中序
表达式树输出前缀表达式	先序
表达式树输出后缀表达式	后序

四、例题与精解

例题1（基础巩固）

题目：已知二叉树的先序序列为 ABDECFG，中序序列为 DBEACGF，请写出后序序列。

命题意图：考查由先序+中序序列还原二叉树并求后序序列的能力。

审题分析：先序首元素 A 是根，在中序中 A 将序列分为左子树 DBE 和右子树 CGF。

解题思路：递归划分，每次确定根节点后在中序中划分左右子树。

完整步骤：

Step 1：先序 ABDECFG，中序 DBEACGF

根 = A（先序首元素）
中序中 A 的位置：左边 DBE（左子树3个节点），右边 CGF（右子树3个节点）
先序中：左子树 BDE，右子树 CFG

Step 2：左子树先序 BDE，中序 DBE

根 = B
中序中 B 左边 D，右边 E
B 的左子 = D，右子 = E

Step 3：右子树先序 CFG，中序 CGF

根 = C
中序中 C 左边为空，右边 GF
C 无左子，右子树先序 FG，中序 GF

Step 4：右子树的右子树先序 FG，中序 GF

根 = F
中序中 F 左边 G，右边为空
F 的左子 = G，无右子

Step 5：还原的二叉树：

Step 6：后序遍历（左右根）：D → E → B → G → F → C → A

答案：后序序列为 DEBGFCA。

方法反思：还原二叉树时，每一步都要在中序中准确定位根的位置，从而正确划分左右子树的长度。注意先序中左右子树的子序列长度要与中序中的一致。

例题2（中等提升）

题目：写出中序遍历非递归算法的执行过程。对以下二叉树，给出栈的变化过程：

命题意图：深入理解中序非递归算法的执行机制。

审题分析：需要模拟栈的操作过程，明确每一步入栈、出栈和访问的操作。

完整步骤：

步骤	操作	栈状态（栈底→栈顶）	访问序列	当前指针 p
1	初始	空		1
2	1 入栈，p→左	[1]		2
3	2 入栈，p→左	[1, 2]		4
4	4 入栈，p→左	[1, 2, 4]		NULL
5	p空，出栈4，visit(4)	[1, 2]	4	NULL
6	p空，出栈2，visit(2)	[1]	4, 2	NULL
7	p空，出栈1，visit(1)	[]	4, 2, 1	NULL→右→3
8	3 入栈，p→左	[3]	4, 2, 1	5
9	5 入栈，p→左	[3, 5]	4, 2, 1	NULL
10	p空，出栈5，visit(5)	[3]	4, 2, 1, 5	NULL
11	p空，出栈3，visit(3)	[]	4, 2, 1, 5, 3	NULL→右→6
12	6 入栈，p→左	[6]	4, 2, 1, 5, 3	NULL
13	p空，出栈6，visit(6)	[]	4, 2, 1, 5, 3, 6	NULL
14	栈空且p空，结束

答案：中序序列为 4, 2, 1, 5, 3, 6。

方法反思：非递归中序遍历的核心模式是"一路向左入栈到底，出栈访问，转向右"。理解这个过程对后续线索二叉树的构造非常重要。

五、考情分析

项目	内容
考查频次	近5年每年必考，是第四章的核心考点
常见题型	选择题（由遍历序列还原树、判断遍历结果）、大题（非递归算法实现、遍历应用）
分值占比	选择题2-4分 + 大题5-10分，合计可达10-14分
命题趋势	非递归遍历是高频大题考点；由两种遍历序列还原树是经典选择题；近年倾向于结合实际应用（如表达式树）
典型考点	①先序+中序→后序 ②中序非递归算法 ③层序遍历用队列 ④遍历的应用（求树高、复制、释放）

六、易错点提醒

易错点1

错误表现：先序+后序无法唯一确定二叉树时，误以为可以
错误原因：混淆了"先序+中序"和"先序+后序"的确定性
正确理解：先序+中序或后序+中序可唯一确定；先序+后序一般不行（除非是满二叉树或只有一个孩子的特殊情况）

易错点2

错误表现：后序非递归遍历中忘记用变量 $r$ 记录上次访问节点，导致右子树重复访问
错误原因：后序遍历的节点出栈时机不明确
正确理解：节点必须在左右子树都访问完后才能出栈。判断右子树是否已访问的方法是检查 p->rchild == r

易错点3

错误表现：在由遍历序列还原树时，左右子树长度划分错误
错误原因：在中序中找到根后，左右子树长度的计算出错
正确理解：中序中根左边的字符数 = 左子树节点数，右边的 = 右子树节点数。然后在先序中截取对应长度的子序列

易错点4

错误表现：层序遍历误用栈实现
错误原因：混淆了BFS和DFS的实现方式
正确理解：层序遍历 = BFS = 队列；先序/中序/后序 = DFS = 栈（或递归）

易错点5

错误表现：遍历的时间复杂度误写为 $O(n\log n)$
错误原因：与其他算法的复杂度混淆
正确理解：无论哪种遍历，每个节点恰好访问一次，时间复杂度严格为 $O(n)$

七、来源标注

依据2026考研统考408大纲
依据《数据结构（C语言版）》严蔚敏版
依据《数据结构》王道考研辅导讲义

408 ​

数据结构 ​

DS-04-03 二叉树的遍历（先序/中序/后序/层序） ​

一、定位信息 ​

二、知识点讲解 ​

2.1 遍历的概念 ​

2.2 三种深度优先遍历（递归定义） ​

2.3 递归实现 ​

2.4 中序遍历的非递归实现（栈） ​

2.5 先序遍历的非递归实现（栈） ​

2.6 后序遍历的非递归实现（栈） ​

2.7 层序遍历（队列） ​

2.8 由遍历序列唯一确定二叉树 ​

2.9 三种遍历对比表 ​

三、记忆与理解辅助 ​

技巧1：遍历顺序口诀 ​

技巧2：非递归遍历通用框架 ​

技巧3：已知两种遍历还原二叉树的步骤 ​

技巧4：遍历序列的快速识别 ​

四、例题与精解 ​

例题1（基础巩固） ​

例题2（中等提升） ​

五、考情分析 ​

六、易错点提醒 ​

易错点1 ​

易错点2 ​

易错点3 ​

易错点4 ​

易错点5 ​

七、来源标注 ​

408