二叉树 · 考纲词条练习

考点：树与结点的术语（A1）。

（A1）考点：**叶子结点（叶）**是没有子结点的结点——它是树的"末端"。

解析：叶子是度数为 0 的结点；树最顶端的结点叫根，其余有孩子的结点叫内部结点。

排除法：A 内部结点是"有孩子"的结点；B 兄弟结点是同一父结点下的结点；C 根结点是树最顶端的结点。

考点：二叉树的定义（A2）。

（A2）考点：二叉树每个结点最多两个子结点，且左右次序确定（左孩子和右孩子是不同位置）。

解析：二叉树可以是空树；区分左右（左右互换是两棵不同的树）。

排除法：A 二叉树的子结点可以少于两个（0 或 1 个都行）；B "度数为 2"要求每个结点恰有两个孩子，比二叉树的定义更严；C 最多是 2 个而不是 4 个。

考点：结点与边的关系（A3）。

（A3）考点：$n$ 个结点的树恰好有 $n-1$ 条边——除根外每个结点恰好由一条边连上来。

解析：每个非根结点对应一条"父子边"，$n$ 个结点去掉根就是 $n-1$ 条边。

排除法：A 边数比结点多 1 不可能（那会成环）；B 是"每个结点 2 条边"的思路；D 与结点数相同（那是环或误记）。

考点：第 i 层最多结点数（A4）。

（A4）考点：二叉树第 $i$ 层（根为第 1 层）最多 $2^{i-1}$ 个——第 4 层最多 $2^3 = 8$。

解析：每往下一层结点数最多翻倍：1、2、4、8……

排除法：A 是层数本身；B 是前 4 层的总数 $15$；C 是第 5 层的上限 $16$。

考点：深度为 k 的最多结点数（A5）。

（A5）考点：深度为 $k$ 的二叉树最多 $2^k - 1$ 个结点（满二叉树）——深度 4 最多 $15$。

解析：$1+2+4+8 = 15 = 2^4 - 1$。

排除法：A 是第 4 层的结点数；B 是 $2^4 = 16$（忘减 1）；D 是 $2^3 - 1$（少算一层）。

考点：叶子数与度 2 结点数（A6）。

（A6）考点：任何二叉树都有 $n_0 = n_2 + 1$——叶子数比度 2 的结点数多 1。

解析：由 $n = n_0 + n_1 + n_2$ 和 $n - 1 = n_1 + 2n_2$（边数按度统计）联立消元得到，与树形无关、恒成立。

排除法：A 把方向记反；B 两者有严格的数量关系；D 是"相等"（只在特殊情况下成立）。

考点：树的高度定义（A7）。

（A7）考点：高度 = 根到最深叶子的路径上的结点数（根的高度为 1，这也是 CSP 真题口径）。

解析：单根树高度 1；给根加一个孩子高度变 2。

排除法：A 是边数口径（有些书的高度定义，但 CSP 约定结点数）；C 是总结点数；D 是路径边数（与 A 同口径）。

考点：满二叉树的定义（B1）。

（B1）考点：满二叉树每层结点数都达到最大值——第 $i$ 层恰好 $2^{i-1}$ 个。

解析：满二叉树的叶子全在同一层，没有任何空缺。

排除法：A 任何一层缺结点就不是满；B 最后一层可以不满是"完全二叉树"的特点；C 只有根有孩子是最小的树。

考点：完全二叉树的定义（B2）。

（B2）考点：完全二叉树除最后一层外每层都满，最后一层结点从左到右连续（不能有空档）。

解析：完全二叉树可以按层序紧凑地存进数组，这是它与"普通二叉树"的核心区别。

排除法：A "每个结点恰有两个孩子"是满二叉树的特征；B 每一层都满也是满二叉树；C 完全二叉树不一定是满的（最后层可以不满）。

考点：满二叉树的结点数（B3）。

（B3）考点：深度 $k$ 的满二叉树有 $2^k - 1$ 个结点——深度 5 满树 $2^5-1 = 31$。

解析：$1+2+4+8+16 = 31$。

排除法：A 是 $2^5 = 32$（忘减 1）；B 是第 5 层结点数 $16$；D 是深度 6 的满树 $63$。

考点：完全二叉树的高度公式（B4）。

（B4）考点：$n$ 个结点的完全二叉树高度 $= \lfloor \log_2 n \rfloor + 1$——$61$ 个结点：$2^5 \le 61 < 2^6$，高度 6。

解析：$32 \le 61 \le 63$，落在深度 6 的范围内（$2^5$ 到 $2^6-1$）。真题 2020 年原题。

排除法：A 是 $2^4$ 范围（16~31 个结点才对应高度 5）；B 是 $2^7$ 范围的高度；C 是 $2^6$ 范围（64~127 个结点才对应高度 7）。

考点：完全二叉树的形态数（B5）。

（B5）考点：高度 $k$ 的完全二叉树形态数 = 最后一层的结点数取法 = $2^{k-1}$——高度 3 有 $4$ 种。

解析：前两层固定满（1+2 个），第 3 层可以放 $1\sim4$ 个结点，共 4 种形态。真题 2021 年问"高度 5 的完全二叉树有几种形态"，答案 $2^4 = 16$ 种。

排除法：A 只数了 3 种（漏了满的情况）；B 只数了 2 种；D 是 $2^3-1$ 的混淆。

考点：满与完全的区别（B6）。

（B6）考点：满二叉树一定是完全二叉树（每层都满当然满足"最后层连续"），反之不然。

解析：满 ⇒ 完全；完全只要求最后层连续，前面层满。

排除法：A 两者有包含关系（满 ⊂ 完全）；B 反了；D 完全二叉树最后一层可以不满。

考点：顺序存储的孩子下标（B7）。

（B7）考点：下标从 1 开始，结点 $i$ 的左孩子是 $2i$、右孩子是 $2i+1$。

解析：完全二叉树按层序编号，左孩子编号恰是父编号的两倍。

排除法：A 是右孩子；C 是父结点（向下取整的 $i/2$）；D 是下一个结点（层序相邻，不是孩子）。

考点：前序遍历（C1）。

（C1）考点：前序 = 根左右——先访问根，再左子树、右子树。

解析：根 A → 左子树（B 为根：B、D、E）→ 右子树 C：ABDEC。

排除法：A 左右子树顺序写错（E 和 B 的位置颠倒了）；B 是中序的结果；C 是后序的结果。

考点：中序遍历（C2）。

（C2）考点：中序 = 左根右——先左子树、再根、后右子树。

解析：左子树（D、B、E）→ 根 A → 右子树 C：DBEAC。

排除法：A 是前序；B 是层序；C 是后序。

考点：后序遍历（C3）。

（C3）考点：后序 = 左右根——先左子树、右子树，最后根。

解析：左子树（D、E、B）→ 右子树 C → 根 A：DEBCA。

排除法：A 是中序；B 无此顺序（左右子树的根顺序错乱）；D 是前序。

考点：层序遍历（C4）。

（C4）考点：层序 = 从上到下、每层从左到右——按"层"访问。

解析：A → B、C → D、E：ABCDE。

排除法：A 是前序；B 是后序；C 是中序。

考点：三序的根结点位置（C5）。

（C5）考点：前序根最先访问、后序根最后访问——中序的根在中间。

解析：前序第一个必是根；后序最后一个必是根；中序根把序列分成左、右两段（还原树的关键）。

排除法：A 后序不是"根最先"；B 前序不是"根最后"；D 中序的根在中间而非最后。

考点：前序+中序还原（C6）。

（C6）考点：前序第一个是根，用它在中序里分割左右子树，递归还原——前序 ABDEC + 中序 DBEAC → 后序 DEBCA。

解析：根 A；中序左段 DBE（3 个）右段 C；左子树前序 BDE、中序 DBE → 根 B，左 D、右 E；得树后后序 DEBCA。

排除法：A、B 是原前序/中序（没有转换）；D 是层序。

考点：后序+中序还原（C7）。

（C7）考点：后序最后一个（A）是根，在中序分割后递归——后序 DGJHEBIFCA + 中序 DBGEHJACIF → 前序 ABDEGHJCFI。真题 2019 年原题。

解析：根 A；中序左段 DBGEHJ、右段 CIF；左子树后序 DGJHEB、中序 DBGEHJ → 根 B，左 D，右子树（根 E，左 GJH）……递归得前序 ABDEGHJCFI。

排除法：A 是"把序列某处字母换位"的干扰（G 与 H 换位）；C 是中序原序列；D 是 ABCDEFGHIJ 的想当然排列。

考点：根下标从 1 开始（D1）。

（D1）考点：顺序存储二叉树的根存放在下标 1（下标 0 不用，这是 CSP 惯例）。

解析：从 1 编号使得"父 $i$ → 左 $2i$、右 $2i+1$"的公式最简洁。

排除法：A 下标 2 是根的左孩子；B 任意位置编号公式就不成立；C 是"数组下标从 0 起"的语言习惯，不是树的存储约定。

考点：左孩子下标 2i（D2）。

（D2）考点：结点 $i$ 的左孩子下标 $= 2i$——下标 5 的左孩子是 10。

解析：$2 \times 5 = 10$。

排除法：A 是"层序相邻"（兄弟位置不对，6 与 5 不满足公式）；B 是右孩子 $11$；C 是父结点的思路。

考点：右孩子下标 2i+1（D3）。

（D3）考点：结点 $i$ 的右孩子下标 $= 2i+1$——下标 5 的右孩子是 11。

解析：$2 \times 5 + 1 = 11$。

排除法：A 是 $2i+2$ 的错式（从 0 编号的变形）；B 是左孩子；D 无依据。

考点：父结点下标（D4）。

（D4）考点：结点 $i$ 的父结点下标 $= \lfloor i/2 \rfloor$——下标 9 的父是 4。

解析：$9 \div 2 = 4.5$，向下取整为 4。

排除法：A 是"一半加 1"的错式；B 是"乘以 2"（那是求孩子）；C 是兄弟的邻位（8 是 9 的兄弟）。

考点：兄弟结点下标（D5）。

（D5）考点：兄弟结点下标相邻——偶数（左孩子）的兄弟是它加 1，奇数（右孩子）的兄弟是它减 1：下标 9（奇数）的兄弟是 8。

解析：9 是奇数，说明它是右孩子，兄弟（左孩子）是 $9-1=8$。真题 2022 年考过这个。

排除法：A 是"左孩子的兄弟"方向（把 9 当左孩子）；B 是 9 本身；D 无依据。

考点：数组存储的连续性（D6）。

（D6）考点：完全二叉树按层序存储连续无空洞——这正是它适合数组存储的原因。

解析：完全二叉树的层序编号恰好填满 $1..n$，父与子下标可直接计算。

排除法：B 必须按层序（不是后序）存储；C 非完全二叉树层序存储会有空洞（NULL 占位）；D 叶子存前面无此规定。

考点：数组下标综合（D7）。

（D7）考点：综合公式——下标 9 的结点：父 4、兄弟 8、左孩子 18、右孩子 19。真题 2022 年原题。

解析：$2 \times 9 + 1 = 19$。

排除法：B 是左孩子（$2 imes 9 = 18$）；C 是兄弟结点（$9 - 1$）；D 是父结点的孩子下标混淆。

考点：哈夫曼树的定义（E1）。

（E1）考点：哈夫曼树是带权路径长度（WPL）最小的二叉树。

解析：给定权值集合，哈夫曼树让"权大离根近、权小离根远"，从而 WPL 最小。

排除法：A 哈夫曼树深度不保证最小（完全均衡时深度最小，但那是另一种目标）；B 不一定满（只有特定权值才恰好满）；D 与二叉搜索树是两回事（哈夫曼树不要求左小右大）。

考点：WPL 计算（E2）。

（E2）考点：WPL = Σ(叶子权值 × 路径长度)——权值 $2,3,4,5$ 的哈夫曼树 WPL = $5\times1 + 4\times2 + 2\times3 + 3\times3 = 28$。

解析：构造：$2+3=5$；$4+5=9$；$5+9=14$。最大权 5 深度 1、次大 4 深度 2、最小两个深度 3。

排除法：A 是权值总和；B 是"等深"的近似；D 是少算了一层。

考点：哈夫曼编码的本质（E3）。

（E3）考点：哈夫曼编码本质是贪心策略——每次选最小的两个合并，局部最优导向全局最优。真题 2021 年原题。

解析：贪心正确性由哈夫曼树的 WPL 最优性保证。

排除法：A 分治是"拆大问题"；C 动态规划要记录子问题重叠解；D 回溯是穷举式搜索。

考点：构造的贪心过程（E4）。

（E4）考点：哈夫曼构造每步取权值最小的两个结点合并成一个新结点（权值为两者之和）。

解析：反复取最小两个，直到只剩一棵树。

排除法：A、D 按深度取是错的（构造过程不看深度）；C 取最大两个是"最大化"思路，与最小 WPL 目标相反。

考点：前缀码概念（E5）。

（E5）考点：前缀码中任何一个编码都不是另一个编码的前缀——这样才能无歧义地切分码流。

解析：如 {0, 10, 110, 111} 中 0 不是 10 的前缀、10 不是 110 的前缀……解码时从左到右扫到匹配即切分，不会二义。

排除法：B 前缀码通常是变长的（这正是它的意义）；C 同 B；D 前缀码不要求以 0 开头。

考点：编码长度计算（E6）。

（E6）考点：构造哈夫曼树后，字母的编码长度 = 其叶子深度。频率 10/15/30/16/29：先并 $10+15=25$，再并 $16+25=41$，$29+30=59$，最后 $41+59$——$d$（16%）深度 2，编码长度 2 位。真题 2022 年原题。

解析：d 在第 2 层（41 子树的孩子），所以编码 2 位。

排除法：A、C、D 都是构造顺序弄错时各字母深度算错的结果。

考点：哈夫曼与等长编码比较（E7）。

（E7）考点：哈夫曼编码高频字符用短码、低频用长码，总编码长度通常更短；编码表是必须的。

解析：等长编码每个字符一样长；哈夫曼按频率分配长度，压缩效果来自频率分布不均。

排除法：B 频率完全均匀时哈夫曼与等长一样长，不会"总是更短"；C 哈夫曼必须有编码表（否则无法解码）；D 固定长度是等长编码的特点。

考点：编码的合法性验证（E8）。

（E8）考点：验证前缀码——逐对检查"任一码是否是另一码的前缀"：{0, 10, 110, 111} 合法。

解析：0 不是 10 的前缀（10 以 1 开头）、10 不是 110 的前缀（110 第三位是 0，10 两位后无此结构）……逐对检查通过，是合法前缀码。真题 2023 年考过同类验证。

排除法：B 的说法本身错误（0 和 10 的开头不同）；C 变长恰恰是哈夫曼码的正常形态；D 等长不是合法性的要求。

考点：BST 的定义（F1）。

（F1）考点：二叉搜索树（BST）：左子树所有结点 < 根 < 右子树所有结点，且左右子树也递归满足。

解析：注意是"整个子树"的比较，不是只看直接孩子——这是 BST 定义最容易理解错的地方。

排除法：A 中序遍历是升序的；C 说反了方向；D 根只是中间值，不是最大值（最大值在最右）。

考点：BST 查找路径（F2）。

（F2）考点：BST 查找最坏 $O(n)$——当插入顺序单调时树退化成一条链（链表），每次查找要走到链尾。

解析：只有平衡的 BST 才有 $O(\log n)$；普通 BST 不保证平衡，最坏退化成链表。真题 2024 年考过类似结论。

排除法：A $O(\log n)$ 需要"平衡"前提；C $O(1)$ 不可能（至少要比较几次）；D 没有这么差。

考点：BST 插入（F3）。

（F3）考点：BST 插入第一个元素成为根——空树插 5，5 是根。

解析：5, 3, 8：5 先插入为根，3 比 5 小放左、8 比 5 大放右。

排除法：B 根不确定是错的（根就是第一个插入的值）；C、D 是后插入的结点。

考点：BST 中序有序（F4）。

（F4）考点：BST 的中序遍历恰好是升序序列——这是 BST 的核心性质（也是验证 BST 的依据）。

解析：左子树（小）→ 根（中）→ 右子树（大），递归起来整体升序。

排除法：A 无规律（那是普通树）；C 按插入顺序是"插入序列"不是中序；D 降序是"左右反过来的树"的性质。

考点：BST 最小值（F5）。

（F5）考点：BST 最小值 = 一直向左走到头（最左下的结点）。

解析：BST 性质保证左子树全小，所以最左下的叶子（或最左的无左孩子结点）就是最小值。

排除法：B 根只是中间值；C 中序第一个元素其实就是"最左下"，但选项描述不完整（"不一定是"的自相矛盾说法）；D 向右走是最大值的方向。

考点：判断 BST（F6）。

（F6）考点：判断 BST 最可靠的方法 = 中序遍历是否严格递增。

解析："每个结点大于左孩子小于右孩子"只是必要条件（可能整个左子树有比根大的漏网之鱼），中序递增才是充要条件。

排除法：B、C 都是局部条件的陷阱；D 前序有序不是 BST 的特征。

考点：递归求结点数（G1）。

（G1）考点：count(t) = count(左) + count(右) + 1——结点数 = 左子树 + 右子树 + 自己。

解析：3 结点满树：根 1 + 左 1 + 右 1 = 3。

排除法：A 只数了根；C 把空指针也算了一个；D 只数了孩子。

考点：递归求深度（G2）。

（G2）考点：depth = max(左深, 右深) + 1——单根树返回 1（左右都空，max(0,0)+1）。

解析：空树返回 0 是递归出口，单根 = max(0,0)+1 = 1。

排除法：B 是 2 层树的值；C 是把"空树返回 0"当成了根的结果；D 是空树的值。

考点：递归求叶子数（G3）。

（G3）考点：叶子 = 左右孩子都空的结点；叶子数 = 左叶子 + 右叶子。

解析：3 结点满树：根有孩子（不是叶子），左右孩子都是叶子 → 2。

排除法：A 只数了左叶子；C 把根也当叶子了；D 是空树的结果。

考点：遍历输出代码（G4）。

（G4）考点：先输出当前结点、再递归左右——这是前序（根左右）。

解析：cout 在两次递归之前 → 根最先输出 → 前序。

排除法：B 中序是"先左、输出、再右"；C 层序要用队列不是递归；D 后序是"先左、再右、最后输出"。

考点：BST 查找代码（G5）。

（G5）考点：利用 BST 有序性查找——相等返回真，比根小去左子树、大去右子树，空指针返回假。

解析：这是标准的 BST 二分式查找递归实现。

排除法：B 插入要修改树结构（该函数只读）；C、D 与代码逻辑完全不符。

考点：三种遍历别记混（H1）。

（H1）考点："序"指的是访问根结点的先后——前=最先、中=中间、后=最后。

解析：三种遍历对左右子树的访问顺序都是先左后右，差别只在根何时出现。

排除法：A 与结点总数无关；C 与深度无关；D 与值大小无关（遍历不排序）。

考点：完全与满的区别（H2）。

（H2）考点：深度 $k$ 的完全二叉树结点数范围 $2^{k-1} \sim 2^k-1$——深度 3 是 $4 \sim 7$。

解析：最少 = 前两层满 + 最后一层 1 个 = 4；最多 = 满树 = 7。

排除法：A 是深度 3 的第 3 层范围；C 漏了"不满"的所有情况；D 下界 1 是"深度 1"的范围。

考点：下标从 1 开始的陷阱（H3）。

（H3）考点：下标从 0 开始时公式变为左孩子 $2i+1$、右孩子 $2i+2$——从 1 开始才用 $2i$、$2i+1$。

解析：下标从 0 编号时，结点 $j$ 的左孩子是 $2j+1$、右孩子是 $2j+2$——比"从 1 编号"的公式各多 1。

排除法：B 是从 0 编号的右孩子；C 是"从 1 编号的左孩子"（未换算）；D 是 $2i-1$ 的错式。

考点：WPL 计算陷阱（H4）。

（H4）考点：WPL 只统计叶子——Σ(叶子权值 × 叶子到根的路径长度)，非叶子的权值（合并出来的值）不计入。

解析：WPL = Σ 叶子权值 × 深度；把内部结点的合并值也加进去是常见错误。

排除法：B 与边权无关；C 与高度乘结点数无关；D 只求和不算路径（那是权值和）。