408 高频考点精讲:二叉排序树(Binary Search Tree, BST)¶
模块归属:数据结构 · 树与二叉树 / 查找
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:4 次(2016~2025 年:2018#6、2020#5、2022#41、2024#7)
- 历年总考查频次:6 次(含 2011#7、2013#6)
- 出题形式:单项选择题(分值 2 分)与算法综合大题(2022 年第 41 题,分值 10 分)兼备
- 命题特点:
- 理论性质考查深入:高频考查二叉排序树的中序遍历单调性定理、抽象拓扑结构下的关键字范围约束(如 2018#6、2024#7)。
- 动态构造机理常考:重点考查关键字输入序列对树形拓扑的决定性作用,考查序列插入模拟及树形同构判定(如 2020#5)。
- 算法设计与存储结构融合:2022 年第 41 题首次将顺序存储方式(数组完全二叉树映射)与二叉搜索树判定算法相结合,考查中序遍历与区间收敛的递归设计能力。
- 知识关联度高:二叉排序树是后续平衡二叉树(AVL)、红黑树、B树、B+树等高级搜索树的理论基石,具有承前启后的核心地位。
近十年考查年份分布:
2016 2017 2018 2019 2020 2021 2022 2023 2024 2025
- - √ - √ - √ - √ -
(#6) (#5) (#41) (#7)
二、 具体考察内容¶
1. 二叉排序树的数学定义与核心性质¶
(1) 递归形式化定义¶
二叉排序树(Binary Search Tree, BST),又称二叉搜索树、二叉查找树,是一棵空树,或者是具有下列性质的非空二叉树: 1. 若其左子树非空,则左子树上所有结点的关键字值均小于其根结点的关键字值; 2. 若其右子树非空,则右子树上所有结点的关键字值均大于其根结点的关键字值; 3. 其左子树、右子树也分别是一棵二叉排序树。
若用形式化谓词逻辑表示,设二叉树为 \(T\)$ \text{,根结点为} $\(r\)$ \text{,结点} $\(u\)$ \text{的关键字为} $\(\text{key}(u)\)$ \text{,其左子树结点集为} $\(V(T_L)\)$ \text{,右子树结点集为} $\(V(T_R)\),则必须满足: $\(\forall u \in V(T_L), \quad \text{key}(u) < \text{key}(r)\)$ $\(\forall v \in V(T_R), \quad \text{key}(v) > \text{key}(r)\)$ 且 \(T_L\)$ \text{与} $\(T_R\) 均为二叉排序树。
(2) 核心性质与边界认知¶
- 关键字唯一性假定:408 考研大纲范畴内,默认二叉排序树中所有结点的关键字互不相同。
- 全局约束特性:定义强调的是根结点大于左子树的所有结点,小于右子树的所有结点。仅仅满足“根大于左孩子、根小于右孩子”的局部条件,不能判定该二叉树为二叉排序树。
2. 核心定理:中序遍历严格单调性定理¶
(1) 定理陈述¶
定理:一棵二叉树是二叉排序树的充分必要条件是,对其进行中序遍历(In-order Traversal)所得到的关键字序列呈严格单调递增。
(2) 数学归纳法证明¶
- 必要性($$ \text{T \text{ 是 BST} \implies \text{中序遍历序列严格单增}} $$): 设树的高度为 \(h\)。
- 当 \(h=1\) 时,仅有根结点,序列长度为 1,显然严格单调递增。
- 假设对高度小于 \(h\) 的所有二叉排序树,其中序序列均严格单增。
- 当树高为 \(h\)$ \text{时,设根为} $\(r\)$ \text{,左子树为} $\(T_L\)$ \text{,右子树为} $\(T_R\)。二叉树的中序遍历顺序为: $\(\text{Inorder}(T) = \langle \text{Inorder}(T_L), \, r, \, \text{Inorder}(T_R) \rangle\)$ 由归纳假设,\(\text{Inorder}(T_L)\)$ \text{与} $\(\text{Inorder}(T_R)\) 自身严格单增。 又由 BST 定义,\(\forall u \in T_L, \text{key}(u) < \text{key}(r)\)$ \text{,故} $\(\text{Inorder}(T_L)\)$ \text{中最大元素(即最末元素)严格小于} $\(\text{key}(r)\)$ \text{;同理,} $\(\forall v \in T_R, \text{key}(r) < \text{key}(v)\)$ \text{,故} $\(\text{key}(r)\)$ \text{严格小于} $\(\text{Inorder}(T_R)\) 中最小元素(即首元素)。 因此,拼接后的全序列整体严格单调递增。
- 充分性($$ \text{中序遍历序列严格单增} \implies T \text{ 是 BST} $$): 同理可通过反证法与树结构递归分解易证。
3. 二叉排序树的查找与平均查找长度(ASL)¶
(1) 查找算法流程¶
在二叉排序树 \(T\)$ \text{中查找关键字} $\(key\) 的递归逻辑: 1. 若 \(T\) 为空,则查找失败,返回空指针; 2. 若 \(key == \text{key}(T)\),则查找成功,返回当前结点指针; 3. 若 \(key < \text{key}(T)\)$ \text{,则递归在左子树} $\(T_L\) 中查找; 4. 若 \(key > \text{key}(T)\)$ \text{,则递归在右子树} $\(T_R\) 中查找。
(2) 平均查找长度(Average Search Length, ASL)¶
- 查找成功的平均查找长度: $\(\text{ASL}_{\text{success}} = \frac{1}{n} \sum_{i=1}^{n} C_i\)$ 其中 \(n\)$ \text{为内部结点总数,} $\(C_i\)$ \text{为查找到第} $\(i\) 个结点所需的关键字比较次数(对应于该结点在树中的层数,根结点层数为 1)。
- 查找失败的平均查找长度: 引入外部虚结点(Failure Nodes / 叶子结点的空指针),用矩形方框表示。若外部结点总数为 \(m\)$ \text{(根据二叉树性质,} $\(n\)$ \text{个结点的二叉树具有} $\(m = n + 1\) 个空指针),则: $\(\text{ASL}_{\text{failure}} = \frac{1}{n+1} \sum_{j=1}^{n+1} C'_j\)$ 其中 \(C'_j\)$ \text{为到达第} $\(j\) 个外部失败结点所经历的比较次数(等于该外部结点的双亲结点的层数)。
(3) 查找性能分析与极值形态¶
- 最好情况:二叉排序树形态均衡,高度为 \(h = \lceil \log_2(n+1) \rceil\)$ \text{,查找的时间复杂度与折半查找相同,为} $\(O(\log_2 n)\)。
- 最坏情况:输入关键字序列按有序排列(如从小到大或从大到小),生成的二叉排序树退化为单支树,树高为 \(n\)$ \text{,查找的时间复杂度恶化为} $\(O(n)\)。
4. 动态插入与构造算法¶
(1) 插入算法机理¶
向二叉排序树插入新关键字 \(key\) 的核心法则: * 插入操作建立在查找操作的基础之上; * 若树为空,直接生成新结点作为根结点; * 若 \(key < \text{key}(T)\)$ \text{,递归向左子树插入;若} $\(key > \text{key}(T)\),递归向右子树插入; * 关键性质:任何新插入的结点必将作为新的叶子结点挂接在查找失败的外部空指针位置,原有的所有结点拓扑关系与相对层级均不发生变动。
(2) 序列输入次序与树形态多样性¶
相同的关键字集合,由于输入的排列顺序不同,构造出的二叉排序树拓扑形态可能大相径庭。 例如集合 \(\{1, 2, 3, 4\}\): * 输入序列 \(\langle 1, 2, 3, 4 \rangle \implies\) 退化为右单斜链,高度为 4; * 输入序列 \(\langle 2, 1, 4, 3 \rangle \implies\) 高度为 3 的平衡形态。
5. 二叉排序树的删除算法与指针重构¶
二叉排序树中删除结点 \(z\)$ \text{时,必须保证删除后仍维持二叉排序树性质。根据结点} $\(z\) 的度数,严格分为三种拓扑重构情形:
情形 1: 结点 z 为叶子结点 (度为 0)
[p] [p]
/ /
[z] ==> NULL
情形 2: 结点 z 仅有单支子树 (度为 1)
[p] [p]
/ /
[z] ==> [z_L]
/
[z_L]
情形 3: 结点 z 拥有双子树 (度为 2)
[p] [p]
/ /
[z] ==> [s] (中序后继的值填入)
/ \ / \
[z_L] [z_R] [z_L] [z_R'] (原 s 结点被物理删除)
- 情形 1:\(z\) 为叶子结点(度为 0)
- 处理方式:直接释放结点 \(z\)$ \text{,将其双亲结点} $\(p\) 的对应孩子指针置为 NULL。
- 情形 2:\(z\) 只有左子树或只有右子树(度为 1)
- 处理方式:令 \(z\)$ \text{的唯一子树继承} $\(z\)$ \text{的位置,直接挂接至双亲结点} $\(p\)$ \text{的对应分支指针上(“子承父业”),释放结点} $\(z\)。
- 情形 3:\(z\) 同时拥有左子树与右子树(度为 2)
- 处理方式:
- 在 \(z\)$ \text{的右子树中找到其中序后继} $\(s\)$ \text{(即右子树中关键字最小的结点,顺着右孩子的左指针一路向下直至左孩子为空);或者在} $\(z\)$ \text{的左子树中找到其中序前驱} $\(p\)(左子树中关键字最大的结点)。
- 将后继 \(s\)$ \text{的关键字复制覆盖到结点} $\(z\) 中;
- 此时问题转化为从 \(z\)$ \text{的右子树中删除结点} $\(s\)$ \text{。由于} $\(s\) 必然没有左孩子(度至多为 1),可按照情形 1 或情形 2 轻松将其删除。
(4) 删除与再插入的不可逆性定理¶
定理(2013#6 原理): * 若结点 \(v\)$ \text{是二叉排序树} $\(T_1\)$ \text{的叶子结点,删除} $\(v\)$ \text{得到} $\(T_2\)$ \text{,再将} $\(v\)$ \text{重新插入} $\(T_2\)$ \text{得到} $\(T_3\)$ \text{,则必有} $\(T_1 = T_3\)(拓扑形态完全同构)。 * 若结点 \(v\)$ \text{不是叶子结点(度为 1 或 2),删除} $\(v\)$ \text{得到} $\(T_2\)$ \text{,再将} $\(v\)$ \text{重新插入} $\(T_2\)$ \text{得到} $\(T_3\)$ \text{,则必有} $\(T_1 \ne T_3\)$ \text{。因为新插入的结点} $\(v\) 必将落入树底成为叶子结点,绝不可能恢复原先的非叶分支结点地位。
6. 二叉搜索树的判别算法原理¶
判定一棵给定二叉树是否为 BST 存在两大通用范式:
| 算法范式 | 核心思想 | 时间复杂度 | 空间复杂度 | 优缺点对比 |
|---|---|---|---|---|
| 中序遍历单调性法 | 维护前驱值 pre_val,验证访问序列是否严格单调递增 |
\(O(n)\) | \(O(h)\) | 代码逻辑简洁,符合定义本质,空间效率高 |
| 区间约束递归传导法 | 每个结点继承允许的开区间 \((low, high)\)$ \text{,自顶向下校验 | } $\(O(n)\) | \(O(h)\) | 结构直观,易于并行或局部剪枝 |
常见思维陷阱:局部性误判¶
判断二叉树是否为 BST 时,严禁仅仅判定如下局部条件: $\(\text{key}(root \to left) < \text{key}(root) < \text{key}(root \to right)\)$ 反例结构:
在上述二叉树中,对每个分支结点(10 与 15),其根值均大于直接左孩子、小于直接右孩子。但结点 6 位于根结点 10 的右子树中,却满足 \(6 < 10\),严重违反二叉排序树定义。故必须采用全局中序递增或区间约束法。7. 存储结构实现对比:链式存储与顺序存储¶
在算法实现中,二叉树可采用链式存储或顺序存储:
* 二叉链表存储:结点包含 data、lchild、rchild 指针。
* 顺序存储结构(完全二叉树编号映射):
采用一维数组 SqBiTNode[MAX_SIZE] 保存,根结点位于下标 0。对任意下标为 \(i\) 的结点:
- 其左孩子下标为 \(2i + 1\);
- 其右孩子下标为 \(2i + 2\);
- 其双亲结点下标为 \(\lfloor (i - 1) / 2 \rfloor\);
- 若数组元素值为 \(-1\)$ \text{或下标超过有效元素范围} $\(ElemNum\),表示对应位置为空结点。
三、 近十年真题精讲(2016~2025)¶
【真题 1】2024 年 408 第 7 题 · 抽象子树关键字范围约束推导¶
题目
一棵二叉搜索树如下图所示,\(K_1\)、\(K_2\)、\(K_3\)$ \text{分别是对应结点中保存的关键字、三角形表示子树。其中} $\(K_2\)$ \text{是} $\(K_1\)$ \text{的右孩子,} $\(K_2\)$ \text{的左孩子为} $\(K_3\),\(K_3\)$ \text{的右子树为} $\(T\)$ \text{。则子树} $\(T\)$ \text{中任一结点中保存的关键字} $\(X\) 满足的是( )。
A. \(X < K_1\) B. \(X > K_2\) C. \(K_1 < X < K_3\) D. \(K_3 < X < K_2\)
【解析】¶
本题考查二叉搜索树(BST)各分支的全局偏序约束继承关系。 1. 依据根与右子树性质: \(K_2\)$ \text{位于} $\(K_1\)$ \text{的右分支,以} $\(K_2\)$ \text{为根的整棵右子树内所有结点的关键字均严格大于} $\(K_1\)。 由于子树 \(T\)$ \text{属于以} $\(K_2\) 为根的子树,故必然满足: $\(X > K_1\)$ 2. 依据左子树性质: \(K_3\)$ \text{为} $\(K_2\)$ \text{的左孩子,以} $\(K_3\)$ \text{为根的整棵左子树内所有结点的关键字均严格小于} $\(K_2\)。 由于子树 \(T\)$ \text{挂接在} $\(K_3\)$ \text{之下,属于} $\(K_2\) 的左子树范畴,故必然满足: $\(X < K_2\)$ 3. 依据右子树性质: 子树 \(T\)$ \text{直接作为} $\(K_3\)$ \text{的右子树,由 BST 右子树必须大于根的定义,子树} $\(T\)$ \text{内任意结点的关键字} $\(X\) 均满足: $\(X > K_3\)$ 4. 综合不等式链: 将上述条件连立可得: $\(K_1 < K_3 < X < K_2\)$ 对照各选项,表达式 \(K_3 < X < K_2\) 准确描述了上界与紧确下界,选项 D 正确。
正确答案:D
【真题 2】2022 年 408 第 41 题 · 顺序存储 BST 判定的算法综合设计题¶
题目
已知非空二叉树 \(T\) 的结点值均为正整数,采用顺序存储方式保存,数据结构定义如下:
typedef struct {
ElemType SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
} SqBiTree;
SqBiTNode 中用 -1 表示。例如,对于下图所示的两棵非空二叉树} $\(T_1\)$ \text{和} $\(T_2\):
\(T_1\) 的存储结果如下:
\(T_2\) 的存储结果如下:下标: 0 1 2 3 4 5 6 7 8 9 10
T2.SqBiTNode: [40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35]
T2.ElemNum = 11
请设计一个尽可能高效的算法,判定一棵采用这种方式存储的二叉树是否为二叉搜索树,若是,则返回 true,否则,返回 false。要求:
(1) 给出算法的基本设计思想。
(2) 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释。
【解析】¶
(1) 算法基本设计思想¶
采用基于顺序存储二叉树的中序遍历严格单调递增性校验算法。
1. 顺序存储的映射规律:
在顺序存储结构中,根结点位于下标 \(0\)$ \text{。对于任意下标为} $\(k\) 的有效结点:
* 其左孩子保存在下标 \(2k + 1\) 中;
* 其右孩子保存在下标 \(2k + 2\) 中;
* 若下标 \(k \ge \text{ElemNum}\),或数组值 SqBiTNode[k] == -1,表示该结点为空结点。
2. BST 的充要判定准则:
二叉搜索树的充要条件为中序遍历序列严格单调递增。
3. 算法具体执行流程:
* 维护一个变量 pre_val,用于记录中序遍历过程中最新访问的前驱结点的关键字值。由于题目明确指出结点值均为正整数,初始时可将 pre_val 赋值为 \(0\)(或负无穷)。
* 按照“左子树 \(\to\)$ \text{根结点} $\(\to\) 右子树”的顺序进行递归中序遍历:
- 若当前访问的下标越界或值为 -1,视为空子树,直接返回 true;
- 递归遍历左子树,若左子树判定返回 false,则向上传递 false;
- 访问当前根结点,检查当前关键字值是否严格大于前驱记录值 pre_val:若小于或等于 pre_val,说明违反严格单调递增,算法立即返回 false;若严格大于,则将 pre_val 更新为当前结点值;
- 递归遍历右子树,并返回右子树的判定结果;
* 当全树遍历顺利完成且均满足递增约束时,返回 true。
(注:亦可采用自顶向下区间传递法 RangeJudge(k, min_val, max_val),逻辑等价,同样为满分设计)
(2) 算法实现与详细注释(C 语言)¶
#include <stdbool.h>
#define MAX_SIZE 1024
typedef int ElemType;
typedef struct {
ElemType SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
} SqBiTree;
/**
* 递归中序遍历判定辅助函数
* @param tree 指向顺序存储二叉树的指针
* @param k 当前遍历到的数组下标
* @param pre_val 指向记录中序遍历前驱结点值的指针
* @return 当前子树是否满足二叉搜索树定义
*/
bool InOrderJudge(SqBiTree *tree, int k, int *pre_val) {
// 边界条件:若下标超过有效范围,或当前结点标记为 -1,视为空子树,合法
if (k >= tree->ElemNum || tree->SqBiTNode[k] == -1) {
return true;
}
// 1. 递归判定左子树(左孩子下标为 2 * k + 1)
if (!InOrderJudge(tree, 2 * k + 1, pre_val)) {
return false;
}
// 2. 访问当前结点:检验中序序列的严格单调递增性
if (tree->SqBiTNode[k] <= *pre_val) {
return false; // 当前值小于或等于前驱值,不满足 BST 定义,返回 false
}
// 更新前驱结点值为当前访问的值
*pre_val = tree->SqBiTNode[k];
// 3. 递归判定右子树(右孩子下标为 2 * k + 2)
if (!InOrderJudge(tree, 2 * k + 2, pre_val)) {
return false;
}
return true; // 左右子树与当前结点均合法
}
/**
* 主算法接口:判断顺序存储的二叉树是否为二叉搜索树
*/
bool IsBST(SqBiTree *tree) {
if (tree == NULL || tree->ElemNum <= 0) {
return true; // 空树视为合法的二叉搜索树
}
// 题目说明结点值均为正整数,故前驱初始值设为 0 即可保证小于任意首个中序结点
int pre_val = 0;
return InOrderJudge(tree, 0, &pre_val);
}
(3) 算法复杂度分析¶
- 时间复杂度:\(O(n)\)$ \text{。算法在中序遍历过程中,对树中实际存在的} $\(n\)$ \text{个有效结点各访问一次,遇到非法情况即刻剪枝,最坏情况下遍历全部结点,故时间复杂度为线性阶} $\(O(n)\)。
- 空间复杂度:\(O(h)\)$ \text{。主要开销为递归调用工作栈的深度,等于二叉树的高度} $\(h\)$ \text{。在最坏情况下(树退化为单支树),工作栈深度为} $\(O(n)\)$ \text{;最好情况下(形态接近完全二叉树),工作栈深度为} $\(O(\log_2 n)\)。
【真题 3】2020 年 408 第 5 题 · 关键字输入序列与目标树形态匹配¶
题目
下列给定的关键字输入序列中,不能生成如下二叉排序树的是( )。
A. 4, 5, 2, 1, 3 B. 4, 5, 1, 2, 3 C. 4, 2, 5, 3, 1 D. 4, 2, 1, 3, 5
【解析】¶
本题考查二叉排序树的动态构建机理。向空的二叉排序树中逐一插入关键字,新结点必然落入查找失败的位置作为叶子结点。逐项模拟构建过程:
- 选项 A(4, 5, 2, 1, 3):
- 插入 4:生成根结点 4;
- 插入 5:\(5 > 4\),挂为 4 的右孩子;
- 插入 2:\(2 < 4\),挂为 4 的左孩子;
- 插入 1:\(1 < 4 \to 1 < 2\),挂为 2 的左孩子;
-
插入 3:\(3 < 4 \to 3 > 2\),挂为 2 的右孩子。 生成结构与目标树完全一致。
-
选项 B(4, 5, 1, 2, 3):
- 插入 4:生成根结点 4;
- 插入 5:\(5 > 4\),挂为 4 的右孩子;
- 插入 1:\(1 < 4\),挂为 4 的左孩子;
- 插入 2:\(2 < 4 \to 2 > 1\),挂为 1 的右孩子;
-
插入 3:\(3 < 4 \to 3 > 1 \to 3 > 2\),挂为 2 的右孩子。 此时生成的左子树形态退化为以 1 为根的右斜单支链(\(1 \to 2 \to 3\)),与目标树中“2 为根,1 为左孩子,3 为右孩子”的拓扑结构严重不符。故选项 B 无法生成目标树。
-
选项 C(4, 2, 5, 3, 1):
- 插入 4:根为 4;
- 插入 2:4 的左孩子为 2;
- 插入 5:4 的右孩子为 5;
- 插入 3:\(3 < 4 \to 3 > 2\),挂为 2 的右孩子;
-
插入 1:\(1 < 4 \to 1 < 2\),挂为 2 的左孩子。 与目标树完全一致。
-
选项 D(4, 2, 1, 3, 5): 同理,各结点插入位置完全符合目标拓扑。
正确答案:B
【真题 4】2018 年 408 第 6 题 · BST 拓扑结构推导中序序列与偏序关系¶
题目
已知二叉排序树如下图所示,元素之间应满足的大小关系是( )。
A. \(x_1 < x_2 < x_3\) B. \(x_1 < x_4 < x_5\) C. \(x_3 < x_5 < x_4\) D. \(x_4 < x_3 < x_5\)
【解析】¶
- 定理切入:二叉排序树的中序遍历序列(左子树 \(\to\)$ \text{根} $\(\to\) 右子树)严格单调递增。
- 中序遍历过程推演:
- 首先访问根 \(x_1\) 的左子树(为空);
- 访问根结点 \(x_1\);
- 递归中序遍历 \(x_1\)$ \text{的右子树(以} $\(x_2\) 为根):
- \(x_2\)$ \text{的左子树非空,先进入以} $\(x_4\) 为根的子树;
- \(x_4\)$ \text{的左子树非空,先进入以} $\(x_3\) 为根的子树;
- \(x_3\)$ \text{无左孩子,访问根结点} $\(x_3\);
- 访问 \(x_3\)$ \text{的右孩子} $\(x_5\);
- 回溯访问根结点 \(x_4\);
- \(x_4\)$ \text{无右子树,回溯访问根结点} $\(x_2\)。
- 确定中序遍历序列: 全树的中序遍历序列唯一确定为: $\(\langle x_1, \, x_3, \, x_5, \, x_4, \, x_2 \rangle\)$
- 依据严格递增推导偏序不等式: $\(x_1 < x_3 < x_5 < x_4 < x_2\)$ 对照各选项:
- A 项:\(x_1 < x_2 < x_3\)$ \text{与} $\(x_3 < x_2\) 矛盾,错误;
- B 项:\(x_1 < x_4 < x_5\)$ \text{与} $\(x_5 < x_4\) 矛盾,错误;
- C 项:\(x_3 < x_5 < x_4\) 准确成立,正确;
- D 项:\(x_4 < x_3 < x_5\) 颠倒了大小顺序,错误。
正确答案:C
四、 核心解题套路与易错陷阱¶
1. 核心解题套路¶
套路一:中序遍历水平投影法(秒杀大小关系题)¶
对于题目给出二叉排序树拓扑形态、求解结点关键字大小关系的题目(如 2018#6、2024#7): * 几何直观法:将整棵二叉树中的所有结点向一条水平基准线做垂直正投影。 * 判定原理:由于中序遍历顺序在几何投影上严格表现为“自左向右”的排列顺序,投影在水平线上从左到右的位置次序即为严格递增次序。
原二叉树形态:
x1
\
x2
/
x4
/
x3
\
x5
水平投影轴 (自左向右递增):
------------------------------------------>
| | | | |
x1 x3 x5 x4 x2
套路二:查找路径收敛法 / 区间夹逼检验(2011#7 经典模式)¶
在考查“下列序列中不可能构成二叉排序树查找路径的是”题型时: * 设查找目标为 \(K\)$ \text{,初始合法搜索区间为} $\((-\infty, +\infty)\); * 依次读入查找路径中的每一个关键字 \(A_i\): - 若下一步查找转向比 \(A_i\)$ \text{小的值,说明目标在左侧,当前结点的右边界收敛:} $\(high = \min(high, A_i)\); - 若下一步查找转向比 \(A_i\)$ \text{大的值,说明目标在右侧,当前结点的左边界收敛:} $\(low = \max(low, A_i)\); - 路径中后续的所有关键字必须严格落在当前开区间 \((low, high)\) 内。一旦出现任何超出区间的数字,该路径必然非法。
套路三:序列反求二叉树形态(分治建树法)¶
给定关键字序列要求判定树形态(如 2020#5): 1. 序列首个元素必为根; 2. 遍历后续序列:比根小的划归左子序列,比根大的划归右子序列(保持在原序列中的相对先后顺序); 3. 对左右子序列分别递归确定其子树根结点与分支,避免盲目画图导致的混淆。
2. 核心易错陷阱辨析¶
陷阱 1:ASL 计算中失败结点的层数统计混淆¶
- 易错点:计算 \(\text{ASL}_{\text{failure}}\) 时,误将外部虚结点本身的深度计为比较次数。
- 辨析纠正: 查找失败是在遇到空指针时判定的。到达空指针所需的关键字比较次数,等于其双亲内部结点的层数(即外部结点深度减 1)。 若题目问“到达查找失败位置比较的关键字次数”,应统计每条失败路径上实际比对过的内部结点个数。
陷阱 2:非叶结点删除后再插入的不可逆性¶
- 易错点:误认为“在二叉排序树中删除某结点再重新插入,必定能还原原树”。
- 辨析纠正: 二叉排序树的插入算法永远只能将新元素挂在最底层的叶子位置。
- 若被删元素本来就是叶子,重新插入后能够回到原位置,树形不变;
- 若被删元素是原树的内部根分支结点,重新插入后将变为叶子结点,原树结构发生永久性拓扑改变。
陷阱 3:二叉排序树判定算法的局部边界错误¶
- 易错点:在编写判定 BST 的递归算法时,仅简单比较左孩子与右孩子值。
- 辨析纠正: 必须采用中序遍历记录全局前驱,或者递归向下传递动态收紧的上下界开区间 \((\text{min}, \text{max})\)。
五、 考点速记清单¶
- 基本性质:
- 左子树所有结点 \(<\)$ \text{根} $\(<\) 右子树所有结点。
- 中序遍历序列严格单调递增(充要条件)。
- 效率表现:
- 最好时间复杂度:\(O(\log_2 n)\)(树高平衡)。
- 最坏时间复杂度:\(O(n)\)(退化为单支链表)。
- 插入与删除:
- 插入位置:查找失败的空位置,必定作为新的叶子结点插入。
- 删除度为 0 结点:直接删除,父指针置空。
- 删除度为 1 结点:单子树直接接替被删结点位置。
- 删除度为 2 结点:用其中序前驱或中序后继的值替代,转化为删除该前驱或后继。
- 叶子结点删后再插可复原;非叶结点删后再插无法复原。
- 顺序存储核心公式(从 0 标号):
- 结点 \(i\)$ \text{的左孩子为} $\(2i + 1\)。
- 结点 \(i\)$ \text{的右孩子为} $\(2i + 2\)。
- 结点 \(i\)$ \text{的双亲为} $\(\lfloor (i - 1) / 2 \rfloor\)。
- 解题速杀口诀:
- 拓扑求偏序,中序投影解;
- 路径判真伪,区间两头截;
- 序列构树形,首大即为根;
- 判定写算法,中序单增确。