26. B

2027 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照

## 26. B

所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况，如下图所示。对于高度为 $n$、左右子树的高度分别为 $n - 1$ 和 $n - 2$、所有非叶结点的平衡因子均为1的平衡二叉树，计算总结点数的公式为 $C_{n} = C_{n - 1} + C_{n - 2} + 1, C_{1} = 1, C_{2} = 2, C_{3} = 2 + 1 + 1 = 4$，可推出 $C_{6} = 20$。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

<!-- page: 311 -->

第7章 查找
299

画图法：先画出 $T_{1}$ 和 $T_{2}$；然后新建一个根结点，连接 $T_{2}$、$T_{1}$ 构成 $T_{3}$；新建一个根结点，连接 $T_{3}$、$T_{2}$ 构成 $T_{4}$……直到画出 $T_{6}$，可知 $T_{6}$ 的结点数为 20。

排除法：对于选项 A，高度为 6、结点数为 12 的树怎么也无法达到平衡。对于选项 C，结点较多时，考虑较极端的情形，即第 6 层只有最左叶子的完全二叉树刚好有 32 个结点，虽然满足平衡的条件，但显然再删去部分结点依然不影响平衡，不是最少结点的情况。同理，选项 D 错误。

27. C

由于在二叉排序树中插入结点的位置是一个新的叶结点，若删除的是叶结点，则重新插入后得到的二叉排序树与原来的二叉排序树相同。若删除的是非叶结点，在删除过程中会找其他结点填补，重新插入后变成叶结点，则得到的二叉排序树与原来的二叉排序树不同。

28. D

利用 7 个关键字构建平衡二叉树 $T$，平衡因子为 0 的分支结点个数为 3，构建的平衡二叉树及构造与调整过程如下图所示。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

29. D

大多数教材将平衡二叉树定义为一种高度平衡的二叉排序树，二叉排序树的中序序列是一个升序序列，而题意正好相反。由此可知，命题老师认为平衡二叉树仅为一棵满足高度平衡的二叉树，不一定是二叉排序树。只有两个结点的平衡二叉树的根结点的度为 1，选项 A 错误。中序遍历后得到一个降序序列（与二叉排序树正好相反），树中最大元素一定无左子树（可能有右子树），这与二叉排序树也正好相反，也因此不一定是叶结点，选项 B 错误，选项 D 正确。最后插入的结点可能会导致平衡调整，而不一定是叶结点，选项 C 错误。

30. C

根据二叉排序树的特性：中序遍历（LNR）得到的是一个递增序列。图中二叉排序树的中序遍历序列为 $x_{1}, x_{3}, x_{5}, x_{4}, x_{2}$，可知 $x_{3} < x_{5} < x_{4}$。

31. A

在非空平衡二叉树中插入结点，在失去平衡调整前，一定插入在叶结点的位置。

若删除的是 $T_{1}$ 的叶结点，则删除后平衡二叉树可能不会失去平衡，即不会发生调整，再插入此结点得到的二叉平衡树 $T_{1}$ 与 $T_{3}$ 相同；若删除后平衡二叉树失去平衡而发生调整，再插入结点得到的二叉平衡树 $T_{3}$ 与 $T_{1}$ 可能不同。说法 I 正确。例如，如下图所示，删除结点 0，平衡二叉树失衡调整，再插入结点 0 后，平衡二叉树和以前不同。

<!-- page: 312 -->

2027年数据结构考研复习指导

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

对于比较绝对的说法 II 和 III，通常只需举出反例即可。

若删除的是 $T_{1}$ 的非叶结点，且删除和插入操作均没有导致平衡二叉树的调整（这时可以首先想到删除的结点只有一个孩子的情况），则该结点从非叶结点变成了叶结点，$T_{1}$ 与 $T_{3}$ 显然不同。例如，如下图所示，删除结点 2，用右孩子结点 3 填补，再插入结点 2，平衡二叉树和以前不同。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

若删除的是 $T_{1}$ 的非叶结点，且删除和插入操作后导致了平衡二叉树的调整，则该结点有可能通过旋转后继续变成非叶结点，$T_{1}$ 与 $T_{3}$ 相同。例如，如下图所示，删除结点 2，用右孩子结点 3 填补，再插入结点 2，平衡二叉树失衡调整，调整后的平衡二叉树和以前相同。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

## 32. B

每个选项都逐一验证，选项 B 生成二叉排序树的过程如下图所示，显然错误。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

## 33. D

关键字 23 的插入位置为 25 的左孩子，此时破坏了平衡的性质，需要对平衡二叉树进行调整。最小不平衡子树就是该树本身，插入位置在根结点的右子树的左子树上，因此需要进行 RL 旋转，RL 旋转过程如下图所示，旋转完成后根结点的关键字为 25，所以选择选项 D。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

<!-- page: 313 -->

第7章 查找
301

# 34. D

在二叉搜索树中，每个结点的左子树中的所有关键字都小于该结点的关键字，右子树中的所有关键字都大于该结点的关键字。$k_{2}$、$k_{3}$所在结点都在 $k_{1}$所在结点的右子树中，因此 $k_{2} &gt; k_{1}$、$k_{3} &gt; k_{1}$；$k_{3}$所在结点在 $k_{2}$所在结点的左子树中，因此 $k_{3} &lt; k_{2}$；子树 $T$ 是 $k_{3}$所在结点的右子树，因此子树 $T$ 中任意结点的关键字 $x$ 满足 $x &gt; k_{3}$。综合可得，$k_{3} &lt; x &lt; k_{2}$。

## 二、综合应用题

### 01. 【解答】

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

先序序列为(50, 38, 30, 45, 40, 48, 70, 60, 75, 80)，二叉树的中序序列是一个有序序列，所以为(30, 38, 40, 45, 48, 50, 60, 70, 75, 80)，由先序序列和中序序列可以构造出对应的二叉树，如左图所示。

查找成功的平均查找长度为

$$
\mathrm{ASL} = (1 \times 1 + 2 \times 2 + 3 \times 4 + 4 \times 3) / 10 = 2.9
$$

图中的方块结点为虚构的查找失败结点，其查找路径为从根结点到其父结点（圆形结点）的结点序列，所以对应的查找失败平均长度为

$$
\mathrm{ASL} = (3 \times 5 + 4 \times 6) / 11 = 39 / 11
$$

### 02. 【解答】

根据二叉排序树的定义，该序列所对应的二叉排序树如下图所示。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

平均查找长度为 $\mathrm{ASL} = (1 + 2 \times 2 + 3 \times 3 + 4 \times 2 + 5 \times 2) / 10 = 3.2$。

### 03. 【解答】

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

第一步：插入结点34,23,15后，需要根结点34的子树做LL调整。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

第二步：插入结点98,115后，需要根结点34的子树做RR调整。


<!-- page: 314 -->

2027年数据结构考研复习指导

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

第三步：插入结点28后，需要根结点23的子树做RL调整。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

第四步：插入结点107后，需要根结点98的子树做RL调整。

## 04. 【解答】

当各关键字的查找概率相等时，最佳二叉排序树应是高度最小的二叉排序树。构造过程分两步走：首先对各关键字按值从小到大排序，然后仿照折半查找的判定树的构造方法构造二叉排序树。这样得到的就是最佳二叉排序树，结果如右图所示。

## 05. 【解答】

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

对二叉排序树来说，其中序遍历序列为一个递增有序序列。因此，对给定的二叉树进行中序遍历，若始终能保持前一个值比后一个值小，则说明该二叉树是一棵二叉排序树。算法实现如下：

KeyType predt=-32767; //predt为全局变量，保存当前结点中序前驱的值，初值为-∞
int JudgeBST(BiTree bt){
int b1,b2;
//空树
return 1;
else{
b1=JudgeBST(bt->lchild); //判断左子树是否是二叉排序树
if (b1==0 || predt>=bt->data) //若左子树返回值为0或前驱大于或等于当前结点
return 0; //则不是二叉排序树
predt=bt->data; //保存当前结点的关键字
b2=JudgeBST(bt->rchild); //判断右子树
return b2; //返回右子树的结果
}
}


## 06. 【解答】

算法思想：设二叉树采用二叉链表存储结构。在二叉排序树中，查找一次就下降一层。因此，查找该结点所用的次数就是该结点在二叉排序树中的层次。采用二叉排序树非递归查找算法，用 $n$ 保存查找层次，每查找一次，$n$ 就加1，直到找到相应的结点。算法如下：

int level(BiTree bt,BSTNode *p){
int n=0; //统计查找次数
BiTree t=bt;
if (bt != NULL){
n++;
while (t->data != p->data) {

<!-- page: 315 -->

第7章 查找
303

```c
if (p->data<t->data) //在左子树中查找
t=t->lchild;
else //在右子树中查找
t=t->rchild;
n++; //层次加1
}
return n;


## 07. 【解答】

设置二叉树的平衡标记 balance，以标记返回二叉树 bt 是否为平衡二叉树，若为平衡二叉树，则返回 1，否则返回 0；h 为二叉树 bt 的高度。采用后序遍历的递归算法：

1）若 bt 为空，则高度为 0，balance=1。
2）若 bt 仅有根结点，则高度为 1，balance=1。
3）否则，对 bt 的左右子树执行递归运算，返回左右子树的高度和平衡标记，bt 的高度为最高子树的高度加 1。若左右子树的高度差大于 1，则 balance=0；若左右子树的高度差小于或等于 1，且左右子树都平衡时，balance=1，否则 balance=0。

算法如下：

void Judge_AVL(BiTree bt, int &balance, int &h) {
int bl=0, br=0, hl=0, hr=0; //左右子树的平衡标记和高度
if (bt == NULL) { //空树，高度为 0
h=0;
balance=1;
}
else if (bt->lchild == NULL && bt->rchild == NULL) { //仅有根结点，则高度为 1
h=1;
balance=1;
}
else {
Judge_AVL(bt->lchild, bl, hl); //递归判断左子树
Judge_AVL(bt->rchild, br, hr); //递归判断右子树
h = (hl > hr ? hl : hr) + 1;
if (abs(hl - hr) < 2) //若子树高度差的绝对值 < 2，则看左右子树是否都平衡
balance = bl && br; //&& 为逻辑与，即左右子树都平衡时，二叉树平衡
else
balance = 0;
}
}


## 08. 【解答】

在一棵二叉排序树中，最左下结点即关键字最小的结点，最右下结点即关键字最大的结点，本算法只要找出这两个结点即可，而不需要比较关键字。算法如下：

KeyType MinKey(BSTNode *bt) {
while (bt->lchild != NULL)
bt = bt->lchild;
return bt->data;
}
KeyType MaxKey(BSTNode *bt) {
//求出二叉排序树中最大关键字结点
while (bt->rchild != NULL)
bt = bt->rchild;
return bt->data;
}

<!-- page: 316 -->

2027年数据结构考研复习指导

## 09. 【解答】

由二叉排序树的性质可知，右子树中所有的结点值均大于根结点值，左子树中所有的结点值均小于根结点值。为了从大到小输出，先遍历右子树，再访问根结点，后遍历左子树。算法如下：

```c
void OutPut(BSTNode *bt, KeyType k)
//本算法从大到小输出二叉排序树中所有值不小于 k 的关键字
if (bt == NULL)
return;
if (bt->rchild != NULL)
OutPut(bt->rchild, k); //递归输出右子树结点
if (bt->data >= k)
printf("%d", bt->data); //只输出大于或等于 k 的结点值
if (bt->lchild != NULL)
OutPut(bt->lchild, k); //递归输出左子树的结点
}


本题也可采用中序遍历加辅助栈的方法实现。

## 10. 【解答】

设二叉排序树的根结点为 *t，根据结点存储的信息，有以下几种情况：

当 t->lchild 为空时，情况如下：

1）若 t->rchild 非空且 k == 1，则 *t 即第 k 小的元素，查找成功。
2）若 t->rchild 非空且 k != 1，则第 k 小的元素必在 *t 的右子树。

当 t->lchild 非空时，情况如下：

1）t->lchild->count == k-1，*t 即第 k 小的元素，查找成功。
2）t->lchild->count > k-1，第 k 小的元素必在 *t 的左子树，继续到 *t 的左子树中查找。
3）t->lchild->count < k-1，第 k 小的元素必在右子树，继续搜索右子树，寻找第 k-(t->lchild->count + 1) 小的元素。

对左右子树的搜索采用相同的规则，递归实现的算法描述如下：

BSTNode *Search_Small(BSTNode*t, int k) {
//在以 t 为根的子树上寻找第 k 小的元素，返回其所在结点的指针。k 从 11 开始计算
//在树结点中增加一个 count 数据成员，存储以该结点为根的子树的结点个数
if (k < 1 || k > t->count) return NULL;
if (t->lchild == NULL) {
if (k == 1) return t;
else return Search_Small(t->rchild, k-1);
}
else {
if (t->lchild->count == k-1) return t;
if (t->lchild->count > k-1) return Search_Small(t->lchild, k);
if (t->lchild->count < k-1) return Search_Small(t->rchild, k-(t->lchild->count + 1));
}
}


最大查找长度取决于树的高度。由于二叉排序树是随机生成的，其高度应是 $O(\log_2 n)$，算法的时间复杂度为 $O(\log_2 n)$。

## 7.4 B 树①和 B+树

考研大纲对 B 树和 B+树的要求各不相同：重点考查 B 树，不仅要求理解其基本特点，还要

① 也可写成“B-树”，注意这里的“-”是连接词，不能读作“减”。

<!-- page: 317 -->

第7章 查找
305

求掌握其建立、插入和删除操作；而对 B+ 树，仅考查基本概念。

## 7.4.1 B 树及其基本操作

$m$ 阶 B 树是一种自平衡的 $m$ 路查找树，其所有叶结点都位于同一层次。

**考虑语言** ▶ B 树的定义和特点（2009、2025）

具体而言，一棵 $m$ 阶 B 树或为空树，或为满足以下特性的 $m$ 叉树。

1）每个结点至多有 $m$ 棵子树，即至多包含 $m - 1$ 个关键字。
2）若根结点不是叶结点，则至少有 2 棵子树，即至少包含 1 个关键字。
3）除根结点外，所有非叶结点至少有 $\lceil m / 2\rceil$ 棵子树，即至少包含 $\lceil m / 2\rceil -1$ 个关键字。
4）每个非叶结点的结构如下

|  n | P₀ | K₁ | P₁ | K₂ | P₂ | … | Kₙ | Pₙ  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |

其中，$K_i$（$i = 1,2,\dots,n$）为关键字，且满足 $K_1 &lt; K_2 &lt; \dots &lt; K_n$；$P_i$（$i = 0,1,\dots,n$）为指向子树根结点的指针；指针 $P_{i-1}$ 所指子树中所有关键字均小于 $K_i$，指针 $P_i$ 所指子树中所有关键字均大于 $K_i$（更准确地说，介于 $K_i$ 和 $K_{i+1}$ 之间）；$n$ 为该结点中关键字的个数。

5）所有叶结点①都出现在同一层次上，且不实际存储数据（对应指针为空，可视为查找失败的外部结点，作用类似于折半查找判定树中的失败结点）。

**考虑语言** ▶ B 树中关键字数和结点数的分析（2013、2014、2018、2021）

图 7.28 所示为一棵 5 阶 B 树，可借助该实例分析 B 树的性质。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

图 7.28 一棵 5 阶 B 树的实例

1）任意结点的子树个数等于其关键字个数加 1。
2）若 B 树为空，则无结点；若非空，则根结点至少包含 1 个关键字，因此至少有 2 棵子树。
3）除根结点外，所有非叶结点至少有 $\lceil m / 2\rceil = \lceil 5 / 2\rceil = 3$ 棵子树（至少包含 $\lceil m / 2\rceil -1 = 2$ 个关键字）；至多有 5 棵子树（至多包含 $m - 1 = 4$ 个关键字）。
4）结点中的关键字从左到右严格递增。每个关键字两侧的指针指向其对应的子树：左侧指针所指子树中的所有关键字均小于该关键字，右侧指针所指子树中的所有关键字均大于该关键字。也可理解为，下层子树中的所有关键字均落在由上层结点关键字划分出的对应区间内。例如，第二层最左结点的关键字为 5 和 11，可将关键字空间划分为三个区间 $(-\infty, 5), (5, 11), (11, +\infty)$，其三个子树中的关键字分别落在这三个区间内。
5）所有叶结点（外部结点）均位于第 4 层，代表查找失败的位置。

## 1. B 树的查找

在 B 树上进行查找与二叉排序树相似，只是每个结点都是多关键字的有序表。在每个结点上

① 多数教材将 B 树的叶结点定义为失败结点，本书也采用此定义，但统考真题将 B 树的叶结点定义为最底层终端结点。

<!-- page: 318 -->

2027年数据结构考研复习指导

所做的不是二路分支决定，而是基于该结点的多个子树进行多路分支决策。

B树的查找包含两个基本操作：①在B树中定位目标结点；②在结点内查找关键字。B树常存储在磁盘上，因此前一操作是在磁盘上进行的，而后一操作是在内存中进行的，即在磁盘上找到目标结点后，先将结点读入内存，再采用顺序查找法或折半查找法。因此，在磁盘上的查找次数（目标结点在B树中的层次数）是决定查找效率的关键因素。

在B树上查找到某结点后，先在该结点的有序表中查找。若找到，则查找成功；否则，根据对应的指针信息继续在所指子树中查找。例如，在图7.28中查找关键字42，先从根结点开始，根结点只有一个关键字22，且 $42 &gt; 22$ ，因此42必定位于22的右边子树。右孩子结点包含两个关键字36和45，由于 $36 &lt; 42 &lt; 45$ ，因此42必定位于36与45之间的子树。最终在该子结点中找到42，查找成功。若查找到叶结点，则说明树中不存在该关键字，查找失败。