若一棵二叉树的前序遍历序列和后序遍历序列分别为 1,2,3,4 和 4,3,2,1，则该二叉树的中序遍历序列不会是()
目标
- 独立辨析前序遍历中的核心概念、结构性质与遍历关系；
- 对选择题写出排除干扰项的依据，而不只记忆答案字母；
- 对源文档提供的综合题完成推导、算法设计或复杂度分析。
前置知识
建议先阅读第 4 章对应教材，再开始本组练习。
环境、输入与预期输出
- 环境：任意现代浏览器；综合题建议准备纸笔或本地编辑器。
- 输入：12 道四选一选择题，1 道综合题。
- 预期输出：一份独立作答记录，以及每道错题或综合题的完整推理过程。
作答方法
- 选择题先独立判断并记录依据，再点击“提交答案”；
- 提交后核对正确答案和解析，做错的题使用“重新作答”；
- 综合题先完成推导、伪代码或代码，再展开参考答案逐项核对；
- 对重复出现的真题，说明它在不同知识主题下分别考查了什么。
选择题
答题进度已答 0/12正确 0
难度★★★考点由遍历序列构造二叉树、前序遍历、后序遍历、前序+后序、二叉树重构、唯一性判断
若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点( )。
难度★★考点前序遍历、中序遍历、二叉树基础（性质+存储）、二叉树遍历、先序遍历
要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶节点须满足的条件是( )。
难度★★★考点二叉树基础（性质+存储）、前序遍历、后序遍历、二叉树、先序遍历、遍历序列重建
已知一棵二叉树的树形如下图所示，若其后序遍历为 f, d, b, e, c, a，则其先序序列为( )。
1(2(4(_, 6), 5), 3)
结构（文字版）（节点按层序由 1 到 6 编号；编号仅为表述方便，原题节点皆为空圆）：根 1 的左孩子是 2、右孩子是 3（叶子）；2 的左孩子是 4、右孩子是 5（叶子）；4 没有左孩子，右孩子是 6（叶子）。
难度★★考点前序遍历、二叉树遍历、递归
对下列二叉树进行前序遍历，输出序列是( )。
A(B(D, E(G, _)), C(_, F))
难度★★★考点前序遍历、二叉树遍历、递归
对下列二叉树进行前序遍历，输出序列是( )。
1(2(4, 5), 3(6(_, 8), 7))
难度★★★考点前序遍历、非递归、栈
用栈实现前序遍历的非递归算法：从根开始，每次 pop 出栈顶结点立刻访问它，然后把右孩子先压栈、再把左孩子压栈（保证左孩子下次先出栈），栈空时结束。栈状态约定记为 [栈底, ..., 栈顶]（左端为栈底）。对二叉树 1(2(4, 5), 3(6, 7)) 执行该算法，第 3 次 pop 操作完成之后、第 4 次 pop 之前那一刻，栈中元素是( )。
难度★★★★考点前序遍历、非递归、算法步骤、栈
用一个栈实现二叉树前序非递归遍历，循环体的核心操作顺序如下四种（循环条件统一为"栈非空"，初始已 push(root)）。其中正确的是( )。
难度★★★★考点前序遍历、应用、复制二叉树、递归
要"复制一棵二叉树"——递归创建一棵新二叉树，其结构与原树完全相同（每个原结点对应一个新建的结点）。下列遍历顺序中最适合直接套用复制算法的是( )。
难度★★★★考点前序遍历、中序遍历、二叉树构造
已知一棵二叉树的前序遍历为
难度★★★★★考点前序遍历、综合、性质判断
关于二叉树的前序遍历，下列说法全部正确的选项是( )。
① 前序序列的第一个元素必然是整棵树的根。 ② 前序序列与后序序列相同 ⇒ 该二叉树只有一个结点。 ③ 树的先根遍历 = 对应二叉树（孩子兄弟法转换后）的前序遍历。 ④ 仅知道前序序列就能唯一确定一棵二叉树。
难度★★★★考点前序遍历、先序遍历、结点编号、遍历次序反推、中序遍历、层次遍历
按某种顺序对二叉树的结点进行编号，编号为
答案总览（建议完成全部题目后查看）
- 第 1 题：C
- 第 2 题：A
- 第 3 题：B
- 第 4 题：A
- 第 5 题：A
- 第 6 题：C
- 第 7 题：B
- 第 8 题：A
- 第 9 题：B
- 第 10 题：C
- 第 11 题：B
- 第 12 题：B
综合题
综合题 1｜2014 年真题第 41 题
难度：★★★★ · 分值：13 分
考点：树与森林、前序遍历、二叉树、WPL、带权路径长度、先序遍历、算法设计
二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 T，采用二叉链表存储，结点结构为：
+--------+--------+--------+
| left | weight | right |
+--------+--------+--------+其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向 T 的根结点的指针，请设计求 T 的 WPL 的算法。要求：
(1) 给出算法的基本设计思想。
(2) 使用 C 或 C++ 语言，给出二叉树结点的数据类型定义。
(3) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
参考答案与详细解析
详细解析
(1) 设计思想
答案：递归遍历二叉树，传递当前结点的深度 depth；遇到叶结点时累加 weight × depth，遇到内部结点则递归左右子树（depth+1）。
为什么这种 DFS 就能算 WPL？
WPL（Weighted Path Length）= 所有叶子的（权值 × 路径长度）之和。每个叶子的"路径长度"就是从根到该叶子的边数（也即该叶子的深度，根定为深度 0）。一次 DFS 自然地把"深度"作为递归参数向下传递：
- 进入新结点 depth+1；
- 到达叶子时（左右孩子都为 NULL）：贡献
node->weight × depth； - 内部结点不贡献——题面明确"叶结点的 weight 域保存权值"，内部结点的 weight 不计入 WPL。
实现细节：
- 主函数调用一次
wplDfs(root, 0)，根的深度从 0 开始； - 递归函数判断：
node == NULL→ return 0；- 是叶子（左右子树都空）→ return
weight × depth； - 否则 → return 左子树 WPL + 右子树 WPL。
(2) 二叉树结点的数据类型定义
c
typedef struct TreeNode {
struct TreeNode *left; // 左孩子指针
int weight; // 叶结点的权值
struct TreeNode *right; // 右孩子指针
} TreeNode;字段顺序对照题面给的结构图（left | weight | right）。
weight在内部结点不使用，但所有结点共用同一类型，便于树的统一构造与遍历。
(3) 代码实现
c
static int wplDfs(TreeNode *node, int depth) {
if (node == NULL) return 0; // 空树或空指针：贡献 0
// 判断叶结点（左右子树都为 NULL）
if (node->left == NULL && node->right == NULL) {
return node->weight * depth; // 叶子：贡献 weight × 深度
}
// 内部结点：递归累加左右子树的 WPL，深度 +1
return wplDfs(node->left, depth + 1)
+ wplDfs(node->right, depth + 1);
}
int wpl(TreeNode *root) {
return wplDfs(root, 0); // 根的深度从 0 起算
}关键点说明：
- 叶子判定 = 左右孩子都 NULL：本题二叉链表，没有"度为 1 的中间结点"作为叶子——题面默认"叶 = 左右都空"。如果是表达式树等会出现"单孩子结点"的场景，要按题意单独判。
- 根的深度从 0 起：题中"路径长度"指边数，根到自己 0 条边。如果题目改成"层数从 1 起"，把初始 depth 改 1 即可，递归形态不变。
- 递归 vs 迭代：本题用递归最自然；用迭代（BFS + 队列携带深度）也能实现，但代码繁、空间也是 O(n)，不划算。
- 复杂度：时间 O(n)，每个结点访问一次；空间 O(h)，递归栈深 = 树高。最坏（退化链状树）h = n，平均（平衡树）h = log n。
编者注（生僻术语）：WPL 是哈夫曼编码的核心评价指标。哈夫曼树就是"在所有叶子权值固定的二叉树中 WPL 最小的那棵"。本题不要求构造最优树，只要求会算 WPL——即对任意给定二叉树（可能根本不是哈夫曼树），按定义遍历求和。
完成清单
复盘
- 哪道题最容易因遍历顺序、层次口径或结构关系判断失误？
- 我能否不用背答案，重新画树或写出访问过程？
- 如果题目改变一个条件，原结论是否仍成立？