7.3 树形查找·习题
复习入口
7.3 树形查找 · 7.3.1 二叉排序树的定义 · 7.3.1.1 二叉排序树的查找 · 7.3.1.2 二叉排序树的插入 · 7.3.1.3 二叉排序树的构造 · 7.3.1.4 二叉排序树的删除 · 7.3.1.5 二叉排序树的查找效率 · 7.3.2 平衡二叉树 · 7.3.2.1 AVL 的插入与平衡旋转 · 7.3.2.2 AVL 的删除 · 7.3.2.3 AVL 的查找与高度界 · 7.3.3 红黑树 · 7.3.3.1 红黑树的插入 · 7.3.3.2 红黑树的删除
本节共44题:选择题34题,综合应用题10题。每题答案紧接题目折叠显示。
文字转录进度:44/44题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P296 · 解析P300 · 目视转录
对于二叉排序树,下面说法中,( )是正确的。
A. 二叉排序树是动态树表,查找失败时插入新结点,会引起树的重新分裂和组合
B. 对二叉排序树进行后序遍历可得到有序序列
C. 用逐点插入法构造二叉排序树,若先后插入的关键字有序,二叉排序树的深度最大
D. 在二叉排序树中查找,关键字比较次数不超过结点总数的 1/2
查看答案与解析
答案:C。
插入新结点不会引起二叉排序树分裂组合。中序遍历才能得到有序序列。插入关键字有序时,树形成长链,此时深度最大,查找可能需要比较每个结点的关键字,超过结点总数的 1/2。
单项选择题 02
原书题目P296 · 解析P301 · 目视转录
按( )遍历二叉排序树得到的序列是一个有序序列。
A. 先序
B. 中序
C. 后序
D. 层次
查看答案与解析
答案:B。
由二叉排序树定义可得,中序遍历得到有序序列。
单项选择题 03
原书题目P296 · 解析P301 · 目视转录
在二叉排序树中进行查找的效率与( )有关。
A. 二叉排序树的深度
B. 二叉排序树的结点个数
C. 被查找结点的度
D. 二叉排序树的存储结构
查看答案与解析
答案:A。
二叉排序树的查找路径自顶向下,其平均查找长度主要取决于树高。
单项选择题 04
原书题目P296 · 解析P301 · 目视转录
在常用的描述二叉排序树的存储结构中,关键字值最大的结点( )。
A. 左指针一定为空
B. 右指针一定为空
C. 左右指针均为空
D. 左右指针均不为空
查看答案与解析
答案:B。
每个结点由三部分构成,左、右指针分别指向关键字较小、较大的结点。最大关键字结点位于树的最右位置,因此右指针一定为空,但可能不是叶结点。反证:若右指针非空,则右指针所指结点关键字更大,与原结点最大矛盾。
单项选择题 05
原书题目P296 · 解析P301 · 目视转录
设二叉排序树中关键字由 1~1000 的整数组成,现查找关键字 363。下述关键字序列中,不可能是在树上查找的序列是( )。
A. 2,252,401,398,330,344,397,363
B. 924,220,911,244,898,258,362,363
C. 925,202,911,240,912,245,363
D. 2,399,387,219,266,382,381,278,363
查看答案与解析
答案:C。
查找先与根比较,不同则按比较结果进入左、右子树。根据左子树值<根值<右子树值,C 中比较 911 后应转向其左子树比较 240,之后不应出现比 911 大的值,但 240 的右孩子值为 912,因此不可能正确。
单项选择题 06
原书题目P297 · 解析P301 · 目视转录
分别以下列序列构造二叉排序树,与其他 3 个序列的构造结果不同的是( )。
A. (100,80,90,60,120,110,130)
B. (100,120,110,130,80,60,90)
C. (100,60,80,90,120,110,130)
D. (100,80,60,90,120,130,110)
查看答案与解析
答案:C。
按二叉排序树的构造方法,A、B、D 的构造结果相同。
单项选择题 07
原书题目P297 · 解析P301 · 目视转录
从空树开始,依次插入 52,26,14,32,71,60,93,58,24,41 后构成二叉排序树。在树上查找 60 要比较( )次。
A. 3
B. 4
C. 5
D. 6
查看答案与解析
答案:A。
以第一个元素为根依次插入。查找先与根比较,再按结果向左或右继续。比较结点依次为 52、71、60,共 3 次。
单项选择题 08
原书题目P297 · 解析P301 · 目视转录
在含有 n 个结点的二叉排序树中查找某个关键字结点时,最多进行( )次比较。
A. n/2
B. log₂n
C. log₂n+1
D. n
查看答案与解析
答案:D。
输入序列有序时,构造的树是单支树。查找不存在的关键字或最后一个结点时,需要 n 次比较。
单项选择题 09
原书题目P297 · 解析P301 · 目视转录
五个不同结点构造的二叉查找树的形态共有( )种。
A. 20
B. 30
C. 32
D. 42
查看答案与解析
答案:D。
二叉查找树的中序序列确定,先序序列个数为 n=5 的卡特兰数。先序、中序能唯一确定二叉树,故形态共有 Catalan(5)=42 种。
单项选择题 10
原书题目P297 · 解析P301 · 目视转录
构造一棵具有 n 个结点的二叉排序树,最理想情况下的深度为( )。
A. n/2
B. n
C.
D.
查看答案与解析
答案:D。
叶结点全部在相邻两层内时深度最小。理想情况下从第一层到倒数第二层为满二叉树,类比完全二叉树,可得深度为 。
单项选择题 11
原书题目P297 · 解析P301 · 目视转录
含有 20 个结点的平衡二叉树的最大深度为( )。
A. 4
B. 5
C. 6
D. 7
查看答案与解析
答案:C。
构造高度 h 的平衡二叉树所需最少结点数满足 n₀=0、n₁=1、n₂=2、nₕ=1+nₕ₋₁+nₕ₋₂。由递推式,5 层至少 12 个结点,6 层至少 20 个结点,因此最大深度为 6。
单项选择题 12
原书题目P297 · 解析P301 · 目视转录
具有 5 层结点的平衡二叉树至少有( )个结点。
A. 10
B. 12
C. 15
D. 17
查看答案与解析
答案:B。
设 nₕ 为高度 h 的平衡二叉树的最少结点数,则 n₁=1、n₂=2、nₕ=nₕ₋₁+nₕ₋₂+1,得到 n₃=4、n₄=7、n₅=12。
单项选择题 13
原书题目P297 · 解析P302 · 目视转录
高度为 3 的平衡二叉排序树的形态共有( )种。
A. 13
B. 14
C. 16
D. 15
查看答案与解析
答案:D。
左右子树高度有三种情况:① 均为 2;② 左 1、右 2;③ 左 2、右 1。高度 1 仅一个单结点形态,高度 2 有仅左孩子、仅右孩子、左右孩子都有这 3 种形态。因此情况①有 3×3=9 种,②有 1×3=3 种,③同样有 3 种,共 9+3+3=15 种。
单项选择题 14
原书题目P297 · 解析P302 · 目视转录
在平衡二叉树的基本操作中,可能发生两次旋转的操作是( )。
A. 添加、删除结点
B. 仅删除结点
C. 仅添加结点
D. 都不会
查看答案与解析
答案:A。
插入和删除结点都可能引起 LR 或 RL 平衡旋转,发生两次旋转操作。
单项选择题 15
原书题目P297 · 解析P302 · 目视转录
将关键字 1,2,3,…,1024 依次插入初始为空的平衡二叉树中。假设只有一个根结点的二叉树高度为 0,则插入结束后的平衡二叉树高度是( )。
A. 8
B. 9
C. 10
D. 11
查看答案与解析
答案:C。
按关键字有序顺序插入空平衡二叉树,若关键字数 ,则一定形成满二叉树(可用 1~3、1~7 手工验证)。插入 1023 时,树恰为满二叉树,高度 9;插入 1024 后高度为 10。
单项选择题 16
原书题目P297 · 解析P302 · 目视转录
下列关于红黑树和 AVL 树的说法中,不正确的是( )。
Ⅰ.一棵含有 n 个结点的红黑树的高度至多为 2log₂(n+1)。
Ⅱ.若一个结点是红色的,则它的父结点和孩子结点都是黑色的。
Ⅲ.红黑树的查询效率一般要优于含有相同结点数的 AVL 树。
Ⅳ.若 AVL 树某结点的左右孩子的平衡因子都是零,则该结点的平衡因子也是零。
A. Ⅰ、Ⅲ
B. Ⅲ
C. Ⅱ、Ⅳ
D. Ⅲ、Ⅳ
查看答案与解析
答案:D。
Ⅰ、Ⅱ都是红黑树性质。AVL 是高度平衡的二叉查找树,红黑树是适度平衡的二叉查找树,因此 AVL 查询效率往往更优,Ⅲ错误。左右孩子平衡因子均为零,并不能说明左右子树高度相等,所以该结点平衡因子不一定为零,Ⅳ错误。
单项选择题 17
原书题目P297 · 解析P302 · 目视转录
下列关于红黑树和 AVL 树的描述中,不正确的是( )。
A. 两者都属于自平衡的二叉树
B. 两者查找、插入、删除的时间复杂度都相同
C. 红黑树插入和删除过程至多有 2 次旋转操作
D. 红黑树任意一个结点的左右子树高度(含叶结点)之比不超过 2
查看答案与解析
答案:C。
自平衡二叉排序树在插入和删除时自动调整,保持所定义的平衡性,两者都属于自平衡二叉树,A 正确。查找、插入、删除均为 ,B 正确。
红黑树删除结点时,情况 1 可能变为情况 2、3 或 4,情况 2 会变为情况 3,可能出现旋转次数超过 2 的情况,C 错误。从任一结点到各叶结点的路径均包含相同数目黑结点,没有连续红结点,且叶结点是黑色,因此最长与最短路径之间红结点数小于或等于黑结点数,路径长度之比不超过 2,D 正确。
单项选择题 18
原书题目P297 · 解析P302 · 目视转录
下列关于红黑树的说法中,正确的是( )。
A. 红黑树的红结点数目最多和黑结点数目相同
B. 若红黑树的所有结点都是黑色,则它一定是一棵满二叉树
C. 红黑树的任何一个分支结点都有两个非空孩子结点
D. 红黑树的子树也一定是红黑树
查看答案与解析
答案:B。
红结点数目最大可以是黑结点的 2 倍,如 3 个结点、根黑而两个孩子红的树,A 错误。从根出发到所有叶结点的黑结点数相同,若全部为黑,则一定是满二叉树,B 正确。黑结点可以有一个空叶结点孩子和一个非空红结点孩子,C 错误。某个红结点作为子树根时,该子树不满足根黑的条件,D 错误。
单项选择题 19
原书题目P297 · 解析P303 · 目视转录
下列四个选项中,满足红黑树定义的是( )。(图中实心结点为黑色,空心结点为红色。)
A. 
B. 
C. 
D. 
查看答案与解析
答案:A。
红黑树是特殊的二叉排序树,B 不满足二叉排序树性质。C 中结点 2 的左右黑结点数不同;D 中结点 3 的左右黑结点数不同,只有 A 满足定义。
单项选择题 20
原书题目P298 · 解析P303 · 目视转录
将关键字 1,2,3,4,5,6,7 依次插入初始为空的红黑树 T,则 T 中红结点个数是( )。
A. 1
B. 2
C. 3
D. 4
查看答案与解析
答案:C。
以下用“结点(左子树,右子树)”记录原书每次插入后的树形,B 表示黑色、R 表示红色、∅ 表示空子树,省略叶结点的空孩子。
| 插入后 | 红黑树形态 |
|---|---|
| 1 | 1B |
| 2 | 1B(∅,2R) |
| 3 | 2B(1R,3R) |
| 4 | 2B(1B,3B(∅,4R)) |
| 5 | 2B(1B,4B(3R,5R)) |
| 6 | 2B(1B,4R(3B,5B(∅,6R))) |
| 7 | 2B(1B,4R(3B,6B(5R,7R))) |
最终红结点为 4、5、7,共 3 个。
单项选择题 21
原书题目P298 · 解析P303 · 目视转录
将关键字 5,4,3,2,1 依次插入初始为空的红黑树 T,则最终形态是( )。(实心为黑,空心为红。)
A. 
B. 
C. 
D. 
查看答案与解析
答案:D。
以 B 表示黑、R 表示红、∅ 表示空子树,原书插入过程可写为:
| 插入后 | 形态(根(左,右)) |
|---|---|
| 5 | 5B |
| 4 | 5B(4R,∅) |
| 3 | 4B(3R,5R) |
| 2 | 4B(3B(2R,∅),5B) |
| 1 | 4B(2B(1R,3R),5B) |
单项选择题 22
原书题目P298 · 解析P303 · 目视转录
在如下红黑树中插入结点 2 且染成红色后,下一步应进行的操作是( )。(B 为黑色,R 为红色。)
8B
/ \
5B 12B
/ / \
3R 10R 14R
A. 左旋
B. 右旋
C. 变色
D. 无须调整
查看答案与解析
答案:B。
插入 2 并染红后违反“不红红”原则,且叔结点为黑色,应进行 LL 旋转:将 3 右旋至 5 的位置,2、5 分别成为 3 的左、右孩子,再将 3 染黑,2、5 染红。因此下一步应先右旋。
单项选择题 23
原书题目P298 · 解析P303 · 目视转录
【2009 统考真题】下列二叉排序树中,满足平衡二叉树定义的是( )。
A. 
B. 
C. 
D. 
查看答案与解析
答案:B。
平衡二叉树任意结点的左右子树高度差绝对值不超过 1,其他三个选项都可找到不满足条件的结点。答题时可把每个非叶结点的平衡因子都写出。
单项选择题 24
原书题目P298 · 解析P303 · 目视转录
【2010 统考真题】在下列平衡二叉树中插入关键字 48,得到新平衡二叉树。新树中,关键字 37 所在结点的左、右子结点保存的关键字分别是( )。
24
/ \
13 53
/ \
37 90
A. 13,48
B. 24,48
C. 24,53
D. 24,90
查看答案与解析
答案:C。
48 插入为 37 的右孩子,根结点 24 的平衡因子从 −1 变为 −2。新结点位于最小不平衡子树根的右子树的左子树,属于 RL 型,先右旋再左旋。调整后:
37
/ \
24 53
/ / \
13 48 90
37 的左右孩子分别为 24、53。
单项选择题 25
原书题目P298 · 解析P304 · 目视转录
【2011 统考真题】下列关键字序列,不可能成为某二叉排序树中一条查找路径的是( )。
A. 95,22,91,24,94,71
B. 92,20,91,34,88,35
C. 21,89,77,29,36,38
D. 12,25,71,68,33,34
查看答案与解析
答案:A。
左子树值小于根,右子树值大于根。A 找到 91 后转向 24,说明进入 91 的左子树,后续查找的数应均小于 91,却又查到 94,矛盾(过程中关键字波动两回路),故错误。
也可画各序列对应的查找过程:B、C、D 对应的树均为二叉排序树,A 在以 91 为根的左子树中出现了大于 91 的 94,不满足定义。
单项选择题 26
原书题目P299 · 解析P304 · 目视转录
【2012 统考真题】若平衡二叉树高度为 6,且所有非叶结点的平衡因子均为 1,则结点总数为( )。
A. 12
B. 20
C. 32
D. 33
查看答案与解析
答案:B。
所有非叶结点平衡因子为 1,即满足平衡的最少结点情况。高度 n 的左右子树高度分别为 n−1、n−2,结点数满足 Cₙ=Cₙ₋₁+Cₙ₋₂+1,C₁=1、C₂=2、C₃=4,推出 C₆=20。
画图法:画 T₁、T₂,再新建根连接 T₂、T₁ 构成 T₃,连接 T₃、T₂ 构成 T₄,直至 T₆,可数得 20 个结点。
排除法:A 的 12 个结点无法达到高度 6;C 的 32 个结点可形成最后一层仅最左叶结点的完全二叉树,虽平衡但删除部分结点后仍能满足平衡,并非最少结点情况;同理 D 错误。
单项选择题 27
原书题目P299 · 解析P304 · 目视转录
【2013 统考真题】在任意非空二叉排序树 T₁ 中,删除某结点 v 后形成 T₂,再将 v 插入 T₂ 形成 T₃。下列关于 T₁、T₃ 的叙述中,正确的是( )。
Ⅰ.若 v 是 T₁ 的叶结点,则 T₁ 与 T₃ 不同。
Ⅱ.若 v 是 T₁ 的叶结点,则 T₁ 与 T₃ 相同。
Ⅲ.若 v 不是 T₁ 的叶结点,则 T₁ 与 T₃ 不同。
Ⅳ.若 v 不是 T₁ 的叶结点,则 T₁ 与 T₃ 相同。
A. 仅Ⅰ、Ⅲ
B. 仅Ⅰ、Ⅳ
C. 仅Ⅱ、Ⅲ
D. 仅Ⅱ、Ⅳ
查看答案与解析
答案:C。
插入结点的位置总是新叶结点。若删除叶结点,重新插入后与原树相同;若删除非叶结点,删除时会用其他结点填补,重新插入后成为叶结点,所得树与原树不同。
单项选择题 28
原书题目P299 · 解析P305 · 目视转录
【2013 统考真题】将关键字 1,2,3,4,5,6,7 依次插入初始为空的平衡二叉树 T,则 T 中平衡因子为 0 的分支结点个数是( )。
A. 0
B. 1
C. 2
D. 3
查看答案与解析
答案:D。
构造过程中,插入 3 时对根 1 做 RR 调整;插入 5 时对结点 3 做 RR 调整;插入 6 时对根 2 做 RR 调整;插入 7 时对结点 5 做 RR 调整。最终得到满二叉树:
4
/ \
2 6
/ \ / \
1 3 5 7
平衡因子为 0 的分支结点是 4、2、6,共 3 个。
单项选择题 29
原书题目P299 · 解析P305 · 目视转录
【2015 统考真题】现有一棵无重复关键字的平衡二叉树(AVL),中序遍历得到一个降序序列。下列叙述中,正确的是( )。
A. 根结点的度一定为 2
B. 树中最小元素一定是叶结点
C. 最后插入的元素一定是叶结点
D. 树中最大元素一定无左子树
查看答案与解析
答案:D。
多数教材将平衡二叉树定义为高度平衡的二叉排序树,后者中序为升序,但题意相反。故本题应认为是满足高度平衡的二叉树,不一定按通常二叉排序树方向排列。仅两个结点的平衡树根度为 1,A 错误。
中序降序意味着最大元素一定无左子树,但可能有右子树,与通常排序树正好相反;最小元素也不一定是叶结点,B 错误,D 正确。最后插入结点可能导致旋转调整,因此不一定仍为叶结点,C 错误。
单项选择题 30
原书题目P299 · 解析P305 · 目视转录
【2018 统考真题】已知二叉排序树如下,元素之间应满足的大小关系是( )。
x₁
\
x₂
/
x₃
\
x₄
/
x₅
A. x₁<x₂<x₅
B. x₁<x₄<x₅
C. x₃<x₅<x₄
D. x₄<x₃<x₅
查看答案与解析
答案:C。
中序遍历 LNR 得递增序列。图中中序为 x₁,x₃,x₅,x₄,x₂,可知 x₃<x₅<x₄。
单项选择题 31
原书题目P299 · 解析P305 · 目视转录
【2019 统考真题】在任意非空平衡二叉树(AVL)T₁ 中,删除某结点 v 后形成 T₂,再插入 v 形成 T₃。下列关于 T₁、T₃ 的叙述中,正确的是( )。
Ⅰ.若 v 是 T₁ 的叶结点,则 T₁ 与 T₃ 可能不同。
Ⅱ.若 v 不是 T₁ 的叶结点,则 T₁ 与 T₃ 一定不同。
Ⅲ.若 v 不是 T₁ 的叶结点,则 T₁ 与 T₃ 一定相同。
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅱ
D. 仅Ⅰ、Ⅲ
查看答案与解析
答案:A。
插入结点在失去平衡调整前,一定插入叶结点位置。
若删除的是叶结点,删除后可能不失衡,重新插入后与原树相同;若删除导致失衡并调整,再插入后可能不同,Ⅰ正确。例如用“根(左,右)”表示树:原树 1(0,2(∅,3)),删除 0 后调整为 2(1,3),再插入 0 得 2(1(0,∅),3),与原树不同。
对绝对说法Ⅱ、Ⅲ,可举反例。删除非叶结点,且删除、插入均未发生调整时,该结点从非叶变叶,树形不同。例如 1(0,2(∅,3)) 删除 2,用右孩子 3 填补,再插入 2,得到 1(0,3(2,∅)),说明Ⅲ错误。
若删除、插入导致调整,该结点可能通过旋转继续成为非叶,与原树相同。例如原树 2(1,3),删除 2 后用 3 填补得到 3(1,∅),插入 2 得 3(1(∅,2),∅),调整后又是 2(1,3),说明Ⅱ错误。
单项选择题 32
原书题目P299 · 解析P306 · 目视转录
【2020 统考真题】下列关键字输入序列中,不能生成如下二叉排序树的是( )。
4
/ \
2 5
/ \
1 3
A. 4,5,2,1,3
B. 4,5,1,2,3
C. 4,2,5,3,1
D. 4,2,1,3,5
查看答案与解析
答案:B。
逐项验证。B 先插入 4、5、1,此后 2 成为 1 的右孩子,3 又成为 2 的右孩子,所得根的左子树是一条 1→2→3 的右链,与题图不同。
单项选择题 33
原书题目P300 · 解析P306 · 目视转录
【2021 统考真题】给定如下平衡二叉树,插入关键字 23 后,根中的关键字是( )。
20
/ \
16 30
/ \
25 40
A. 16
B. 20
C. 23
D. 25
查看答案与解析
答案:D。
23 插入为 25 的左孩子,破坏平衡。最小不平衡子树是整树,插入位置在根的右子树的左子树,需要 RL 旋转。完成后根为 25,左子树根 20,孩子 16、23;右子树根 30,右孩子 40,所以选 D。
单项选择题 34
原书题目P300 · 解析P306 · 目视转录
【2024 统考真题】一棵二叉搜索树的部分结构如下,k₁、k₂、k₃ 是对应结点中的关键字。子树 T 的任一结点中保存的关键字 x 满足( )。
k₁
/ \
子树 k₂
/ \
k₃ 子树
/ \
子树 T
A. x<k₁
B. x>k₂
C. k₁<x<k₃
D. k₃<x<k₂
查看答案与解析
答案:D。
左子树所有关键字小于根,右子树所有关键字大于根。k₂、k₃ 都在 k₁ 的右子树中,所以均大于 k₁;k₃ 在 k₂ 的左子树中,所以 k₃<k₂;T 为 k₃ 的右子树,所以 x>k₃。综合得 k₃<x<k₂。
综合应用题
综合应用题 01
原书题目P300 · 解析P306 · 目视转录
一棵二叉排序树的先序遍历序列为 (50,38,30,45,40,48,70,60,75,80)。试画出树,并求等概率下查找成功和失败的平均查找长度。
查看答案与解析
二叉排序树的中序为有序序列 (30,38,40,45,48,50,60,70,75,80)。由先序与中序可构造对应树:
50
/ \
38 70
/ \ / \
30 45 60 75
/ \ \
40 48 80
查找成功 ASL=(1×1+2×2+3×4+4×3)/10=2.9。
各空指针对应虚构失败结点,失败路径比较至其父结点。父结点在第 3 层的失败位置有 5 个,第 4 层的有 6 个,所以失败 ASL=(3×5+4×6)/11=39/11。
综合应用题 02
原书题目P300 · 解析P307 · 目视转录
按照序列 (40,72,38,35,67,51,90,8,55,21) 建立二叉排序树,画出该树,并求等概率下查找成功的平均查找长度。
查看答案与解析
按二叉排序树定义构造如下。
40
/ \
38 72
/ / \
35 67 90
/ /
8 51
\ \
21 55
ASL=(1+2×2+3×3+4×2+5×2)/10=3.2。
综合应用题 03
原书题目P300 · 解析P307 · 目视转录
依次把结点 (34,23,15,98,115,28,107) 插入初始为空的平衡二叉排序树,使每次插入后仍保持平衡。试依次画出每次插入后形成的平衡二叉排序树。
查看答案与解析
用 根(左子树,右子树) 表示树,∅ 为空,单个叶结点省略空孩子。每次插入并调整后的结果如下。
| 插入值 | 平衡二叉排序树 |
|---|---|
| 34 | 34 |
| 23 | 34(23,∅) |
| 15 | 23(15,34) |
| 98 | 23(15,34(∅,98)) |
| 115 | 23(15,98(34,115)) |
| 28 | 34(23(15,28),98(∅,115)) |
| 107 | 34(23(15,28),107(98,115)) |
原书的四次调整分别为:插入 34、23、15 后,对根 34 的子树做 LL 调整;插入 98、115 后,对根 34 的子树做 RR 调整;插入 28 后,对根 23 的子树做 RL 调整;插入 107 后,对根 98 的子树做 RL 调整。
综合应用题 04
原书题目P300 · 解析P308 · 目视转录
给定关键字集合 {25,18,34,9,14,27,42,51,38},假定各关键字查找概率相同,试画出最佳二叉排序树。
查看答案与解析
各关键字概率相等时,应构造高度最小的二叉排序树。先将关键字从小到大排序,再按折半查找判定树的构造方法构造,结果如下。
27
/ \
14 38
/ \ / \
9 18 34 42
\ \
25 51
综合应用题 05
原书题目P300 · 解析P308 · 目视转录
试编写一个算法,判断给定二叉树是否是二叉排序树。
查看答案与解析
整理注记
用中序遍历检验严格二叉排序树时,前驱初值不宜固定为-32767,否则更小的合法关键字会被误判。可用“已有前驱”标志,仅从第二个结点开始比较,并在每次独立检查前重置状态。
二叉排序树的中序序列递增。因此中序遍历给定树,若始终保持前一值比后一值小,就说明是二叉排序树。
KeyType predt = -32767; // 全局变量,中序前驱值,初值为 −∞
int JudgeBST(BiTree bt) {
int b1, b2;
if (bt == NULL)
return 1;
else {
b1 = JudgeBST(bt->lchild);
if (b1 == 0 || predt >= bt->data)
return 0;
predt = bt->data;
b2 = JudgeBST(bt->rchild);
return b2;
}
}
调用前应将 predt 重置为低于所有合法关键字的值;−32767 是原书用来表示负无穷的示例值。
综合应用题 06
原书题目P300 · 解析P308 · 目视转录
设计一个算法,求出指定结点在给定二叉排序树中的层次。
查看答案与解析
采用二叉链表存储。在二叉排序树中,每查找一次下降一层,因此查找该结点所用次数就是其层次。采用非递归查找,用 n 保存层次,直至找到给定结点。
int level(BiTree bt, BSTNode *p) {
int n = 0;
BiTree t = bt;
if (bt != NULL) {
n++;
while (t->data != p->data) {
if (p->data < t->data)
t = t->lchild;
else
t = t->rchild;
n++;
}
}
return n;
}
此流程按题设假定指定结点存在于树中。
综合应用题 07
原书题目P300 · 解析P309 · 目视转录
利用二叉树遍历思想,编写判断二叉树是否为平衡二叉树的算法。
查看答案与解析
设置 balance 标记是否平衡,平衡返回 1,否则返回 0;h 表示树高。采用后序递归:空树高度 0、balance=1;仅根结点高度 1、balance=1;其他情况分别递归求左右高度与平衡标记,树高为较高子树高度加 1。若高度差大于 1 则不平衡;若高度差不超过 1 且左右子树均平衡,则平衡。
原书代码如下。
void Judge_AVL(BiTree bt, int &balance, int &h) {
int bl = 0, br = 0, hl = 0, hr = 0;
if (bt == NULL) {
h = 0;
balance = 1;
}
else if (bt->lchild == NULL && bt->rchild == NULL) {
h = 1;
balance = 1;
}
else {
Judge_AVL(bt->lchild, bl, hl);
Judge_AVL(bt->lchild, br, hr);
h = (hl > hr ? hl : hr) + 1;
if (abs(hl - hr) < 2)
balance = bl && br;
else
balance = 0;
}
}
转录核对:原书第二个递归调用误写为
bt->lchild,根据题意和原注释“递归判断右子树”,应为Judge_AVL(bt->rchild, br, hr)。
综合应用题 08
原书题目P300 · 解析P309 · 目视转录
设计一个算法,求出给定二叉排序树中最小和最大的关键字。
查看答案与解析
最左下结点关键字最小,最右下结点关键字最大,只需找到两结点,无须比较关键字。以下假设树非空。
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;
}
综合应用题 09
原书题目P300 · 解析P309 · 目视转录
设计一个算法,从大到小输出二叉排序树中所有值不小于 k 的关键字。
查看答案与解析
右子树值均大于根,左子树值均小于根。为从大到小输出,先遍历右子树,再访问根,最后遍历左子树。
void OutPut(BSTNode *bt, KeyType k) {
if (bt == NULL)
return;
if (bt->rchild != NULL)
OutPut(bt->rchild, k);
if (bt->data >= k)
printf("%d", bt->data);
if (bt->lchild != NULL)
OutPut(bt->lchild, k);
}
也可采用中序遍历加辅助栈的方法实现。
综合应用题 10
原书题目P300 · 解析P310 · 目视转录
编写递归算法,在一棵有 n 个结点、随机建立的二叉排序树上查找第 k(1≤k≤n)小的元素,并返回指向该结点的指针,要求平均时间复杂度为 。每个结点除 data、lchild、rchild 等成员外,增加 count 成员,存储以该结点为根的子树结点个数。
查看答案与解析
整理注记
原书代码在“左子树为空、k>1”时应递归查找右子树,即return Search_Small(t->rchild,k-1),不能再访问空的左子树。通用实现还应先检查t非空及k的取值范围。
设根结点为 *t,按结点信息分类:
- 左子树为空时,k=1 则根为第 k 小元素;k≠1 则去右子树查找第 k−1 小元素。
- 左子树非空时,若左子树 count=k−1,则根即第 k 小元素;若 count>k−1,去左子树查找第 k 小元素;若 count<k−1,去右子树查找第 k−(左子树 count+1) 小元素。
对左右子树采用相同规则递归。原书代码如下。
BSTNode *Search_Small(BSTNode *t, int k) {
// k 从 1 开始,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);
}
}
最大查找长度取决于树高。随机生成的二叉排序树平均高度为 ,平均时间复杂度也为 。
转录核对:最后一个递归调用的秩参数,原书写为
k - t->lchild->count + 1,与前文设计思想不符。应为k - (t->lchild->count + 1)。