3. 二叉树的性质
## 3. 二叉树的性质
**考点击注** 二叉树中结点数的关系（2025）
1）非空二叉树的叶结点数等于度为2的结点数加1，即 $n_0 = n_2 + 1$。
<!-- page: 143 -->
第5章 树与二叉树
131
设度为 $0, 1$ 和 $2$ 的结点数分别为 $n_0, n_1$ 和 $n_2$，结点总数 $n = n_0 + n_1 + n_2$。
再考虑二叉树中的分支数，除根结点外，其余结点都有一个分支进入，设 $B$ 为分支总数，则 $n = B + 1$。这些分支是由度为1或2的结点射出的，因此有 $B = n_{1} + 2n_{2}$。
由此得出 $n_0 + n_1 + n_2 = n_1 + 2n_2 + 1$，从而得出 $n_0 = n_2 + 1$。
## 注意
该性质在选择题中经常出现，希望读者牢记并灵活应用。
2）非空二叉树的第 $k$ 层最多有 $2^{k-1}$ 个结点（$k \geqslant 1$）。
例如，第1层最多有 $2^{1-1} = 1$ 个结点（根），第2层最多有 $2^{2-1} = 2$ 个结点，以此类推，这构成一个首项为1、公比为2的等比数列，通项为 $2^{k-1}$。
3）高度为 $h$ 的二叉树至多有 $2^{h} - 1$ 个结点（$h \geqslant 1$）。
该性质可通过性质2求前 $h$ 项的和得到，即等比数列求和的结果。
## 注意
性质2和3可拓展到 $m$ 叉树的情况，即 $m$ 叉树的第 $k$ 层最多有 $m^{k-1}$ 个结点，高度为 $h$ 的 $m$ 叉树至多有 $(m^h - 1)/(m - 1)$ 个结点。
4）对完全二叉树按从上到下、从左到右的顺序依次编号 $1,2,\dots ,n$，则有以下关系：
① 最后一个分支结点的编号为 $[n/2]$，若 $i \leqslant [n/2]$，则结点 $i$ 为分支结点，否则为叶结点。
② 叶结点只可能出现在最后两层上（相当于在相同高度的满二叉树的最底层、最右侧减少一些连续叶结点；当减少两个及以上叶结点时，次底层将出现叶结点）。
③ 若存在度为 1 的结点，则最多只可能有一个，且该结点只有左孩子而无右孩子（度为 1 的分支结点只可能是最后一个分支结点，其结点编号为 $[n/2]$）。
④ 按层序编号后，一旦某个结点 $i$ 为叶结点或仅有左孩子，则所有编号大于 $i$ 的结点均为叶结点（与上述结论①和结论③一致）。
⑤ 若 $n$ 为奇数，则每个分支结点都有左右孩子；若 $n$ 为偶数，则编号最大的分支结点（编号为 $n/2$）只有左孩子，没有右孩子，其余分支结点都有左右孩子。
⑥ 当 $i > 1$ 时，结点 $i$ 的双亲结点的编号为 $[i/2]$。
⑦ 若结点 $i$ 有左右孩子，则左孩子编号为 $2i$，右孩子编号为 $2i + 1$。
⑧ 结点 $i$ 所在层次（深度）为 $\lfloor \log_2 i \rfloor + 1$。
5）具有 $n$ 个（$n > 0$）结点的完全二叉树的高度为 $\lceil \log_2(n + 1) \rceil$ 或 $\lfloor \log_2 n \rfloor + 1$。
设高度为 $h$，根据性质3和完全二叉树的定义有
$$
2^{h-1} - 1 < n \leqslant 2^{h} - 1 \quad \text{或者} \quad 2^{h-1} \leqslant n < 2^{h}
$$
得出 $2^{h-1} < n + 1 \leqslant 2^h$，即 $h - 1 < \log_2(n + 1) \leqslant h$，因为 $h$ 为正整数，所以 $h = \lceil \log_2(n + 1) \rceil$，或者得出 $h - 1 \leqslant \log_2 n < h$，所以 $h = \lfloor \log_2 n \rfloor + 1$。
## 5.2.2 二叉树的存储结构
### 1. 顺序存储结构
二叉树的顺序存储是指使用一组连续的存储单元，按照自上而下、自左至右的层序，依次存储完全二叉树中的结点元素。即将编号为 $i$ 的结点存储在一维数组下标为 $i-1$ 的位置中。
依据二叉树的性质，完全二叉树和满二叉树特别适合采用顺序存储，其结点编号能够唯一反
<!-- page: 144 -->
2027年数据结构考研复习指导
映结点之间的逻辑关系，既能最大限度地节省存储空间，又可直接通过数组下标快速确定结点在二叉树中的位置及其父子、兄弟关系。
考点包括
▶ 二叉树的顺序存储结构相关应用（2020、2025）
然而，对于一般的二叉树，若仍想通过数组下标反映逻辑结构，则需插入若干“空结点”，使其结构与同高度的完全二叉树一致，再将所有结点（包括空结点）按层序存入数组，这种做法在最坏情况下效率极低。例如，一个高度为 $h$ 且仅有 $h$ 个结点的单叉树，却需要占用近 $2^h - 1$ 个存储单元。图5.4展示了二叉树的顺序存储结构，其中用0表示空结点。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图5.4 二叉树的顺序存储结构
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 完全二叉树的顺序存储结构 (b) 一般二叉树的顺序存储结构 # 注意 建议从数组下标1开始存储树中结点，保证数组下标与结点编号一致。 ## 2. 链式存储结构 由于顺序存储的空间利用率较低，二叉树通常采用链式存储结构，即使用链表结点来存储二叉树中的每个结点。在二叉树的链式存储中，每个结点通常包括若干数据域和指针域。二叉链表至少包含3个域：左指针域lchild、数据域data和右指针域rchild，如图5.5所示。 | lchild | data | rchild | | --- | --- | --- | 图5.5 二叉树链式存储的结点结构 图5.6展示了一棵二叉树及其对应的二叉链表。在实际应用中，还可根据需要扩展结点结构，例如增加指向父结点的指针域，从而形成三叉链表的存储结构。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图5.6 二叉链表的存储结构
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图5.6 二叉链表的存储结构 二叉树的链式存储结构可定义如下： 不同的存储结构会导致二叉树操作算法的实现不同，因此应根据实际应用场景（如二叉树的 <!-- page: 145 --> 第5章 树与二叉树 133 形态特征及所需执行的运算类型）选择合适的存储方式。 容易验证，在含有 $n$ 个结点的二叉链表中，共有 $n + 1$ 个空链域（重要结论），常出现在选择题中。下一节将利用这些空链域构造一种新的链表结构——线索链表。 ## 5.2.3 本节试题精选 ### 一、单项选择题 01. 下列关于二叉树的说法中，正确的是（）。 A. 度为 2 的有序树就是二叉树 B. 含有 $n$ 个结点的二叉树的高度为 $\lfloor \log_2 n \rfloor + 1$ C. 在完全二叉树中，若一个结点没有左孩子，则它必是叶结点 D. 含有 $n$ 个结点的完全二叉树的高度为 $\lceil \log_2 n \rceil$ 02. “二叉树为空”意味着二叉树（）。 A. 根结点没有子树 B. 不存在 C. 没有结点 D. 由一些没有赋值的空结点构成 03. 下列关于完全二叉树的说法中，正确的是（）。 A. 在完全二叉树中，叶结点的双亲的左兄弟（若存在）一定不是叶结点 B. 任何一棵二叉树中，叶结点数为度为 2 的结点数减 1，即 $n_0 = n_2 - 1$ C. 完全二叉树不适合顺序存储结构，只有满二叉树适合顺序存储结构 D. 结点按完全二叉树层序编号的二叉树中，第 $i$ 个结点的左孩子的编号为 $2i$ 04. 具有 10 个叶结点的二叉树中有（ ）个度为 2 的结点。 A. 8 B. 9 C. 10 D. 11 05. 设高度为 $h$ 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为（）。 A. $h$ B. $2h - 1$ C. $2h + 1$ D. $h + 1$ 06. 具有 $n$ 个结点且高度为 $n$ 的二叉树的数目为（）。 A. $\log_2 n$ B. $n/2$ C. $n$ D. $2^{n-1}$ 07. 假设一棵二叉树的结点数为 50，则它的最小高度是（）。 A. 4 B. 5 C. 6 D. 7 08. 设二叉树有 $2n$ 个结点，且 $m < n$ ，则不可能存在（ ）的结点。 A. $n$ 个度为 0 B. $2m$ 个度为 0 C. $2m$ 个度为 1 D. $2m$ 个度为 2 09. 一个具有 1025 个结点的二叉树的高 $h$ 为（）。 A. 11 B. 10 C. $11 \sim 1025$ D. $10 \sim 1024$ 10. 设二叉树只有度为 0 和 2 的结点，其结点数为 15，则该二叉树的最大深度为（）。 A. 4 B. 5 C. 8 D. 9 11. 高度为 $h$ 的完全二叉树最少有（ ）个结点。 A. $2^h$ B. $2^h + 1$ C. $2^{h-1}$ D. $2^h - 1$ 12. 已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则完全二叉树的结点数最少是（）。 A. 39 B. 52 C. 111 D. 119 13. 若一棵深度为 6 的完全二叉树的第 6 层有 3 个叶结点，则该二叉树共有（ ）个叶结点。 A. 17 B. 18 C. 19 D. 20 <!-- page: 146 --> 2027年数据结构考研复习指导 14. 一棵完全二叉树上有 1001 个结点，其中叶结点的个数是（ ）。 A. 250 B. 500 C. 254 D. 501 15. 若一棵二叉树有 126 个结点，在第 7 层（根结点在第 1 层）至多有（ ）个结点。 A. 32 B. 64 C. 63 D. 不存在第 7 层 16. 一棵有 124 个叶结点的完全二叉树，最多有（ ）个结点。 A. 247 B. 248 C. 249 D. 250 17. 某完全二叉树 $T$ 中，结点数最大的层有 8 个结点，则 $T$ 中至多有（ ）个结点。 A. 8 B. 15 C. 23 D. 31 18. 一棵有 $n$ 个结点的二叉树采用二叉链存储结点，其中空指针数为（ ）。 A. $n$ B. $n + 1$ C. $n - 1$ D. $2n$ 19. 设有 $n (n \geqslant 1)$ 个结点的二叉树采用三叉链表表示，其中每个结点包含三个指针，分别指向其左孩子、右孩子及双亲（若不存在，则置为空），则下列说法中正确的是（ ）。 I. 树中空指针的数量为 $n + 2$ II. 所有度为 2 的结点均被三个指针指向 III. 每个叶结点均被一个指针所指向 A. I B. I, II C. I, III D. II, III 20. 在一棵完全二叉树中，其根的序号为 1，（ ）可判定序号为 $p$ 和 $q$ 的两个结点是否在同一层。 A. $\lfloor \log_2 p \rfloor = \lfloor \log_2 q \rfloor$ B. $\log_2 p = \log_2 q$ C. $\lfloor \log_2 p \rfloor + 1 = \lfloor \log_2 q \rfloor$ D. $\lfloor \log_2 p \rfloor = \lfloor \log_2 q \rfloor + 1$ 21. 在一个用数组表示的完全二叉树中，根结点的下标为 1，那么下标为 17 和 19 的结点的最近公共祖先的下标是（ ）。 A. 1 B. 2 C. 4 D. 8 22. 假定一棵三叉树的结点数为 50，则它的最小高度为（ ）。 A. 3 B. 4 C. 5 D. 6 23. 具有 $n$ 个结点的三叉树用三叉链表表示，则树中空指针域的个数为（ ）。 A. $3n + 1$ B. $2n + 1$ C. $3n - 1$ D. $3n$ 24. 对于一棵满二叉树，共有 $n$ 个结点和 $m$ 个叶结点，高度为 $h$，则（ ）。 A. $n = h + m$ B. $n + m = 2h$ C. $m = h - 1$ D. $n = 2^h - 1$ 25. 【2009 统考真题】已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则该完全二叉树的结点数最多是（ ）。 A. 39 B. 52 C. 111 D. 119 26. 【2011 统考真题】若一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是（ ）。 A. 257 B. 258 C. 384 D. 385 27. 【2018 统考真题】设一棵非空完全二叉树 $T$ 的所有叶结点均位于同一层，且每个非叶结点都有 2 个子结点。若 $T$ 有 $k$ 个叶结点，则 $T$ 的结点总数是（ ）。 A. $2k - 1$ B. $2k$ C. $k^2$ D. $2^k - 1$ 28. 【2020 统考真题】对于任意一棵高度为 5 且有 10 个结点的二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是（ ）。 A. 31 B. 16 C. 15 D. 10 29. 【2022 统考真题】若三叉树 $T$ 中有 244 个结点（叶结点的高度为 1），则 $T$ 的高度至少是（ ）。 <!-- page: 147 --> 第5章 树与二叉树 135 A. 8 B. 7 C. 6 D. 5 30. 【2025统考真题】若二叉树的结点值均为正整数，采用顺序存储方式保存在数组 R 中，用 -1 表示结点不存在，则下列数组中，不能表示一棵二叉树的是（ ）。 A. R[ ] = {20, 15, 40, -1, -1, 35} B. R[ ] = {15, 40, 10, 18, 35, -1, -1} C. R[ ] = {15, 40, 10, -1, -1, -1, 12} D. R[ ] = {17, 20, 35, -1, 18, 45, -1, -1, 19, 27} ## 二、综合应用题 01. 在一棵完全二叉树中，含有 $n_0$ 个叶结点，当度为 1 的结点数为 1 时，该树的高度是多少？当度为 1 的结点数为 0 时，该树的高度是多少？ 02. 一棵有 $n$ 个结点的满二叉树有多少个分支结点和多少个叶结点？该满二叉树的高度是多少？ 03. 已知完全二叉树的第 9 层有 240 个结点，则整个完全二叉树有多少个结点？有多少个叶结点？ 04. 一棵高度为 $h$ 的满 $m$ 叉树有如下性质：根结点所在层次为第 1 层，第 $h$ 层上的结点都是叶结点，其余各层上每个结点都有 $m$ 棵非空子树，若按层次自顶向下，同一层自左向右，顺序从 1 开始对全部结点进行编号，试问： 1）各层的结点数是多少？ 2）编号为 $i$ 的结点的双亲结点（若存在）的编号是多少？ 3）编号为 $i$ 的结点的第 $k$ 个孩子结点（若存在）的编号是多少？ 4）编号为 $i$ 的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？ 05. 已知一棵二叉树按顺序存储结构进行存储，设计一个算法，求编号分别为 $i$ 和 $j$ 的两个结点的最近的公共祖先结点的值。 06. 【2016统考真题】若一棵非空 $k$（$k \geqslant 2$）叉树 $T$ 中的每个非叶结点都有 $k$ 个孩子，则称 $T$ 为正则 $k$ 叉树。请回答下列问题并给出推导过程。 1）若 $T$ 有 $m$ 个非叶结点，则 $T$ 中的叶结点有多少个？ 2）若 $T$ 的高度为 $h$（单结点的树 $h = 1$），则 $T$ 的结点数最多为多少个？最少为多少个？ ## 5.2.4 答案与解析 ### 一、单项选择题 #### 01. C 在二叉树中，若某个结点只有一个孩子，则这个孩子的左右次序是确定的；而在度为 2 的有序树中，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，选项 A 错误。选项 B 仅当是完全二叉树时才有意义，对于任意一棵二叉树，高度可能为 $\lfloor \log_2 n \rfloor + 1 \sim n$。在完全二叉树中，若有度为 1 的结点，则只可能有一个，且该结点只有左孩子而无右孩子，选项 C 正确。完全二叉树的高度为 $\lceil \log_2 (n + 1) \rceil$ 或 $\lfloor \log_2 n \rfloor + 1$，也可通过举例 $n = 4$ 来排除，选项 D 错误。 #### 02. C “二叉树为空”意味着二叉树中没有结点，但并不意味着二叉树不存在。注意，线性表可以是空表，树可以是空树，但图不能是空图（图中不能没有结点）。 #### 03. A 在完全二叉树中，叶结点的双亲的左兄弟的孩子一定在其前面（且一定存在），所以双亲的左兄弟（若存在）一定不是叶结点，选项 A 正确。$n_0$ 应等于 $n_2 + 1$，选项 B 错误。完全二叉树和满二叉树均可以采用顺序存储结构，选项 C 错误。第 $i$ 个结点的左孩子不一定存在，选项 D 错误。 <!-- page: 148 --> 2027年数据结构考研复习指导 选项B的这种通用公式适用于所有二叉树，我们应能立即联想到采用特殊值代入法验证，如画一个只含3个结点的满二叉树的草图来验证是否满足条件。 04. B 由二叉树的性质 $n_0 = n_2 + 1$，得 $n_2 = n_0 - 1 = 10 - 1 = 9$。 【另解】画出草图，如下图所示。首先画出10个叶结点，然后每2个结点向上合并，构造一个新的度为2的分支结点，直到构成如下图所示的二叉树，其中度为2的分支结点数为9。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
05. B 结点最少的情况如下图所示。除根结点层只有1个结点外，其他 $h - 1$ 层均有两个结点，结点总数 $= 2(h - 1) + 1 = 2h - 1$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
06. D
除根结点外，在其余 $n - 1$ 个结点中，每个结点要么是其父结点的左孩子，要么是其父结点的右孩子，每个结点都有两种可能，$n - 1$ 个结点共有 $2^{n - 1}$ 种不同的组合形态。
07. C
要求满足条件的树，分析可知当这50个结点构成一棵完全二叉树时高度最小，$h = \lfloor \log_2n\rfloor +1 = \lfloor \log_250\rfloor +1 = 6$。
【另解】第1层最多有1个结点，第2层最多有 $2^{1}$ 个结点，第3层最多有 $2^{2}$ 个结点，第4层最多有 $2^{3}$ 个结点，以此类推，可以得到 $h$ 最少为6。
08. C
由二叉树的性质1可知 $n_0 = n_2 + 1$，结点总数 $= 2n = n_0 + n_1 + n_2 = n_1 + 2n_2 + 1$，则 $n_1 = 2(n - n_2) - 1$，所以 $n_1$ 为奇数，说明该二叉树中不可能有 $2m$ 个度为1的结点。
09. C
当二叉树为单支树时具有最大高度，即每层上只有一个结点，最大高度为1025。而当树为完全二叉树时，其高度最小，最小高度为 $\lfloor \log_2n\rfloor +1 = 11$。
10. C
建议画图，第一层有1个结点，其余 $h - 1$ 层各有2个结点，总结点数 $= 1 + 2(h - 1) = 15$，$h = 8$。
11. C
高度为 $h$ 的完全二叉树中，第1层～第 $h - 1$ 层构成一个高度为 $h - 1$ 的满二叉树，结点数为 $2^{h - 1} - 1$。第 $h$ 层至少有一个结点，所以最少的结点数 $= (2^{h - 1} - 1) + 1 = 2^{h - 1}$。
<!-- page: 149 -->
第5章 树与二叉树
137
12. A
第6层有叶结点说明完全二叉树的高度可能为6或7，显然树高为6时结点最少。若第6层上有8个叶结点，则前5层为满二叉树，所以完全二叉树的结点数最少为 $2^{5} - 1 + 8 = 39$。
13. A
深度为6的完全二叉树，第5层共有 $2^{4} = 16$ 个结点。第6层最左边有3个叶结点，其对应的双亲结点为第5层最左边的两个结点，所以第5层剩余的结点均为叶结点，共有 $16 - 2 = 14$ 个，加上第6层的3个叶结点，共有17个叶结点。
14. D
由完全二叉树的性质，最后一个分支结点的序号为 $\lfloor 1001 / 2\rfloor = 500$ ，所以叶结点数为501。
【另解】 $n = n_{0} + n_{1} + n_{2} = n_{0} + n_{1} + (n_{0} - 1) = 2n_{0} + n_{1} - 1$ ，因为 $n = 1001$ ，而在完全二叉树中， $n_{1}$ 只能取0或1。当 $n_{1} = 1$ 时， $n_{0}$ 为小数，不符合题意。所以 $n_{1} = 0$ ，于是有 $n_{0} = 501$ 。
15. C
要使二叉树第7层的结点数最多，只考虑树高为7层的情况，7层满二叉树有127个结点，126仅比127少1个结点，只能少在第7层，所以第7层最多有 $2^{6} - 1 = 63$ 个结点。
16. B
在非空的二叉树当中，由度为0和2的结点数的关系 $n_0 = n_2 + 1$ 可知 $n_2 = 123$ ；总结点数 $n = n_0 + n_1 + n_2 = 247 + n_1$ ，其最大值为248（ $n_1$ 的取值为1或0，当 $n_1 = 1$ 时结点最多）。注意，由完全二叉树总结点数的奇偶性可以确定 $n_1$ 的值，但不能根据 $n_0$ 来确定 $n_1$ 的值。
【另解】 $124 < 2^{7} = 128$ ，所以第8层没满，前7层为完全二叉树，由此可推算第8层可能有120个叶结点，第7层的最右4个为叶结点，考虑最多的情况，这4个叶结点中的最左边可以有1个左孩子（不改变叶结点数），因此结点总数 $= 2^{7} - 1 + 120 + 1 = 248$ 。
17. C
在完全二叉树中，第4层刚好最多有8个结点（前4层对应高度为4的满二叉树），若第5层也有8个结点，则对应于结点数最多的情况，此时树高为5，总结点数为 $15 + 8 = 23$ 。
18. B
非空指针数 $= \text{总分支数} = n - 1$ ，空指针数 $= 2 \times$ 结点总数-非空指针数 $= 2n - (n - 1) = n + 1$ 。
【另解】在树中，1个指针对应1个分支， $n$ 个结点的树共有 $n - 1$ 个分支，即 $n - 1$ 个非空指针，每个结点都有2个指针域，所以空指针数 $= 2n - (n - 1) = n + 1$ 。
19. A
二叉链表表示的二叉树中空指针的数量为 $n + 1$ ，三叉链表表示的二叉树多了一个根结点指向双亲的空指针，所以树中空指针的数量为 $n + 2$ ，说法I正确。若根结点的度为2，则只有左右两个孩子指向它，说法II错误。若整棵树只有一个根结点，则没有指针指向它，说法III错误。
20. A
由完全二叉树的性质，编号为 $i$ （ $i \geqslant 1$ ）的结点所在的层次为 $\lfloor \log_2 i \rfloor + 1$ ，若两个结点位于同一层，则一定有 $\lfloor \log_2 p \rfloor + 1 = \lfloor \log_2 q \rfloor + 1$ ，因此有 $\lfloor \log_2 p \rfloor = \lfloor \log_2 q \rfloor$ 成立。
21. C
当根结点下标为1时，下标为 $i$ 的结点的父结点下标为 $\lfloor i / 2\rfloor$ ，那么下标为17的祖先的下标有8,4,2,1，下标为19的祖先的下标有9,4,2,1，因此两者最近的公共祖先的下标是4。
22. C
分析可知，满足条件的三叉树可以是完全三叉树，这棵树的第 $i$ （ $i \geqslant 1$ ）层最多有 $3^{i-1}$ 个结点。设高度为 $h$ ，则 $3^0 + 3^1 + \dots + 3^{h-1} = (3^h - 1)/2$ 是结点数的上限，问题是求解 $50 \leqslant (3^h - 1)/2$ 的最小 $h$ 值，即 $h \geqslant \log_3 101$ ，有 $h = \lceil \log_3 101 \rceil = 5$ 。
<!-- page: 150 -->
2027年数据结构考研复习指导
23. B
三叉树采用三叉链表表示，每个结点均有3个指针域指向3个孩子，共有 $3n$ 个指针域，但 $n$ 个结点构成的一棵树中只需要 $n - 1$ 个指针（对于 $n - 1$ 条边），因此空指针域有 $2n + 1$ 个。
24. D
对于高度为 $h$ 的满二叉树，结点总数 $n = 2^0 + 2^1 + \dots + 2^{h - 1} = 2^h - 1$，叶结点数 $m = 2^{h - 1}$。
25. C
第6层有叶结点，完全二叉树的高度可能为6或7，显然树高为7时结点最多。完全二叉树与满二叉树相比，只是在最下一层的右边缺少部分叶结点，而最后一层之上是个满二叉树，且只有最后两层上有叶结点。若第6层上有8个叶结点，则前6层为满二叉树，而第7层缺失 $8 \times 2 = 16$ 个叶结点，所以完全二叉树的结点数最多为 $2^7 - 1 - 16 = 111$。
26. C
最后一个分支结点的编号为 $\lfloor 768 / 2\rfloor = 384$，所以叶结点的个数为 $768 - 384 = 384$。
【另解】 $n = n_{0} + n_{1} + n_{2} = n_{0} + n_{1} + (n_{0} - 1) = 2n_{0} + n_{1} - 1$，其中 $n = 768$，而在完全二叉树中，$n_{1}$ 只能取0或1，当 $n_{1} = 0$ 时，$n_{0}$ 为小数，不符合题意。因此 $n_{1} = 1$，所以 $n_{0} = 384$。
27. A
非叶结点的度均为2，且所有叶结点都位于同一层的完全二叉树就是满二叉树。对于一棵高度为 $h$ 的满二叉树（空树 $h = 0$），其最后一层全部是叶结点，数目为 $2^{h - 1}$；总结点数为 $2^h - 1$。因此当 $2^{h - 1} = k$ 时，可以得到 $2^h - 1 = 2k - 1$。
28. A
二叉树采用顺序存储时，用数组下标来表示结点之间的父子关系。对于一棵高度为5的二叉树，为了满足任意性，其1～5层的所有结点都要被存储起来，即考虑为一棵高度为5的满二叉树，共需要存储单元的数量为 $1 + 2 + 4 + 8 + 16 = 31$。
29. C
高度一定的三叉树中结点数最多的情况是满三叉树。高度为5的满三叉树的结点数 $= 3^{0} + 3^{1} + 3^{2} + 3^{3} + 3^{4} = 121$，高度为6的满三叉树的结点数 $= 3^{0} + 3^{1} + 3^{2} + 3^{3} + 3^{4} + 3^{5} = 364$。三叉树 $T$ 的结点数为244， $121 < 244 < 364$，因此 $T$ 的高度至少为6。
30. D
在二叉树的顺序存储结构中，结点按完全二叉树的层次顺序存放：根在下标0，对于任意非根结点 $\mathrm{R}[i]$，其父结点为 $\mathrm{R}[(i - 1) / 2]$。若某结点为空，则其所有后代位置必须也为空，否则将出现“空结点拥有非空子结点”的情况，违反二叉树的定义。在选项A、B、C中，所有非-1的元素，其从根到该结点的祖先路径上均不含-1，符合顺序存储规则。在选项D中， $\mathrm{R}[8] = 19$ 是一个有效结点，其父结点应为 $\mathrm{R}[(8 - 1) / 2] = \mathrm{R}[3]$，但 $\mathrm{R}[3] = -1$，表示该结点不存在，因此无法构成合法的二叉树。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
二、综合应用题
01. 【解答】
在非空的二叉树中，由度为0和度为2的结点之间的关系 $n_0 = n_2 + 1$，可知 $n_2 = n_0 - 1$。因此总结点数 $n = n_{0} + n_{1} + n_{2} = 2n_{0} + n_{1} - 1$。
① 当 $n_1 = 1$ 时，$n = 2n_0$，$h = \lceil \log_2(n + 1) \rceil = \lceil \log_2(2n_0 + 1) \rceil$。
② 当 $n_1 = 0$ 时，$n = 2n_0 - 1$，$h = \lceil \log_2(n + 1) \rceil = \lceil \log_2(2n_0) \rceil = \lceil \log_2(n_0) \rceil + 1$。
02. 【解答】
满二叉树中 $n_1 = 0$，由二叉树的性质1可知 $n_0 = n_2 + 1$，即 $n_2 = n_0 - 1, n = n_0 + n_1 + n_2 = 2n_0 - 1$，
<!-- page: 151 -->
第5章 树与二叉树
139
则 $n_0 = (n + 1)/2$。分支结点数 $n_2 = n - (n + 1)/2 = (n - 1)/2$。高度为 $h$ 的满二叉树的结点数 $n = 1 + 2^1 + 2^2 + \dots + 2^{h-1} = 2^h - 1$，即高度 $h = \log_2(n + 1)$。