数组结构之二叉树

二叉树的性质及证明

1. 叶子结点数与度为2的结点数的关系

性质：在非空二叉树中，叶子结点的个数等于度为2的结点数加1，即 $ n_0 = n_2 + 1 $。
证明：
- 设二叉树中度为0（叶子结点）、度为1、度为2的结点数分别为 $ n_0 $、$ n_1 $、$ n_2 $。
- 根据二叉树结点总数的定义，总结点数 $ n $ 为： $ n = n_0 + n_1 + n_2 $
- 二叉树中的分支数 $ B $ 是度为1和度为2的结点引出的。因此，分支数可以表示为： $ B = n_1 + 2n_2 $
- 除根结点外，其余每个结点都有一个分支进入树中。因此，分支数还可以表示为： $ B = n - 1 $
- 结合上面两个等式得： $ n_1 + 2n_2 = n - 1 $
- 将 $ n $ 用 $ n_0 + n_1 + n_2 $ 替换，得： $ n_1 + 2n_2 = n_0 + n_1 + n_2 - 1 $
- 简化后得到： $ n_0 = n_2 + 1 $
- 结论：叶子结点的数目 $ n_0 $ 等于度为2的结点数 $ n_2 $ 加1。

2. 二叉树每层结点数及高度的性质

性质：非空二叉树中，第 $ k $ 层至多有 $ 2^{k-1} $ 个结点，且高度为 $ h $ 的二叉树至多有 $ 2^h - 1 $ 个结点。
推导：
- 第1层至多有 $ 2^{1-1} = 1 $ 个结点（根结点）。
- 第2层至多有 $ 2^{2-1} = 2 $ 个结点。
- 以此类推，第 $ k $ 层至多有 $ 2^{k-1} $ 个结点。
- 这种结构形成了一个公比为2的等比数列，总结点数至多为前 $ h $ 项的和： $ 1 + 2 + 4 + + 2^{h-1} = 2^h - 1 $
- 因此，二叉树的结点总数最多为 $ 2^h - 1 $。

3. 完全二叉树的性质

编号规律：
- 对完全二叉树的结点从上到下、从左到右依次编号为1, 2, ..., $ n $，有以下关系：
  1. 结点 $ i $ 的双亲结点编号为 $ i/2 $：
    - 若 $ i $ 为偶数，则双亲结点编号为 $ i/2 $，它是双亲的左孩子。
    - 若 $ i $ 为奇数，则双亲结点编号为 $ (i-1)/2 $，它是双亲的右孩子。
  2. 结点 $ i $ 的左孩子编号为 $ 2i $（当 $ 2i n $ 时），否则无左孩子。
  3. 结点 $ i $ 的右孩子编号为 $ 2i+1 $（当 $ 2i+1 n $ 时），否则无右孩子。
  4. 结点 $ i $ 所在层次（深度）为 $ _2 i + 1 $。
完全二叉树的高度：
- 具有 $ n $ 个结点的完全二叉树的高度为 $ _2 (n+1) $ 或 $ _2 n + 1 $。
- 推导：
  - 根据完全二叉树的性质，前 $ h-1 $ 层共有 $ 2^{h-1} - 1 $ 个结点，最后一层至多有 $ 2^{h-1} $ 个结点。因此，结点总数满足： $ 2^{h-1} - 1 < n ^h - 1 $
  - 解得： $ h - 1 < _2 (n+1) h $
  - 由此可知，完全二叉树的高度为 $ h = _2 (n+1) $。

总结

叶子结点数：非空二叉树中，叶子结点数 $ n_0 $ 等于度为2的结点数 $ n_2 $ 加1，即 $ n_0 = n_2 + 1 $。
二叉树的层数与结点数：第 $ k $ 层至多有 $ 2^{k-1} $ 个结点。高度为 $ h $ 的二叉树最多有 $ 2^h - 1 $ 个结点。
完全二叉树的性质：完全二叉树的结点编号及左右孩子的规律具有严格的数学关系，完全二叉树的高度为 $ _2 (n+1) $。

选择题

01.下列关于二叉树的说法中，正确的是()。

A. 度为2的有序树就是二叉树
B. 含有n个结点的二叉树的高度为 $\left\lceil \log_2 n \right\rceil + 1$
C. 在完全二叉树中，若一个结点没有左孩子，则它必是叶结点
D. 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同

答案：C
解释：

选项A错误：度为2的有序树与二叉树并不等同，二叉树要求每个节点最多只能有两个子节点，并区分左右次序。
选项B错误：该公式只适用于完全二叉树，不能推广到所有二叉树。
选项C正确：在完全二叉树中，若一个结点没有左孩子，它必为叶子结点。
选项D错误：在二叉排序树中，删除结点后再插入，可能会改变树的结构。

02.以下说法中，正确的是()。

A. 在完全二叉树中，叶子结点的双亲的左兄弟(若存在)一定不是叶子结点
B. 任何一棵二叉树，叶子结点个数为度为2的结点数减1，即 $n_0 = n_2 - 1$
C. 完全二叉树不适合顺序存储结构，只有满二叉树适合顺序存储结构
D. 结点按完全二叉树层序编号的二叉树中，第i个结点的左孩子的编号为 $2i$

答案：A
解释：

选项A正确：在完全二叉树中，叶子结点的双亲的左兄弟（若存在）一定不是叶子结点。
选项B错误：正确的公式是 $n_0 = n_2 + 1$。
选项C错误：完全二叉树和满二叉树都适合顺序存储结构。
选项D错误：并不是所有结点都一定有左孩子，需保证 $2i \leq n$。

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

A. 8
B. 9
C. 10
D. 11

答案：B
解释：
根据二叉树的性质 $n_0 = n_2 + 1$，有 $n_2 = n_0 - 1 = 10 - 1 = 9$。这意味着具有10个叶子结点的二叉树中，度为2的结点有9个。

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

A. $h$
B. $2h - 1$
C. $2h + 1$
D. $h + 1$

答案：B
解释：
当二叉树的高度为 $h$，且只包含度为0和度为2的结点时，此类二叉树的最少结点数是 $2h - 1$，这对应于一棵完全满的二叉树的结构。

05. 假设一棵完全二叉树的结点个数为 50，则它的最小高度是（）。

A. 4
B. 5
C. 6
D. 7

答案：C
解释：
根据完全二叉树的高度计算公式 $ h = _2 n + 1 $，其中 $ n = 50 $。计算得 $ h = _2 50 + 1 = 6 $。

06. 设二叉树有 2n 个结点，且 $ m < n $，则不可能存在（）的结点。

A. $ n $ 个度为 0
B. $ 2m $ 个度为 0
C. $ 2m $ 个度为 1
D. $ 2m $ 个度为 2

答案：C
解释：
由二叉树的性质可知，节点总数与度的关系 $ n_0 = n_2 + 1 $ 可得，结点总数 = $ n + 2n_2 + 1 $，因此 $ m = 2(n - n_2) - 1 $ 得出 $ n $ 为奇数，故不可能存在 $ 2m $ 个度为 1 的结点。

07. 一个具有 1025 个结点的二叉树的高度 $ h $ 为（）。

A. 11
B. 10
C. 11 ~ 1025
D. 10 ~ 1024

答案：C
解释：
当二叉树为单支树时，最大高度为 1025；而当树为完全二叉树时，其最小高度为 $ _2 1025 = 11 $。因此，$ h $ 的范围为 11 到 1025。

08. 设二叉树只有度为 0 和 2 的结点，其结点总数 15，则该二叉树的最大深度为（）。

A. 4
B. 5
C. 8
D. 9

答案：C
解释：
由性质可知，若有一个结点在第一层，其余 $ h-1 $ 层上各有两个结点，则结点总数为 $ 1 + 2(h - 1) = 15 $，解得 $ h = 8 $。

09. 高度为 $ h $ 的完全二叉树最少有（）个结点。

A. $ 2^h $
B. $ 2^{h} + 1 $
C. $ 2^{h+1} - 1 $
D. $ 2^{h-1} $

答案：D
解释：
在完全二叉树中，高度为 $ h $ 的二叉树，前 $ h-1 $ 层构成一个满二叉树，结点个数为 $ 2^{h-1} - 1 $。第 $ h $ 层至少有一个结点，因此最少结点个数为 $ (2^{h-1} - 1) + 1 = 2^{h-1}$。

10. 已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则完全二叉树的结点个数最少是（）。

A. 39
B. 52
C. 111
D. 119

答案：A
解释：
第 6 层有叶结点表明完全二叉树的高度可能为 6 或 7，若高度为 6 则前 5 层为满二叉树，结点个数为 $ 2^6 - 1 + 8 = 39 $。因此，结点个数最少为 39。

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

A. 17
B. 18
C. 19
D. 20

答案：A
解释：
在深度为6的完全二叉树中，第5层的最大叶子结点数为 $ 2^4 = 16 $。由于已有3个叶子结点，意味着第五层有两个节点被占用，因此答案为16-2+3=17，答案为A。

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

A. 250
B. 500
C. 254
D. 501

答案：D
解释：
对于完全二叉树，叶结点数为 $ n/2 $。在这个例子中，$ /2 = 501 $。因此，叶结点的个数为501。

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

A. 32
B. 64
C. 63
D. 不存在第 7 层

答案：C
解释：
若二叉树有126个结点，最大高度为7层的完全二叉树有 $ 2^7 - 1 = 127 $ 个结点。由于树的结点数仅比满二叉树少一个，因此第7层至多可以有 $ 63 $ 个结点。

14. 一棵有 124 个叶子结点的完全二叉树，最多有()个结点。

A. 247
B. 248
C. 249
D. 250

答案：B
解释：
在非空的二叉树当中，由度为0和2的结点数的关系$n=m+1$可知$n_2=123$;总结点数$n=n_0+n_1+n_2=247+n_1$，其最大值为248($n_1$的取值为1或0，当$n_1=1$时结点最多)。

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

A. n
B. n + 1
C. n - 1
D. 2n

答案：B
解释：
在二叉树中，若有 $ n $ 个结点，非空指针数为 $ n - 1 $（即每个结点都有一个父结点，根结点除外）。每个结点有两个指针域，因此空指针数为 $ 2n - (n - 1) = n + 1 $。

16. 在一棵完全二叉树中，其根的序号为1，( )可判定序号为p和q的两个结点是否在同一层。

A. $ _2 p - _2 q $
B. $ _2 p = _2 q $
C. $ _2 p + 1 = _2 q + 1 $
D. $ _2 p = _2 q + 1 $

答案：A
解释：
在完全二叉树中，结点的层数可以通过其序号 $ p $ 和 $ q $ 计算：若两个结点在同一层，则它们的层数相等，即 $ _2 p = _2 q $。

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

选项：
- A. 3
- B. 4
- C. 5
- D. 6

答案：C. 5

$ _3{101} $

因此：

$ h 。 $

因此$h=5$。

18. 已知一棵有 2011 个结点的树，其叶结点个数是 116，该树对应的二叉树中无右孩子的结点个数是( )。

选项：
- A. 115
- B. 116
- C. 1895
- D. 1896

答案：D. 1896
分析：
对于一棵树，其叶结点个数为 $L$，则该树的中间结点数 $I$ 可以通过以下公式计算： $ I = n - L = 2011 - 116 = 1895 $ 在相应的二叉树中，除了最后一个叶结点外，所有中间结点都可以有右孩子，而仅有 $L - 1$ 个叶结点能够有右孩子（即最后一个叶结点不一定有右孩子）。因此，无右孩子的结点数为： $ = I + 1 = 1895 + 1 = 1896 $ 所以答案是 D. 1896。

19. 对于一棵满二叉树，共有 $n$ 个结点和 $m$ 个叶结点，高度为 $h$，则( )。

选项：
- A. $n + m = 2h$
- B. $n = h + m$
- C. $m = h - 1$
- D. $n = 2^h - 1$

答案：D. $n = 2^h - 1$
分析：
在满二叉树中，高度为 $h$ 的树的结点总数 $n$ 可以由公式给出： $ n = 2^h - 1 $ 而且叶结点 $m$ 数量为 $m = 2^{h-1}$。由于 $n$ 和 $m$ 是根据高度 $h$ 计算得出的，因此选项 D 是正确的。

20. [2009 统考真题] 已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则该完全二叉树的结点个数最多是()。

选项：
- A. 111
- B. 52
- C. 111
- D. 119

答案：C. 111
分析：
在完全二叉树中，第6层的叶结点数为8，因此可以推测该树的高度可能为6或7。若高度为7，则前6层将是满二叉树。

前6层的结点数： $ n_{} = 2^6 - 1 = 63 $
第7层的结点数： 在完全二叉树中，如果第6层有8个叶结点，第7层最多可以有 $2^6 = 64$ 个结点，但如果第7层的结点数不满，已知有8个叶结点，推测第7层有 $64 - 16 = 48$ 个分支结点，所以总的结点数为： $ n_{} = n_{} + n_{} = 63 + 48 = 111 $

因此该完全二叉树的结点个数最多为 111，所以答案是 C. 111。

21. 完全二叉树的叶节点个数

问题： 若一棵完全二叉树有 768 个节点，则该二叉树中叶节点的个数是( )

选项：
- A. 257
- B. 258
- C. 384
- D. 385

答案： C. 384

解释： 在完全二叉树中，叶节点的个数与内部节点的个数之间存在关系。对于 $ n $ 个节点的完全二叉树，叶节点的个数 $ L $ 可以通过以下公式得出：

计算内部节点的个数： $ I = = = 384 $
计算叶节点的个数： $ L = n - I = 768 - 384 = 384 $

因此，叶节点的个数是 384。

22. 非空完全二叉树的节点总数

问题： 设一棵非空完全二叉树 $ T $ 的所有叶节点均位于同一层，且每个非叶节点都有 2 个子节点。若 $ T $ 有 $ k $ 个叶节点，则 $ T $ 的节点总数是( )

选项：
- A. $ 2k - 1 $
- B. $ 2k $
- C. $ R $
- D. $ 2k - 1 $

答案： A. $ 2k - 1 $

解释： 在完全二叉树中，假设有 $ k $ 个叶节点，树的结构如下：

每个非叶节点都有 2 个子节点，所以对于 $ k $ 个叶节点，所有的非叶节点数 $ I $ 可以通过以下关系计算： $ I = k - 1 $ （因为每增加一个叶节点，至少需要一个新的非叶节点）
总节点数： $ n = I + k = (k - 1) + k = 2k - 1 $

因此，节点总数是 $ 2k - 1 $。

23. 高度为 5 且有 10 个节点的二叉树存储单元需求

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

选项：
- A. 31
- B. 16
- C. 15
- D. 10

答案： A. 31

解释： 在顺序存储的情况下，完全二叉树的高度为 $ h $ 的情况下，所有层的节点都需要存储。对于高度为 5 的满二叉树，其节点数量为：

$ n = 1 + 2 + 4 + 8 + 16 = 31 $

即便实际有 10 个节点，仍需要为满二叉树的结构保留 31 个存储单元以保持树的结构。因此，至少需要 31 个存储单元。

解答题

问题01

在一棵完全二叉树中，含有 $ m $ 个叶节点，当度为 1 的节点数为 1 时，该树的高度是多少？当度为 1 的节点数为 0 时，该树的高度又是多少？

问题描述

在非空的二叉树中，由度为 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 = n_0 + n_1 + n_2 = 2n_0 + n_1 - 1 $
高度的计算：
- 在特定情况下，给出了以下计算：
  - 当 $ n_1 = 1 $ 时：
    - 计算得到 $ n_2 = 2n_0 $：$ h = _2(n + 1) = _2(2n_0 + 1) $
  - 当 $ n_1 = 0 $ 时：
    - 计算得到 $ n = 2n_0 - 1 $：$ h = _2(n + 1) = _2(2n_0) = _2(n_0) + 1 $

当度为 1 的节点数 $ n_1 = 1 $ 时，高度为 $ h = _2(2n_0 + 1) $。
当度为 1 的节点数 $ n_1 = 0 $ 时，高度为 $ h = _2(n_0) + 1 $。

问题02:

一棵有 $ n $ 个结点的满二叉树有多少个分支结点和多少个叶子结点？该满二叉树的高度是多少？

解答

满二叉树的性质：
- 在一棵满二叉树中，每个分支结点都有两个子结点，因此其节点数 $ n $ 可以表示为： $ n = n_0 + n_1 $ 其中 $ n_0 $ 是叶子结点的个数，$ n_1 $ 是分支结点的个数。
- 对于满二叉树，有以下关系： $ n_0 = n_1 + 1 $
- 从以上两个公式可以推导出： $ n = n_1 + (n_1 + 1) = 2n_1 + 1 $
- 由此可得分支结点的个数 $ n_1 $：$ n_1 = $
- 叶子结点的个数 $ n_0 $ 则为： $ n_0 = n_1 + 1 = + 1 = $
高度的计算：
- 满二叉树的高度 $ h $ 和结点数 $ n $ 的关系为： $ n = 2^h - 1 $
- 因此，可以得到高度 $ h $：$ h = _2(n + 1) $

结论

分支结点的个数： $ n_1 = $
叶子结点的个数： $ n_0 = $
高度： $ h = _2(n + 1) $

问题03

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

解答

完全二叉树的基本特性：
- 在完全二叉树中，每一层都是满的，除了最后一层可能不满。
- 对于第 $ k $ 层，最大结点数为 $ 2^{k-1} $。因此第9层的最大结点数为 $ 2^{8} = 256 $。
结点数量的计算：
- 已知第9层有240个结点，说明第9层未满，因此它是最后一层。
- 因此，整个树的结点数为： $ n = n_{8} -1+240 = 495 $
叶子结点的计算：

答案是$(495+1)/2=248$

问题04

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

各层的结点个数是多少？
编号为 $ i $ 的结点的双亲结点（若存在）的编号是多少？
编号为 $ i $ 的结点的第 $ k $ 个孩子结点（若存在）的编号是多少？
编号为 $ i $ 的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？

解答

各层的结点个数：
- 在满 $ m $ 叉树中，第 $ i $ 层的结点个数为 $ m^{(i-1)} $。
- 具体来说：
  - 第1层：$ m^{(1-1)} = m^{0} = 1 $ 个结点
  - 第2层：$ m^{(2-1)} = m^{1} = m $ 个结点
  - 第3层：$ m^{(3-1)} = m^{2} $ 个结点
  - ...
  - 第 $ h $ 层：$ m^{(h-1)} $ 个结点
编号为 $ i $ 的结点的双亲结点（若存在）：
- 对于编号为 $ i $ 的结点，其双亲的编号可以通过公式： $ = + 1 $
- 注意：根结点（编号为1）没有双亲，所以需要满足 $ i > 1 $。
编号为 $ i $ 的结点的第 $ k $ 个孩子结点（若存在）：
- 编号为 $ i $ 的结点的第 $ k $ 个孩子结点的编号为： $ k = (i - 1) m + k + 1 $
- 这里 $ k $ 的取值范围为 $ 1 k m $。
编号为 $ i $ 的结点有右兄弟的条件及右兄弟编号：
- 一个结点有右兄弟的条件是它不是双亲的最后一个孩子，即： $ (i - 1) m m - 1 $
- 右兄弟的编号为： $ = i + 1 $
- 换句话说，若结点 $ i $ 不是其双亲的第 $ m $ 个子女，则有右兄弟，且右兄弟的编号为 $ i + 1 $。

结论

各层的结点个数：第 $ i $ 层有 $ m^{(i-1)} $ 个结点。
编号为 $ i $ 的结点的双亲编号为 $ + 1 $（若 $ i > 1 $）。
编号为 $ i $ 的结点的第 $ k $ 个孩子编号为 $ (i - 1) m + k + 1 $（$ 1 k m $）。
编号为 $ i $ 的结点有右兄弟的条件为 $ (i - 1) m m - 1 $，其右兄弟编号为 $ i + 1 $。

问题05:

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

解答

最近公共祖先的定义：在一棵二叉树中，节点 $ x $ 是节点 $ a $ 和节点 $ b $ 的最近公共祖先，如果 $ x $ 是 $ a $ 和 $ b $ 的祖先，并且 $ x $ 的子节点不是 $ a $ 或 $ b $。

算法步骤

在顺序存储结构中，节点 $ i $ 的父节点的编号为 $ $，因此可以通过不断向上查找两个节点的父节点来找到它们的最近公共祖先。

初始化：开始时使用两个变量 $ i $ 和 $ j $，分别表示两个节点的编号。
循环查找：
- 如果 $ i $ 和 $ j $ 相等，说明已经找到了最近公共祖先，返回节点 $ i $ 的值。
- 如果 $ i $ 大于 $ j $，将 $ i $ 更新为其父节点的编号 $ $。
- 否则，将 $ j $ 更新为其父节点的编号 $ $。
重复上述过程，直到找到它们的最近公共祖先节点。

算法实现

以下是 C++ 风格的伪代码实现：

ElemType CommAncestor(SqTree T, int i, int j) {
    // 检查结点i和j是否存在
    if (i <= T.size() && T[i] != '#' && j <= T.size() && T[j] != '#') {
        // 循环直到i和j相等
        while (i != j) {
            if (i > j) {
                i = i / 2;  // 向上查找i的祖先
            } else {
                j = j / 2;  // 向上查找j的祖先
            }
        }
        // 返回最近公共祖先的值
        return T[i];  // i和j此时相等，返回其值
    }
    return -1; // 若不存在返回-1
}

详细解释

顺序存储结构：
- 在顺序存储结构中，通常以数组的形式存储二叉树。
- 对于节点 $ i $，其左子节点的编号为 $ 2i $，右子节点的编号为 $ 2i + 1 $，父节点的编号为 $ $（如果 $ i $ 为根节点，则没有父节点）。
算法的核心逻辑：
- 使用循环逐步向上移动，直到两个节点的编号相等。
- 这个方法非常高效，因为它的时间复杂度为 $ O(n) $，其中 $ n $ 是树中的节点数量。
递归的替代：
- 本题中的算法是非递归的，但可以使用递归方式实现相同的逻辑。递归方法需要考虑到如何管理递归调用栈和返回值。