5.2 二叉树的概念·习题
复习入口
5.2 二叉树的概念 · 5.2.1 二叉树的定义及其主要特性 · 5.2.1.1 几种特殊的二叉树 · 5.2.1.2 二叉树的性质 · 5.2.2 二叉树的存储结构
本节共35题:选择题29题,综合应用题6题。每题答案紧接题目折叠显示。
文字转录进度:35/35题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P133 · 解析P136 · 目视转录
下列关于二叉树的说法中,正确的是( )。
A. 度为 2 的有序树就是二叉树
B. 含有 个结点的二叉树的高度为
C. 在完全二叉树中,若一个结点没有左孩子,则它必定是叶结点
D. 含有 个结点的完全二叉树的高度为
查看答案与解析
答案:C。
在二叉树中,若某个结点只有一个孩子,则这个孩子的左右次序是确定的;而在度为 2 的有序树中,若某个结点只有一个孩子,则这个孩子就无须区分其左右次序,选项 A 错误。选项 B 仅当是完全二叉树时才有意义,对于任意一棵二叉树,高度可能为 。在完全二叉树中,若有度为 1 的结点,则只可能有一个,且该结点只有左孩子而无右孩子,选项 C 正确。完全二叉树的高度为 或 ,也可通过举例 来排除,选项 D 错误。
单项选择题 02
原书题目P133 · 解析P136 · 目视转录
“二叉树为空”意味着二叉树( )。
A. 根结点没有子树
B. 不存在
C. 没有结点
D. 由一些没有赋值的空结点构成
查看答案与解析
答案:C。
“二叉树为空”,意味着二叉树中没有结点,但并不意味着二叉树不存在。注意,线性表可以是空表,树可以是空树,但图不能是空图(图中不能没有结点)。
单项选择题 03
原书题目P133 · 解析P136 · 目视转录
下列关于完全二叉树的说法中,正确的是( )。
A. 在完全二叉树中,叶结点的双亲的左兄弟(若存在)一定不是叶结点
B. 任何一棵二叉树中,叶结点数为度为 2 的结点数减 1,即
C. 完全二叉树不适合顺序存储结构,只有满二叉树适合顺序存储结构
D. 结点按完全二叉树层序编号的二叉树中,第 个结点的左孩子的编号为
查看答案与解析
答案:A。
在完全二叉树中,叶结点的双亲的左兄弟的孩子一定在其前面(且一定存在),所以双亲的左兄弟(若存在)一定不是叶结点,选项 A 正确。 应等于 ,选项 B 错误。完全二叉树和满二叉树均可以采用顺序存储结构,选项 C 错误。第 个结点的左孩子不一定存在,选项 D 错误。
选项 B 的这种通用公式适用于所有二叉树,我们应能立即联想到采用特殊值代入法验证,如画一个只含 3 个结点的满二叉树的草图来验证是否满足条件。
单项选择题 04
原书题目P134 · 解析P136 · 目视转录
具有 10 个叶结点的二叉树中有( )个度为 2 的结点。
A. 8
B. 9
C. 10
D. 11
查看答案与解析
答案:B。
由二叉树的性质 ,得 。
【另解】画出草图。首先画出 10 个叶结点,然后每 2 个结点向上合并,构造一个新的度为 2 的分支结点,直到构成二叉树,其中度为 2 的分支结点数为 9。
单项选择题 05
原书题目P134 · 解析P136 · 目视转录
设高度为 的二叉树上只有度为 0 和度为 2 的结点,则此类二叉树中所包含的结点数至少为( )。
A.
B.
C.
D.
查看答案与解析
答案:B。
结点最少的情况:除根结点层只有 1 个结点外,其他 层均有两个结点,结点总数 。
○
├─○(叶)
└─○
├─○(叶)
└─○
⋮
├─○(叶)
└─○(叶)
单项选择题 06
原书题目P134 · 解析P136 · 目视转录
具有 个结点且高度为 的二叉树的数目为( )。
A.
B.
C.
D.
查看答案与解析
答案:D。
除根结点外,在其余 个结点中,每个结点要么是其父结点的左孩子,要么是其父结点的右孩子,每个结点都有两种可能, 个结点共有 种不同的组合形态。
单项选择题 07
原书题目P134 · 解析P136 · 目视转录
假设一棵二叉树的结点个数为 50,则它的最小高度是( )。
A. 4
B. 5
C. 6
D. 7
查看答案与解析
答案:C。
要求满足条件的树,分析可知当这 50 个结点构成一棵完全二叉树时高度最小,。
【另解】第 1 层最多有 1 个结点,第 2 层最多有 个结点,第 3 层最多有 个结点,第 4 层最多有 个结点,以此类推,可以得到 最小为 6。
单项选择题 08
原书题目P134 · 解析P137 · 目视转录
设二叉树有 个结点,且 ,则不可能存在( )的结点。
A. 个度为 0
B. 个度为 0
C. 个度为 1
D. 个度为 2
查看答案与解析
答案:C。
由二叉树的性质 1 可知 ,结点总数 ,则 ,所以 为奇数,说明该二叉树中不可能有 个度为 1 的结点。
单项选择题 09
原书题目P134 · 解析P137 · 目视转录
一个具有 1025 个结点的二叉树的高 为( )。
A. 11
B. 10
C. 11~1025
D. 10~1024
查看答案与解析
答案:C。
当二叉树为单支树时具有最大高度,即每层上只有一个结点,最大高度为 1025。而当树为完全二叉树时,其高度最小,最小高度为 。
单项选择题 10
原书题目P134 · 解析P137 · 目视转录
设二叉树只有度为 0 和 2 的结点,其结点个数为 15,则该二叉树的最大深度为( )。
A. 4
B. 5
C. 8
D. 9
查看答案与解析
答案:C。
建议画图,第一层有 1 个结点,其余 层各有 2 个结点,总结点数 ,。
单项选择题 11
原书题目P134 · 解析P137 · 目视转录
高度为 的完全二叉树最少有( )个结点。
A.
B.
C.
D.
查看答案与解析
答案:C。
高度为 的完全二叉树中,第 1 层~第 层构成一个高度为 的满二叉树,结点个数为 。第 层至少有一个结点,所以最少的结点个数 。
单项选择题 12
原书题目P134 · 解析P137 · 目视转录
已知一棵完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点,则该完全二叉树的结点个数最少是( )。
A. 39
B. 52
C. 111
D. 119
查看答案与解析
答案:A。
第 6 层有叶结点说明完全二叉树的高度可能为 6 或 7,显然树高为 6 时结点最少。若第 6 层上有 8 个叶结点,则前 5 层为满二叉树,所以完全二叉树的结点个数最少为 个结点。
单项选择题 13
原书题目P134 · 解析P137 · 目视转录
若一棵深度为 6 的完全二叉树的第 6 层有 3 个叶结点,则该二叉树共有( )个叶结点。
A. 17
B. 18
C. 19
D. 20
查看答案与解析
答案:A。
深度为 6 的完全二叉树,第 5 层共有 个结点。第 6 层最左边有 3 个叶结点,其对应的双亲结点为第 5 层最左边的两个结点,所以第 5 层剩余的结点均为叶结点,共有 个,加上第 6 层的 3 个叶结点,共有 17 个叶结点。
单项选择题 14
原书题目P134 · 解析P137 · 目视转录
一棵完全二叉树上有 1001 个结点,其中叶结点的个数是( )。
A. 250
B. 500
C. 254
D. 501
查看答案与解析
答案:D。
由完全二叉树的性质,最后一个分支结点的序号为 ,所以叶结点个数为 501。
【另解】,因为 为 1001,而在完全二叉树中, 只能取 0 或 1。当 时, 为小数,不符合题意。所以 ,于是有 。
单项选择题 15
原书题目P134 · 解析P137 · 目视转录
若一棵二叉树有 126 个结点,在第 7 层(根结点在第 1 层)至多有( )个结点。
A. 32
B. 64
C. 63
D. 不存在第 7 层
查看答案与解析
答案:C。
要使二叉树第 7 层的结点数最多,只考虑树高为 7 层的情况,7 层满二叉树有 127 个结点,126 仅比 127 少 1 个结点,只能少在第 7 层,所以第 7 层最多有 个结点。
单项选择题 16
原书题目P134 · 解析P137 · 目视转录
一棵有 124 个叶结点的完全二叉树,最多有( )个结点。
A. 247
B. 248
C. 249
D. 250
查看答案与解析
答案:B。
在非空的二叉树当中,由度为 0 和 2 的结点数的关系 可知 ;总结点数 ,其最大值为 248( 的取值为 1 或 0,当 时结点最多)。注意,由完全二叉树结点数的奇偶性可以确定 的值,但不能根据 来确定 的值。
【另解】,所以第 8 层没满,前 7 层为完全二叉树,由此可推算第 8 层可能有 120 个叶结点,第 7 层的最右 4 个为叶结点,考虑最多的情况,这 4 个叶结点中的最左边可以有 1 个左孩子(不改变叶结点数),因此结点总数 。
单项选择题 17
原书题目P134 · 解析P137 · 目视转录
某完全二叉树 T 中,结点个数最大的层有 8 个结点,则 T 中至多有( )个结点。
A. 8
B. 15
C. 23
D. 31
查看答案与解析
答案:C。
在完全二叉树中,第 4 层刚好最多有 8 个结点(前 4 层对应高度为 4 的满二叉树),若第 5 层也有 8 个结点,则对应于结点个数最多的情况,此时树高为 5,总结点数为 。
单项选择题 18
原书题目P134 · 解析P137 · 目视转录
一棵有 个结点的二叉树采用二叉链存储结点,其中空指针数为( )。
A.
B.
C.
D.
查看答案与解析
答案:B。
非空指针数=总分支数=,空指针数=结点总数-非空指针数=。
【另解】在树中,1 个指针对应 1 个分支, 个结点的树共有 个分支,即 个非空指针,每个结点都有 2 个指针域,所以空指针数 。
单项选择题 19
原书题目P134 · 解析P138 · 目视转录
设有 ()个结点的二叉树采用三叉链表表示,其中每个结点包含三个指针,分别指向其左孩子、右孩子及双亲(若不存在,则置为空),则下列说法中正确的是( )。
Ⅰ. 树中空指针的数量为
Ⅱ. 所有度为 2 的结点均被三个指针指向
Ⅲ. 每个叶结点均被一个指针所指向
A. Ⅰ
B. Ⅰ、Ⅱ
C. Ⅰ、Ⅲ
D. Ⅱ、Ⅲ
查看答案与解析
答案:A。
二叉链表表示的二叉树中空指针的数量为 ,三叉链表表示的二叉树多了一个根结点指向双亲的空指针,所以树中空指针的数量为 ,选项Ⅰ正确。若根结点的度为 2,则只有左、右两个孩子指向它,选项Ⅱ错误。若整棵树只有一个根结点,则没有指针指向它,选项Ⅲ错误。
单项选择题 20
原书题目P134 · 解析P138 · 目视转录
在一棵完全二叉树中,其根的序号为 1,( )可判定序号为 和 的两个结点是否在同一层。
A.
B.
C.
D.
查看答案与解析
答案:A。
由完全二叉树的性质,编号为 ()的结点所在的层次为 ,若两个结点位于同一层,则一定有 ,因此有 成立。
单项选择题 21
原书题目P134 · 解析P138 · 目视转录
在一个用数组表示的完全二叉树中,根结点的下标为 1,那么下标为 17 和 19 的结点的最近公共祖先的下标是( )。
A. 1
B. 2
C. 4
D. 8
查看答案与解析
答案:C。
当根结点下标为 1 时,下标为 的结点的父结点下标为 ,那么下标为 17 的祖先的下标有 8、4、2、1,下标为 19 的祖先的下标有 9、4、2、1,因此两者最近的公共祖先的下标是 4。
单项选择题 22
原书题目P135 · 解析P138 · 目视转录
假定一棵三叉树的结点数为 50,则它的最小高度为( )。
A. 3
B. 4
C. 5
D. 6
查看答案与解析
答案:C。
分析可知,满足条件的三叉树可以是完全三叉树,这棵树的第 ()层最多有 个结点。设高度为 ,则 是结点数的上限,问题是求解 的最小 值,即 ,有 。
单项选择题 23
原书题目P135 · 解析P138 · 目视转录
具有 个结点的三叉树用三叉链表表示,则树中空指针域的个数为( )。
A.
B.
C.
D.
查看答案与解析
答案:B。
三叉树采用三叉链表表示,每个结点均有 3 个指针域指向 3 个孩子,共有 个指针域,但 个结点构成的一棵树只需要 个指针(对于 条边),因此空指针域有 个。
单项选择题 24
原书题目P135 · 解析P138 · 目视转录
对于一棵满二叉树,共有 个分支结点和 个叶结点,高度为 ,则( )。
A.
B.
C.
D.
查看答案与解析
原书答案:D。
对于高度为 的满二叉树,结点总数 ,叶结点数 。
转录核对:原题将 n 定义为“分支结点数”,解析却将 n 当作“结点总数”。若按题干定义,分支结点数应为 ,D 不成立;原书答案与解析使用的是总结点数口径。
单项选择题 25
原书题目P135 · 解析P138 · 目视转录
【2009 统考真题】已知一棵完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点,则该完全二叉树的结点个数最多是( )。
A. 39
B. 52
C. 111
D. 119
查看答案与解析
答案:C。
第 6 层有叶结点,完全二叉树的高度可能为 6 或 7,显然树高为 7 时结点最多。完全二叉树与满二叉树相比,只是在最下一层的右边缺少部分结点,而最底层之上是个满二叉树,且只有最后两层上有叶结点。若第 6 层上有 8 个叶结点,则前 6 层为满二叉树,而第 7 层缺失 个叶结点,所以完全二叉树的结点个数最多为 。
单项选择题 26
原书题目P135 · 解析P138 · 目视转录
【2011 统考真题】若一棵完全二叉树有 768 个结点,则该二叉树中叶结点的个数是( )。
A. 257
B. 258
C. 384
D. 385
查看答案与解析
答案:C。
最后一个分支结点的编号为 ,所以叶结点的个数为 。
【另解】,其中 ,而在完全二叉树中, 只能取 0 或 1,当 时, 为小数,不符合题意。因此 ,所以 。
单项选择题 27
原书题目P135 · 解析P138 · 目视转录
【2018 统考真题】设一棵非空完全二叉树 T 的所有叶结点均位于同一层,且每个非叶结点都有 2 个子结点。若 T 有 个叶结点,则 T 的结点总数是( )。
A.
B.
C.
D.
查看答案与解析
答案:A。
非叶结点的度均为 2,且所有叶结点都位于同一层的完全二叉树就是满二叉树。对于一棵高度为 的满二叉树(空树 ),其最后一层全部是叶结点,数目为 ;总结点数为 。因此当 时,可以得到 。
单项选择题 28
原书题目P135 · 解析P138 · 目视转录
【2020 统考真题】对于任意一棵高度为 5 且有 10 个结点的二叉树,若采用顺序存储结构保存,每个结点占 1 个存储单元(仅存放结点的数据信息),则存放该二叉树需要的存储单元数量至少是( )。
A. 31
B. 16
C. 15
D. 10
查看答案与解析
答案:A。
二叉树采用顺序存储时,用数组下标来表示结点之间的父子关系。对于一棵高度为 5 的二叉树,为了满足任意性,其 1~5 层的所有结点都要被存储起来,即考虑为一棵高度为 5 的满二叉树,共需要存储单元的数量为 。
单项选择题 29
原书题目P135 · 解析P138 · 目视转录
【2022 统考真题】若三叉树 T 中有 244 个结点(叶结点的高度为 1),则 T 的高度至少是( )。
A. 8
B. 7
C. 6
D. 5
查看答案与解析
答案:C。
高度一定的三叉树中结点数最多的情况是满三叉树。高度为 5 的满三叉树的结点数 ,高度为 6 的满三叉树的结点数 。三叉树 T 的结点数为 244,,因此 T 的高度至少为 6。
综合应用题
综合应用题 01
原书题目P135 · 解析P139 · 目视转录
在一棵完全二叉树中,含有 个叶结点,当度为 1 的结点数为 1 时,该树的高度是多少?当度为 1 的结点数为 0 时,该树的高度是多少?
查看答案与解析
在非空的二叉树中,由度为 0 和度为 2 的结点之间的关系 ,可知 。因此总结点数 。
① 当 时,,。
② 当 时,,。
综合应用题 02
原书题目P135 · 解析P139 · 目视转录
一棵有 个结点的满二叉树有多少个分支结点和多少个叶结点?该满二叉树的高度是多少?
查看答案与解析
满二叉树中 ,由二叉树的性质 1 可知 ,即 ,,则 。分支结点个数 。
高度为 的满二叉树的结点数 ,即高度 。
综合应用题 03
原书题目P135 · 解析P139 · 目视转录
已知完全二叉树的第 9 层有 240 个结点,则整个完全二叉树有多少个结点?有多少个叶结点?
查看答案与解析
在完全二叉树中,若第 9 层是满的,则结点数 ,而现在第 9 层只有 240 个结点,说明第 9 层未满,是最后一层。1~8 层是满的,所以总结点数 。
因为第 9 层是最后一层,所以第 9 层的结点都是叶结点。且第 9 层的 240 个叶结点的双亲在第 8 层中,其双亲个数为 120,即第 8 层有 120 个分支结点,其余为叶结点,所以第 8 层的叶结点数为 。因此,总的叶结点个数 。
【另解】总结点数 ,,。若 ,则 ,不符合;若 ,则 ,则 。
注意:对于本题,应理解完全二叉树中只有最底层的结点是不满的,其他各层的结点都是满的。
综合应用题 04
原书题目P135 · 解析P139 · 目视转录
一棵高度为 的满 叉树有如下性质:根结点所在层次为第 1 层,第 层上的结点都是叶结点,其余各层上每个结点都有 棵非空子树。若按层次自顶向下,同一层自左向右,顺序从 1 开始对全部结点进行编号,试问:
- 各层的结点个数是多少?
- 编号为 的结点的双亲结点(若存在)的编号是多少?
- 编号为 的结点的第 个孩子结点(若存在)的编号是多少?
- 编号为 的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少?
查看答案与解析
1)第 1 层有 个结点,第 2 层有 个结点,第 3 层有 个结点……一般地,第 层有 个结点()。
2)在 叉树的情形下,结点 的第 1 个子女编号为 ,反过来,结点 的双亲的编号是 ,根结点没有双亲,所以要求 。
3)因为结点 的第 1 个子女编号为 ,若设该结点子女的序号为 ,则第 个子女结点的编号为 ()。
4)结点 不是其双亲的第 个子女时才有右兄弟。设其双亲编号为 ,可得 ,结点 的第 个子女的编号为 ,所以当结点的编号 时才有右兄弟,右兄弟的编号为 。或者,对于任意一个双亲结点 ,其第 个子女结点的编号是 ,故若不为第 个子女结点,则 (i-1)%m!=0。
转录核对:以上右兄弟条件针对非根结点,还应要求 ;根结点没有兄弟。孩子编号公式还需以该孩子实际存在为前提,叶结点没有孩子。
综合应用题 05
原书题目P135 · 解析P139 · 目视转录
已知一棵二叉树按顺序存储结构进行存储,设计一个算法,求编号分别为 和 的两个结点的最近的公共祖先结点的值。
查看答案与解析
首先,必须明确二叉树中任意两个结点必然存在最近的公共祖先结点,最坏的情况下是根结点(两个结点分别在根结点的左右分支中),而且从最近的公共祖先结点到根结点的全部祖先结点都是公共的。由二叉树顺序存储的性质可知,任意一个结点 的双亲结点的编号为 。求解 和 最近公共祖先结点的算法步骤如下(设从数组下标 1 开始存储):
1)若 ,则结点 所在层次大于或等于结点 所在层次。结点 的双亲结点为结点 ,若 ,则结点 是原结点 和结点 的最近公共祖先结点;若 ,则令 ,即以该结点 的双亲结点为起点,采用递归的方法继续查找。
2)若 ,则结点 所在层次大于或等于结点 所在层次。结点 的双亲结点为结点 ,若 ,则结点 是原结点 和结点 的最近公共祖先结点;若 ,则令 。
重复上述过程,直到找到它们最近的公共祖先结点为止。
ElemType Comm_Ancestor(SqTree T,int i,int j){
// 本算法在二叉树中查找结点i和结点j的最近公共祖先结点
if(T[i]!='#'&&T[j]!='#'){ // 结点存在
while(i!=j){ // 两个编号不同时循环
if(i>j)
i=i/2; // 向上找i的祖先
else
j=j/2; // 向上找j的祖先
}
return T[i];
}
}
由解题中算法的步骤描述可知,本题也很容易地联想到采用递归的方法求解。
综合应用题 06
原书题目P135 · 解析P140 · 目视转录
【2016 统考真题】若一棵非空 ()叉树 T 中的每个非叶结点都有 个孩子,则称 T 为正则 叉树。请回答下列问题并给出推导过程。
- 若 T 有 个非叶结点,则 T 中的叶结点有多少个?
- 若 T 的高度为 (单结点的树 ),则 T 的结点数最多为多少个?最少为多少个?
查看答案与解析
1)正则 叉树中仅含有两类结点:叶结点(个数记为 )和度为 的分支结点(个数记为 )。树 T 中的结点总数 。树中所含的边数 ,这些边均是从 个度为 的结点发出的,即 。整理得 ,所以 。
2)高度为 的正则 叉树中,含最多结点的树形为:除第 层外,第 1 到第 层的结点都是度为 的分支结点;而第 层均为叶结点,即树是“满”树。此时第 ()层的结点数为 ,结点总数 为
含最少结点的正则 叉树的树形为:第 1 层只有根结点;第 2 到第 层仅含 1 个分支结点和 个叶结点,第 层有 个叶结点。也就是说,除根外,第 2 到第 层中每层的结点数均为 ,所以 T 中所含结点总数 为