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. ⌊log⁡2(n+1)⌋\lfloor\log_2(n+1)\rfloor

D. ⌈log⁡2(n+1)⌉\lceil\log_2(n+1)\rceil

查看答案与解析

答案:D。

叶结点全部在相邻两层内时深度最小。理想情况下从第一层到倒数第二层为满二叉树,类比完全二叉树,可得深度为 ⌈log⁡2(n+1)⌉\lceil\log_2(n+1)\rceil。

单项选择题 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。

按关键字有序顺序插入空平衡二叉树,若关键字数 n=2k−1n=2^k-1,则一定形成满二叉树(可用 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 正确。查找、插入、删除均为 O(log⁡2n)O(\log_2n),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. 红黑树候选A

B. 红黑树候选B

C. 红黑树候选C

D. 红黑树候选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 表示红色、∅ 表示空子树,省略叶结点的空孩子。

插入后红黑树形态
11B
21B(∅,2R)
32B(1R,3R)
42B(1B,3B(∅,4R))
52B(1B,4B(3R,5R))
62B(1B,4R(3B,5B(∅,6R)))
72B(1B,4R(3B,6B(5R,7R)))

最终红结点为 4、5、7,共 3 个。

单项选择题 21

原书题目P298 · 解析P303 · 目视转录

将关键字 5,4,3,2,1 依次插入初始为空的红黑树 T,则最终形态是( )。(实心为黑,空心为红。)

A. 红黑树形态A

B. 红黑树形态B

C. 红黑树形态C

D. 红黑树形态D

查看答案与解析

答案:D。

以 B 表示黑、R 表示红、∅ 表示空子树,原书插入过程可写为:

插入后形态(根(左,右))
55B
45B(4R,∅)
34B(3R,5R)
24B(3B(2R,∅),5B)
14B(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. 平衡树候选A

B. 平衡树候选B

C. 平衡树候选C

D. 平衡树候选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) 插入初始为空的平衡二叉排序树,使每次插入后仍保持平衡。试依次画出每次插入后形成的平衡二叉排序树。

查看答案与解析

用 根(左子树,右子树) 表示树,∅ 为空,单个叶结点省略空孩子。每次插入并调整后的结果如下。

插入值平衡二叉排序树
3434
2334(23,∅)
1523(15,34)
9823(15,34(∅,98))
11523(15,98(34,115))
2834(23(15,28),98(∅,115))
10734(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)小的元素,并返回指向该结点的指针,要求平均时间复杂度为 O(log⁡2n)O(\log_2n)。每个结点除 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);
    }
}

最大查找长度取决于树高。随机生成的二叉排序树平均高度为 O(log⁡2n)O(\log_2n),平均时间复杂度也为 O(log⁡2n)O(\log_2n)。

转录核对:最后一个递归调用的秩参数,原书写为 k - t->lchild->count + 1,与前文设计思想不符。应为 k - (t->lchild->count + 1)。