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. 含有 nn 个结点的二叉树的高度为 ⌊log⁡2n⌋+1\lfloor\log_2 n\rfloor+1

C. 在完全二叉树中,若一个结点没有左孩子,则它必定是叶结点

D. 含有 nn 个结点的完全二叉树的高度为 ⌈log⁡2n⌉\lceil\log_2 n\rceil

查看答案与解析

答案:C。

在二叉树中,若某个结点只有一个孩子,则这个孩子的左右次序是确定的;而在度为 2 的有序树中,若某个结点只有一个孩子,则这个孩子就无须区分其左右次序,选项 A 错误。选项 B 仅当是完全二叉树时才有意义,对于任意一棵二叉树,高度可能为 ⌊log⁡2n⌋+1∼n\lfloor\log_2 n\rfloor+1\sim n。在完全二叉树中,若有度为 1 的结点,则只可能有一个,且该结点只有左孩子而无右孩子,选项 C 正确。完全二叉树的高度为 ⌈log⁡2(n+1)⌉\lceil\log_2(n+1)\rceil 或 ⌊log⁡2n⌋+1\lfloor\log_2 n\rfloor+1,也可通过举例 n=4n=4 来排除,选项 D 错误。

单项选择题 02

原书题目P133 · 解析P136 · 目视转录

“二叉树为空”意味着二叉树( )。

A. 根结点没有子树

B. 不存在

C. 没有结点

D. 由一些没有赋值的空结点构成

查看答案与解析

答案:C。

“二叉树为空”,意味着二叉树中没有结点,但并不意味着二叉树不存在。注意,线性表可以是空表,树可以是空树,但图不能是空图(图中不能没有结点)。

单项选择题 03

原书题目P133 · 解析P136 · 目视转录

下列关于完全二叉树的说法中,正确的是( )。

A. 在完全二叉树中,叶结点的双亲的左兄弟(若存在)一定不是叶结点

B. 任何一棵二叉树中,叶结点数为度为 2 的结点数减 1,即 n0=n2−1n_0=n_2-1

C. 完全二叉树不适合顺序存储结构,只有满二叉树适合顺序存储结构

D. 结点按完全二叉树层序编号的二叉树中,第 ii 个结点的左孩子的编号为 2i2i

查看答案与解析

答案:A。

在完全二叉树中,叶结点的双亲的左兄弟的孩子一定在其前面(且一定存在),所以双亲的左兄弟(若存在)一定不是叶结点,选项 A 正确。n0n_0 应等于 n2+1n_2+1,选项 B 错误。完全二叉树和满二叉树均可以采用顺序存储结构,选项 C 错误。第 ii 个结点的左孩子不一定存在,选项 D 错误。

选项 B 的这种通用公式适用于所有二叉树,我们应能立即联想到采用特殊值代入法验证,如画一个只含 3 个结点的满二叉树的草图来验证是否满足条件。

单项选择题 04

原书题目P134 · 解析P136 · 目视转录

具有 10 个叶结点的二叉树中有( )个度为 2 的结点。

A. 8

B. 9

C. 10

D. 11

查看答案与解析

答案:B。

由二叉树的性质 n0=n2+1n_0=n_2+1,得 n2=n0−1=10−1=9n_2=n_0-1=10-1=9。

【另解】画出草图。首先画出 10 个叶结点,然后每 2 个结点向上合并,构造一个新的度为 2 的分支结点,直到构成二叉树,其中度为 2 的分支结点数为 9。

单项选择题 05

原书题目P134 · 解析P136 · 目视转录

设高度为 hh 的二叉树上只有度为 0 和度为 2 的结点,则此类二叉树中所包含的结点数至少为( )。

A. hh

B. 2h−12h-1

C. 2h+12h+1

D. h+1h+1

查看答案与解析

答案:B。

结点最少的情况:除根结点层只有 1 个结点外,其他 h−1h-1 层均有两个结点,结点总数 =2(h−1)+1=2h−1=2(h-1)+1=2h-1。

○
├─○(叶)
└─○
  ├─○(叶)
  └─○
    ⋮
    ├─○(叶)
    └─○(叶)

单项选择题 06

原书题目P134 · 解析P136 · 目视转录

具有 nn 个结点且高度为 nn 的二叉树的数目为( )。

A. log⁡2n\log_2 n

B. n/2n/2

C. nn

D. 2n−12^{n-1}

查看答案与解析

答案:D。

除根结点外,在其余 n−1n-1 个结点中,每个结点要么是其父结点的左孩子,要么是其父结点的右孩子,每个结点都有两种可能,n−1n-1 个结点共有 2n−12^{n-1} 种不同的组合形态。

单项选择题 07

原书题目P134 · 解析P136 · 目视转录

假设一棵二叉树的结点个数为 50,则它的最小高度是( )。

A. 4

B. 5

C. 6

D. 7

查看答案与解析

答案:C。

要求满足条件的树,分析可知当这 50 个结点构成一棵完全二叉树时高度最小,h=⌊log⁡2n⌋+1=⌊log⁡250⌋+1=6h=\lfloor\log_2 n\rfloor+1=\lfloor\log_2 50\rfloor+1=6。

【另解】第 1 层最多有 1 个结点,第 2 层最多有 212^1 个结点,第 3 层最多有 222^2 个结点,第 4 层最多有 232^3 个结点,以此类推,可以得到 hh 最小为 6。

单项选择题 08

原书题目P134 · 解析P137 · 目视转录

设二叉树有 2n2n 个结点,且 m<nm<n,则不可能存在( )的结点。

A. nn 个度为 0

B. 2m2m 个度为 0

C. 2m2m 个度为 1

D. 2m2m 个度为 2

查看答案与解析

答案:C。

由二叉树的性质 1 可知 n0=n2+1n_0=n_2+1,结点总数 2n=n0+n1+n2=n1+2n2+12n=n_0+n_1+n_2=n_1+2n_2+1,则 n1=2(n−n2)−1n_1=2(n-n_2)-1,所以 n1n_1 为奇数,说明该二叉树中不可能有 2m2m 个度为 1 的结点。

单项选择题 09

原书题目P134 · 解析P137 · 目视转录

一个具有 1025 个结点的二叉树的高 hh 为( )。

A. 11

B. 10

C. 11~1025

D. 10~1024

查看答案与解析

答案:C。

当二叉树为单支树时具有最大高度,即每层上只有一个结点,最大高度为 1025。而当树为完全二叉树时,其高度最小,最小高度为 ⌊log⁡2n⌋+1=11\lfloor\log_2 n\rfloor+1=11。

单项选择题 10

原书题目P134 · 解析P137 · 目视转录

设二叉树只有度为 0 和 2 的结点,其结点个数为 15,则该二叉树的最大深度为( )。

A. 4

B. 5

C. 8

D. 9

查看答案与解析

答案:C。

建议画图,第一层有 1 个结点,其余 h−1h-1 层各有 2 个结点,总结点数 1+2(h−1)=151+2(h-1)=15,h=8h=8。

单项选择题 11

原书题目P134 · 解析P137 · 目视转录

高度为 hh 的完全二叉树最少有( )个结点。

A. 2h2^h

B. 2h+12^h+1

C. 2h−12^{h-1}

D. 2h−12^h-1

查看答案与解析

答案:C。

高度为 hh 的完全二叉树中,第 1 层~第 h−1h-1 层构成一个高度为 h−1h-1 的满二叉树,结点个数为 2h−1−12^{h-1}-1。第 hh 层至少有一个结点,所以最少的结点个数 =(2h−1−1)+1=2h−1=(2^{h-1}-1)+1=2^{h-1}。

单项选择题 12

原书题目P134 · 解析P137 · 目视转录

已知一棵完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点,则该完全二叉树的结点个数最少是( )。

A. 39

B. 52

C. 111

D. 119

查看答案与解析

答案:A。

第 6 层有叶结点说明完全二叉树的高度可能为 6 或 7,显然树高为 6 时结点最少。若第 6 层上有 8 个叶结点,则前 5 层为满二叉树,所以完全二叉树的结点个数最少为 25−1+8=392^5-1+8=39 个结点。

单项选择题 13

原书题目P134 · 解析P137 · 目视转录

若一棵深度为 6 的完全二叉树的第 6 层有 3 个叶结点,则该二叉树共有( )个叶结点。

A. 17

B. 18

C. 19

D. 20

查看答案与解析

答案:A。

深度为 6 的完全二叉树,第 5 层共有 24=162^4=16 个结点。第 6 层最左边有 3 个叶结点,其对应的双亲结点为第 5 层最左边的两个结点,所以第 5 层剩余的结点均为叶结点,共有 16−2=1416-2=14 个,加上第 6 层的 3 个叶结点,共有 17 个叶结点。

单项选择题 14

原书题目P134 · 解析P137 · 目视转录

一棵完全二叉树上有 1001 个结点,其中叶结点的个数是( )。

A. 250

B. 500

C. 254

D. 501

查看答案与解析

答案:D。

由完全二叉树的性质,最后一个分支结点的序号为 ⌊1001/2⌋=500\lfloor1001/2\rfloor=500,所以叶结点个数为 501。

【另解】n=n0+n1+n2=n0+n1+(n0−1)=2n0+n1−1n=n_0+n_1+n_2=n_0+n_1+(n_0-1)=2n_0+n_1-1,因为 nn 为 1001,而在完全二叉树中,n1n_1 只能取 0 或 1。当 n1=1n_1=1 时,n0n_0 为小数,不符合题意。所以 n1=0n_1=0,于是有 n0=501n_0=501。

单项选择题 15

原书题目P134 · 解析P137 · 目视转录

若一棵二叉树有 126 个结点,在第 7 层(根结点在第 1 层)至多有( )个结点。

A. 32

B. 64

C. 63

D. 不存在第 7 层

查看答案与解析

答案:C。

要使二叉树第 7 层的结点数最多,只考虑树高为 7 层的情况,7 层满二叉树有 127 个结点,126 仅比 127 少 1 个结点,只能少在第 7 层,所以第 7 层最多有 26−1=632^6-1=63 个结点。

单项选择题 16

原书题目P134 · 解析P137 · 目视转录

一棵有 124 个叶结点的完全二叉树,最多有( )个结点。

A. 247

B. 248

C. 249

D. 250

查看答案与解析

答案:B。

在非空的二叉树当中,由度为 0 和 2 的结点数的关系 n0=n2+1n_0=n_2+1 可知 n2=123n_2=123;总结点数 n=n0+n1+n2=247+n1n=n_0+n_1+n_2=247+n_1,其最大值为 248(n1n_1 的取值为 1 或 0,当 n1=1n_1=1 时结点最多)。注意,由完全二叉树结点数的奇偶性可以确定 n1n_1 的值,但不能根据 n0n_0 来确定 n1n_1 的值。

【另解】124<27=128124<2^7=128,所以第 8 层没满,前 7 层为完全二叉树,由此可推算第 8 层可能有 120 个叶结点,第 7 层的最右 4 个为叶结点,考虑最多的情况,这 4 个叶结点中的最左边可以有 1 个左孩子(不改变叶结点数),因此结点总数 =27−1+120+1=248=2^7-1+120+1=248。

单项选择题 17

原书题目P134 · 解析P137 · 目视转录

某完全二叉树 T 中,结点个数最大的层有 8 个结点,则 T 中至多有( )个结点。

A. 8

B. 15

C. 23

D. 31

查看答案与解析

答案:C。

在完全二叉树中,第 4 层刚好最多有 8 个结点(前 4 层对应高度为 4 的满二叉树),若第 5 层也有 8 个结点,则对应于结点个数最多的情况,此时树高为 5,总结点数为 15+8=2315+8=23。

单项选择题 18

原书题目P134 · 解析P137 · 目视转录

一棵有 nn 个结点的二叉树采用二叉链存储结点,其中空指针数为( )。

A. nn

B. n+1n+1

C. n−1n-1

D. 2n2n

查看答案与解析

答案:B。

非空指针数=总分支数=n−1n-1,空指针数=2×2\times结点总数-非空指针数=2n−(n−1)=n+12n-(n-1)=n+1。

【另解】在树中,1 个指针对应 1 个分支,nn 个结点的树共有 n−1n-1 个分支,即 n−1n-1 个非空指针,每个结点都有 2 个指针域,所以空指针数 =2n−(n−1)=n+1=2n-(n-1)=n+1。

单项选择题 19

原书题目P134 · 解析P138 · 目视转录

设有 nn(n≥1n\ge1)个结点的二叉树采用三叉链表表示,其中每个结点包含三个指针,分别指向其左孩子、右孩子及双亲(若不存在,则置为空),则下列说法中正确的是( )。

Ⅰ. 树中空指针的数量为 n+2n+2

Ⅱ. 所有度为 2 的结点均被三个指针指向

Ⅲ. 每个叶结点均被一个指针所指向

A. Ⅰ

B. Ⅰ、Ⅱ

C. Ⅰ、Ⅲ

D. Ⅱ、Ⅲ

查看答案与解析

答案:A。

二叉链表表示的二叉树中空指针的数量为 n+1n+1,三叉链表表示的二叉树多了一个根结点指向双亲的空指针,所以树中空指针的数量为 n+2n+2,选项Ⅰ正确。若根结点的度为 2,则只有左、右两个孩子指向它,选项Ⅱ错误。若整棵树只有一个根结点,则没有指针指向它,选项Ⅲ错误。

单项选择题 20

原书题目P134 · 解析P138 · 目视转录

在一棵完全二叉树中,其根的序号为 1,( )可判定序号为 pp 和 qq 的两个结点是否在同一层。

A. ⌊log⁡2p⌋=⌊log⁡2q⌋\lfloor\log_2 p\rfloor=\lfloor\log_2 q\rfloor

B. log⁡2p=log⁡2q\log_2 p=\log_2 q

C. ⌊log⁡2p⌋+1=⌊log⁡2q⌋\lfloor\log_2 p\rfloor+1=\lfloor\log_2 q\rfloor

D. ⌊log⁡2p⌋=⌊log⁡2q⌋+1\lfloor\log_2 p\rfloor=\lfloor\log_2 q\rfloor+1

查看答案与解析

答案:A。

由完全二叉树的性质,编号为 ii(i≥1i\ge1)的结点所在的层次为 ⌊log⁡2i⌋+1\lfloor\log_2 i\rfloor+1,若两个结点位于同一层,则一定有 ⌊log⁡2p⌋+1=⌊log⁡2q⌋+1\lfloor\log_2 p\rfloor+1=\lfloor\log_2 q\rfloor+1,因此有 ⌊log⁡2p⌋=⌊log⁡2q⌋\lfloor\log_2 p\rfloor=\lfloor\log_2 q\rfloor 成立。

单项选择题 21

原书题目P134 · 解析P138 · 目视转录

在一个用数组表示的完全二叉树中,根结点的下标为 1,那么下标为 17 和 19 的结点的最近公共祖先的下标是( )。

A. 1

B. 2

C. 4

D. 8

查看答案与解析

答案:C。

当根结点下标为 1 时,下标为 ii 的结点的父结点下标为 ⌊i/2⌋\lfloor i/2\rfloor,那么下标为 17 的祖先的下标有 8、4、2、1,下标为 19 的祖先的下标有 9、4、2、1,因此两者最近的公共祖先的下标是 4。

单项选择题 22

原书题目P135 · 解析P138 · 目视转录

假定一棵三叉树的结点数为 50,则它的最小高度为( )。

A. 3

B. 4

C. 5

D. 6

查看答案与解析

答案:C。

分析可知,满足条件的三叉树可以是完全三叉树,这棵树的第 ii(i≥1i\ge1)层最多有 3i−13^{i-1} 个结点。设高度为 hh,则 30+31+⋯+3h−1=(3h−1)/23^0+3^1+\cdots+3^{h-1}=(3^h-1)/2 是结点数的上限,问题是求解 50≤(3h−1)/250\le(3^h-1)/2 的最小 hh 值,即 h≥log⁡3101h\ge\log_3 101,有 h=⌈log⁡3101⌉=5h=\lceil\log_3 101\rceil=5。

单项选择题 23

原书题目P135 · 解析P138 · 目视转录

具有 nn 个结点的三叉树用三叉链表表示,则树中空指针域的个数为( )。

A. 3n+13n+1

B. 2n+12n+1

C. 3n−13n-1

D. 3n3n

查看答案与解析

答案:B。

三叉树采用三叉链表表示,每个结点均有 3 个指针域指向 3 个孩子,共有 3n3n 个指针域,但 nn 个结点构成的一棵树只需要 n−1n-1 个指针(对于 n−1n-1 条边),因此空指针域有 2n+12n+1 个。

单项选择题 24

原书题目P135 · 解析P138 · 目视转录

对于一棵满二叉树,共有 nn 个分支结点和 mm 个叶结点,高度为 hh,则( )。

A. n=h+mn=h+m

B. n+m=2hn+m=2h

C. m=h−1m=h-1

D. n=2h−1n=2^h-1

查看答案与解析

原书答案:D。

对于高度为 hh 的满二叉树,结点总数 n=20+21+⋯+2h−1=2h−1n=2^0+2^1+\cdots+2^{h-1}=2^h-1,叶结点数 m=2h−1m=2^{h-1}。

转录核对:原题将 n 定义为“分支结点数”,解析却将 n 当作“结点总数”。若按题干定义,分支结点数应为 2h−1−12^{h-1}-1,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 层缺失 8×2=168\times2=16 个叶结点,所以完全二叉树的结点个数最多为 27−1−16=1112^7-1-16=111。

单项选择题 26

原书题目P135 · 解析P138 · 目视转录

【2011 统考真题】若一棵完全二叉树有 768 个结点,则该二叉树中叶结点的个数是( )。

A. 257

B. 258

C. 384

D. 385

查看答案与解析

答案:C。

最后一个分支结点的编号为 ⌊768/2⌋=384\lfloor768/2\rfloor=384,所以叶结点的个数为 768−384=384768-384=384。

【另解】n=n0+n1+n2=n0+n1+(n0−1)=2n0+n1−1n=n_0+n_1+n_2=n_0+n_1+(n_0-1)=2n_0+n_1-1,其中 n=768n=768,而在完全二叉树中,n1n_1 只能取 0 或 1,当 n1=0n_1=0 时,n0n_0 为小数,不符合题意。因此 n1=1n_1=1,所以 n0=384n_0=384。

单项选择题 27

原书题目P135 · 解析P138 · 目视转录

【2018 统考真题】设一棵非空完全二叉树 T 的所有叶结点均位于同一层,且每个非叶结点都有 2 个子结点。若 T 有 kk 个叶结点,则 T 的结点总数是( )。

A. 2k−12k-1

B. 2k2k

C. k2k^2

D. 2k−12^k-1

查看答案与解析

答案:A。

非叶结点的度均为 2,且所有叶结点都位于同一层的完全二叉树就是满二叉树。对于一棵高度为 hh 的满二叉树(空树 h=0h=0),其最后一层全部是叶结点,数目为 2h−12^{h-1};总结点数为 2h−12^h-1。因此当 2h−1=k2^{h-1}=k 时,可以得到 2h−1=2k−12^h-1=2k-1。

单项选择题 28

原书题目P135 · 解析P138 · 目视转录

【2020 统考真题】对于任意一棵高度为 5 且有 10 个结点的二叉树,若采用顺序存储结构保存,每个结点占 1 个存储单元(仅存放结点的数据信息),则存放该二叉树需要的存储单元数量至少是( )。

A. 31

B. 16

C. 15

D. 10

查看答案与解析

答案:A。

二叉树采用顺序存储时,用数组下标来表示结点之间的父子关系。对于一棵高度为 5 的二叉树,为了满足任意性,其 1~5 层的所有结点都要被存储起来,即考虑为一棵高度为 5 的满二叉树,共需要存储单元的数量为 1+2+4+8+16=311+2+4+8+16=31。

单项选择题 29

原书题目P135 · 解析P138 · 目视转录

【2022 统考真题】若三叉树 T 中有 244 个结点(叶结点的高度为 1),则 T 的高度至少是( )。

A. 8

B. 7

C. 6

D. 5

查看答案与解析

答案:C。

高度一定的三叉树中结点数最多的情况是满三叉树。高度为 5 的满三叉树的结点数 =30+31+32+33+34=121=3^0+3^1+3^2+3^3+3^4=121,高度为 6 的满三叉树的结点数 =30+31+32+33+34+35=364=3^0+3^1+3^2+3^3+3^4+3^5=364。三叉树 T 的结点数为 244,121<244<364121<244<364,因此 T 的高度至少为 6。

综合应用题

综合应用题 01

原书题目P135 · 解析P139 · 目视转录

在一棵完全二叉树中,含有 n0n_0 个叶结点,当度为 1 的结点数为 1 时,该树的高度是多少?当度为 1 的结点数为 0 时,该树的高度是多少?

查看答案与解析

在非空的二叉树中,由度为 0 和度为 2 的结点之间的关系 n0=n2+1n_0=n_2+1,可知 n2=n0−1n_2=n_0-1。因此总结点数 n=n0+n1+n2=2n0+n1−1n=n_0+n_1+n_2=2n_0+n_1-1。

① 当 n1=1n_1=1 时,n=2n0n=2n_0,h=⌈log⁡2(n+1)⌉=⌈log⁡2(2n0+1)⌉h=\lceil\log_2(n+1)\rceil=\lceil\log_2(2n_0+1)\rceil。

② 当 n1=0n_1=0 时,n=2n0−1n=2n_0-1,h=⌈log⁡2(n+1)⌉=⌈log⁡2(2n0)⌉=⌈log⁡2n0⌉+1h=\lceil\log_2(n+1)\rceil=\lceil\log_2(2n_0)\rceil=\lceil\log_2 n_0\rceil+1。

综合应用题 02

原书题目P135 · 解析P139 · 目视转录

一棵有 nn 个结点的满二叉树有多少个分支结点和多少个叶结点?该满二叉树的高度是多少?

查看答案与解析

满二叉树中 n1=0n_1=0,由二叉树的性质 1 可知 n0=n2+1n_0=n_2+1,即 n2=n0−1n_2=n_0-1,n=n0+n1+n2=2n0−1n=n_0+n_1+n_2=2n_0-1,则 n0=(n+1)/2n_0=(n+1)/2。分支结点个数 n2=n−(n+1)/2=(n−1)/2n_2=n-(n+1)/2=(n-1)/2。

高度为 hh 的满二叉树的结点数 n=1+21+22+⋯+2h−1=2h−1n=1+2^1+2^2+\cdots+2^{h-1}=2^h-1,即高度 h=log⁡2(n+1)h=\log_2(n+1)。

综合应用题 03

原书题目P135 · 解析P139 · 目视转录

已知完全二叉树的第 9 层有 240 个结点,则整个完全二叉树有多少个结点?有多少个叶结点?

查看答案与解析

在完全二叉树中,若第 9 层是满的,则结点数 =29−1=256=2^{9-1}=256,而现在第 9 层只有 240 个结点,说明第 9 层未满,是最后一层。1~8 层是满的,所以总结点数 =28−1+240=495=2^8-1+240=495。

因为第 9 层是最后一层,所以第 9 层的结点都是叶结点。且第 9 层的 240 个叶结点的双亲在第 8 层中,其双亲个数为 120,即第 8 层有 120 个分支结点,其余为叶结点,所以第 8 层的叶结点数为 28−1−120=82^{8-1}-120=8。因此,总的叶结点个数 =8+240=248=8+240=248。

【另解】总结点数 n=n0+n1+n2n=n_0+n_1+n_2,n2=n0−1n_2=n_0-1,n=n0+n1+n2=2n0+n1−1n=n_0+n_1+n_2=2n_0+n_1-1。若 n1=1n_1=1,则 2n0+n1−1=2n0=4952n_0+n_1-1=2n_0=495,不符合;若 n1=0n_1=0,则 2n0+n1−1=2n0−1=4952n_0+n_1-1=2n_0-1=495,则 n0=248n_0=248。

注意:对于本题,应理解完全二叉树中只有最底层的结点是不满的,其他各层的结点都是满的。

综合应用题 04

原书题目P135 · 解析P139 · 目视转录

一棵高度为 hh 的满 mm 叉树有如下性质:根结点所在层次为第 1 层,第 hh 层上的结点都是叶结点,其余各层上每个结点都有 mm 棵非空子树。若按层次自顶向下,同一层自左向右,顺序从 1 开始对全部结点进行编号,试问:

  1. 各层的结点个数是多少?
  2. 编号为 ii 的结点的双亲结点(若存在)的编号是多少?
  3. 编号为 ii 的结点的第 kk 个孩子结点(若存在)的编号是多少?
  4. 编号为 ii 的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少?
查看答案与解析

1)第 1 层有 m0=1m^0=1 个结点,第 2 层有 m1m^1 个结点,第 3 层有 m2m^2 个结点……一般地,第 ii 层有 mi−1m^{i-1} 个结点(1≤i≤h1\le i\le h)。

2)在 mm 叉树的情形下,结点 ii 的第 1 个子女编号为 j=(i−1)m+2j=(i-1)m+2,反过来,结点 ii 的双亲的编号是 ⌊(i−2)/m⌋+1\lfloor(i-2)/m\rfloor+1,根结点没有双亲,所以要求 i>1i>1。

3)因为结点 ii 的第 1 个子女编号为 j=(i−1)m+2j=(i-1)m+2,若设该结点子女的序号为 k=1,2,⋯ ,mk=1,2,\cdots,m,则第 kk 个子女结点的编号为 j=(i−1)m+k+1j=(i-1)m+k+1(1≤k≤m1\le k\le m)。

4)结点 ii 不是其双亲的第 mm 个子女时才有右兄弟。设其双亲编号为 jj,可得 j=⌊(i+m−2)/m⌋j=\lfloor(i+m-2)/m\rfloor,结点 jj 的第 mm 个子女的编号为 (j−1)m+m+1=jm+1=⌊(i+m−2)/m⌋m+1(j-1)m+m+1=jm+1=\lfloor(i+m-2)/m\rfloor m+1,所以当结点的编号 i<⌊(i+m−2)/m⌋m+1i<\lfloor(i+m-2)/m\rfloor m+1 时才有右兄弟,右兄弟的编号为 i+1i+1。或者,对于任意一个双亲结点 jj,其第 mm 个子女结点的编号是 jm+1jm+1,故若不为第 mm 个子女结点,则 (i-1)%m!=0。

转录核对:以上右兄弟条件针对非根结点,还应要求 i>1i>1;根结点没有兄弟。孩子编号公式还需以该孩子实际存在为前提,叶结点没有孩子。

综合应用题 05

原书题目P135 · 解析P139 · 目视转录

已知一棵二叉树按顺序存储结构进行存储,设计一个算法,求编号分别为 ii 和 jj 的两个结点的最近的公共祖先结点的值。

查看答案与解析

首先,必须明确二叉树中任意两个结点必然存在最近的公共祖先结点,最坏的情况下是根结点(两个结点分别在根结点的左右分支中),而且从最近的公共祖先结点到根结点的全部祖先结点都是公共的。由二叉树顺序存储的性质可知,任意一个结点 ii 的双亲结点的编号为 ⌊i/2⌋\lfloor i/2\rfloor。求解 ii 和 jj 最近公共祖先结点的算法步骤如下(设从数组下标 1 开始存储):

1)若 i>ji>j,则结点 ii 所在层次大于或等于结点 jj 所在层次。结点 ii 的双亲结点为结点 ⌊i/2⌋\lfloor i/2\rfloor,若 ⌊i/2⌋=j\lfloor i/2\rfloor=j,则结点 ⌊i/2⌋\lfloor i/2\rfloor 是原结点 ii 和结点 jj 的最近公共祖先结点;若 ⌊i/2⌋≠j\lfloor i/2\rfloor\ne j,则令 i=⌊i/2⌋i=\lfloor i/2\rfloor,即以该结点 ii 的双亲结点为起点,采用递归的方法继续查找。

2)若 j>ij>i,则结点 jj 所在层次大于或等于结点 ii 所在层次。结点 jj 的双亲结点为结点 ⌊j/2⌋\lfloor j/2\rfloor,若 ⌊j/2⌋=i\lfloor j/2\rfloor=i,则结点 ⌊j/2⌋\lfloor j/2\rfloor 是原结点 ii 和结点 jj 的最近公共祖先结点;若 ⌊j/2⌋≠i\lfloor j/2\rfloor\ne i,则令 j=⌊j/2⌋j=\lfloor j/2\rfloor。

重复上述过程,直到找到它们最近的公共祖先结点为止。

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 统考真题】若一棵非空 kk(k≥2k\ge2)叉树 T 中的每个非叶结点都有 kk 个孩子,则称 T 为正则 kk 叉树。请回答下列问题并给出推导过程。

  1. 若 T 有 mm 个非叶结点,则 T 中的叶结点有多少个?
  2. 若 T 的高度为 hh(单结点的树 h=1h=1),则 T 的结点数最多为多少个?最少为多少个?
查看答案与解析

1)正则 kk 叉树中仅含有两类结点:叶结点(个数记为 n0n_0)和度为 kk 的分支结点(个数记为 nkn_k)。树 T 中的结点总数 n=n0+nk=n0+mn=n_0+n_k=n_0+m。树中所含的边数 e=n−1e=n-1,这些边均是从 mm 个度为 kk 的结点发出的,即 e=mke=mk。整理得 n0+m=mk+1n_0+m=mk+1,所以 n0=(k−1)m+1n_0=(k-1)m+1。

2)高度为 hh 的正则 kk 叉树中,含最多结点的树形为:除第 hh 层外,第 1 到第 h−1h-1 层的结点都是度为 kk 的分支结点;而第 hh 层均为叶结点,即树是“满”树。此时第 ii(1≤i≤h1\le i\le h)层的结点数为 ki−1k^{i-1},结点总数 M1M_1 为

M1=∑i=1hki−1=kh−1k−1.M_1=\sum_{i=1}^{h}k^{i-1}=\frac{k^h-1}{k-1}.

含最少结点的正则 kk 叉树的树形为:第 1 层只有根结点;第 2 到第 h−1h-1 层仅含 1 个分支结点和 k−1k-1 个叶结点,第 hh 层有 kk 个叶结点。也就是说,除根外,第 2 到第 hh 层中每层的结点数均为 kk,所以 T 中所含结点总数 M2M_2 为

M2=1+(h−1)k.M_2=1+(h-1)k.