数组结构之树的概念与性质

树的基本术语和概念

1. 祖先与子孙

祖先：在从根结点到某个结点的唯一路径上的任意结点称为该结点的祖先。例如，结点B是结点K的祖先。
子孙：相对地，结点K是结点B的子孙。
双亲：结点K的最接近的上一级结点称为K的双亲，K为该双亲的孩子。例如，结点E是K的双亲。
兄弟：具有相同双亲的结点称为兄弟。例如，结点K和结点L的双亲都是结点E，因此K和L互为兄弟。
根结点：根结点是树中唯一没有双亲的结点。在图5.1中，结点A是根结点。

2. 结点的度和树的度

结点的度：结点的度是其子结点的个数。例如，结点B的度为2，结点D的度为3。
树的度：树中结点的最大度数。例如，图5.1中树的最大度为3。

3. 分支结点与叶子结点

分支结点（非终端结点）：度大于0的结点称为分支结点。例如，结点B和结点D都是分支结点。
叶子结点（终端结点）：度为0的结点称为叶子结点。例如，结点K、L等没有子结点的结点都是叶子结点。

4. 结点的层次、深度与高度

层次：从根开始，根结点为第1层，它的子结点为第2层，以此类推。例如，结点A是第1层，结点B、C是第2层。
堂兄弟：同一层的结点如果它们的双亲不同，则互为堂兄弟。例如，结点G与E、F、H等互为堂兄弟。
结点的深度：从根结点开始，自上向下的路径上结点的层数。例如，根结点A的深度为1，结点K的深度为4。
结点的高度：从叶子结点开始，自下向上的路径长度。例如，叶子结点的高度为0，根结点的高度为最大。
树的高度：树中所有结点的最大层数。例如，图5.1中的树的高度为4。

5. 有序树与无序树

有序树：如果树中结点的子树从左到右有严格的次序（不能互换），则称为有序树。例如，在图5.1中，如果子结点互换位置，则会生成不同的树。
无序树：如果树中的子树次序可以互换，则称为无序树。

6. 路径与路径长度

路径：树中两个结点之间的路径是由从一个结点到另一个结点所经过的所有结点构成的序列。
路径长度：路径上所经过的边的个数。例如，从根结点A到结点K的路径长度为3。
路径方向：树中的路径是从双亲指向孩子的，有方向性，即路径从上向下。

7. 森林

森林：森林是由 $ m $ 棵互不相交的树组成的集合。如果将一棵树的根结点去除，剩下的子树集合就是森林。例如，删除图5.1中的根结点A，剩下的部分就是一个森林。相反，如果将 $ m $ 棵树用一个新的结点连接起来，那么森林就变成了一棵树。

树的性质

树结构有一些非常重要的性质，掌握这些性质有助于理解树的形态和应用。以下是树的几个基本性质：

1. 结点数与度数的关系

性质1：树中的结点数等于所有结点的度数之和再加1。
- 解释：假设一棵树有 $ n $ 个结点，每个结点都有某个度数（即子结点的个数）。每个边连接两个结点，其中一个是双亲，另一个是孩子。因此，边数等于所有结点的度数之和。树的结点数 $ n $ 与边数 $ e $ 的关系为 $ n = e + 1 $，即树中结点的度数之和加1等于总结点数。
- 例子：如果树中有4个度数分别为2、1、0、0的结点，度数之和为3，那么总结点数就是 $ 3 + 1 = 4 $。

2. m 叉树的层上结点数

性质2：度为 $ m $ 的树中，第 $ i $ 层上最多有 $ m^{i-1} $ 个结点（对于 $ i > 1 $）。
- 解释：在一棵 $ m $ 叉树中，每个结点最多有 $ m $ 个子结点。根结点（第1层）有1个，第二层最多有 $ m $ 个结点，第三层最多有 $ m^2 $ 个结点，依此类推。对于第 $ i $ 层，其结点数最多为 $ m^{i-1} $ 个。
- 例子：在一棵二叉树中，第2层最多有 $ 2^1 = 2 $ 个结点，第3层最多有 $ 2^2 = 4 $ 个结点。

3. 高度为 $ h $ 的 $ m $ 叉树的最大结点数

性质3：高度为 $ h $ 的 $ m $ 叉树最多有 $ $ 个结点。
- 解释：在一棵 $ m $ 叉树中，树的高度是 $ h $，即根结点到最远的叶子结点的路径长度。每一层的结点数随着高度指数增长，因此总结点数是从根到第 $ h $ 层所有结点数的和。
- 推导：根结点有1个，第二层最多有 $ m $ 个结点，第三层最多有 $ m^2 $ 个结点，依次类推到第 $ h $ 层。总结点数为： $ 1 + m + m^2 + + m^{h-1} = $
- 例子：对于一棵高度为3的二叉树（$ m = 2 $），其最多有 $ = 7 $ 个结点。

4. 具有 $ n $ 个结点的 $ m $ 叉树的最小高度

性质4：具有 $ n $ 个结点的 $ m $ 叉树的最小高度为： $ h_{} = _m{(n(m-1) + 1)} $
- 解释：最小高度是指在结点数已知的情况下，树的高度最小化。根据结点数和每层结点的增长速率，使用对数函数可以计算出最小的层数（高度）。
- 推导：我们知道第 $ h $ 层最多可以容纳的结点数为 $ $。将这个式子变形，可以得到最小高度的表达式。
- 例子：对于一棵具有9个结点的二叉树（$ m = 2 $），最小高度为：$ h_{} = _2{(9(2-1) + 1)} = _2{10} = 4 $

总结

结点数与度数的关系：树的结点数等于所有结点度数的和加1。
每层最大结点数：第 $ i $ 层的结点数最多为 $ m^{i-1} $ 个。
最大结点数：高度为 $ h $ 的 $ m $ 叉树最多有 $ $ 个结点。
最小高度：具有 $ n $ 个结点的 $ m $ 叉树的最小高度为 $ _m{(n(m-1) + 1)} $。

选择题

01. 树最适合用来表示( )的数据。

A. 有序
B. 无序
C. 任意元素之间具有多种联系
D. 元素之间具有分支层次关系

答案：D
解释：树结构特别适合表示具有分层结构或分支层次关系的数据，例如组织架构、文件系统等。在树中，每个结点都有一个或多个子结点，而这些子结点又可以有自己的子结点，从而形成分层结构。

02. 一棵有 $ n $ 个结点的树的所有结点的度数之和为( )。

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

答案：A
解释：在树中，所有结点的度数之和等于树的边数，而树的边数总是比结点数少1，因此，所有结点的度数之和为 $ n - 1 $（其中 $ n $ 为树的结点数）。

03. 树的路径长度是从树根到每个结点的路径长度的( )。

A. 总和
B. 最小值
C. 最大值
D. 平均值

答案：A
解释：树的路径长度是从根结点到树中所有其他结点的路径长度的总和。路径长度是树中一个非常重要的概念，尤其在计算树的效率（例如查找或插入操作）时使用。

04. 对于一棵具有 $ n $ 个结点、度为4的树来说，( )。

A. 树的高度至多是 $ n-3 $
B. 树的高度至多是 $ n-4 $
C. 第 $ i $ 层上至多有 $ 4^{i-1} $ 个结点
D. 至少在某一层上正好有 4 个结点

答案：A
解释：要使树的高度最大，需要使得每一层的结点数尽可能少。例如，对于度为4的树，可以设计为每层只有一个结点，最终使得高度为 $ n-3 $，这样可以达到树的最大高度。注意，树的度为4意味着某些结点最多有4个子结点。

05. 度为 4、高度为 $ h $ 的树( )。

A. 至少有 $ h+3 $ 个结点
B. 至多有 $ 4h-1 $ 个结点
C. 至多有 $ 4h $ 个结点
D. 至少有 $ h+4 $ 个结点

答案：A
解释：要使度为4、高度为 $ h $ 的树的结点数最少，需要尽量减少每一层的结点数。最少情况下，每层只有一个结点，且至少有一个结点有4个孩子。这种树结构类似“链式结构”，其结点数最少为 $ h+3 $。

06. 假定一棵度为3的树中，结点数为50，则其最小高度为( )

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

答案：C

解释：在度为3的完全三叉树中，每一层的结点数量是上一层结点数的3倍。树的最小高度意味着结点尽可能地集中在较少的层数中。我们可以通过层次计算来确定最小高度：

第1层有1个结点
第2层有 $3$ 个结点
第3层有 $3^2 = 9$ 个结点
第4层有 $3^3 = 27$ 个结点

此时，总结点数为 $1 + 3 + 9 + 27 = 40$。由于总结点数是50，剩余 $50 - 40 = 10$ 个结点应分布在第5层。因此，树的最小高度为 5。

07. 在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是( )

A. 41
B. 82
C. 113
D. 122

答案：B. 82

解释：根据树的性质，树中的结点数等于所有结点的度数之和加 1。我们可以通过计算非叶结点的总度数，并利用这个关系来确定叶结点的数量。

首先，已知每种结点的数量及其度数：
- 度为4的结点有20个，总度数为 $20 \times 4 = 80$
- 度为3的结点有10个，总度数为 $10 \times 3 = 30$
- 度为2的结点有1个，总度数为 $1 \times 2 = 2$
- 度为1的结点有10个，总度数为 $10 \times 1 = 10$
总的非叶结点的度数为 $80 + 30 + 2 + 10 = 122$。
根据树的性质，非叶结点的度数和等于叶结点数的和，再加上1（根节点）。
因此，叶结点数为： $ = 122 + 1 = 123 - $
非叶结点数 = $20 + 10 + 1 + 10 = 41$，因此叶结点数为： $ 123 - 41 = 82 $

因此，树T的叶结点个数是 82。

综合应用题

01. 含有 $ n $ 个结点的三叉树的最小高度是多少？

解答：

要求含有 $ n $ 个结点的三叉树的最小高度，最小高度对应的三叉树应该是一棵完全三叉树。接下来，我们推导完全三叉树的最小高度。

假设完全三叉树的高度为 $ h $，那么根据三叉树的特性：

第 $ h $ 层至少有 1 个结点，至多有 $ 3^{h-1} $ 个结点。
总结点数是每一层结点数的总和。

因此，树的总结点数满足以下不等式： $ 1 + 3 + 3^2 + + 3^{h-2} < n + 3 + 3^2 + + 3^{h-1} $

这个不等式可以写成： $ < n $

为了便于计算，我们可以简化该不等式为： $ 3^{h-1} < 2n + 1 ^h $

取对数后可以得到 $ h $ 的范围： $ h - 1 < _3 (2n + 1) h $

因此，最小的高度 $ h $ 为： $ h = _3 (2n + 1) $

答案：含有 $ n $ 个结点的三叉树的最小高度为 $ _3 (2n + 1) $。

解释：

对于完全三叉树，最小高度意味着每一层尽可能多的填满结点。
通过推导，我们得到了 $ h = _3 (2n + 1) $，这就是该三叉树的最小高度。

题目02.已知一棵度为 4 的树中，度为 0, 1, 2, 3 的结点数分别为 14, 4, 3, 2，求该树的结点总数 $ n $ 和度为 4 的结点个数 $ n_4 $。请给出推导过程。

解答

设结点总数为 $ n $，度为 $ i $ ($ i = 0, 1, 2, 3, 4 $) 的结点数分别为 $ n_0, n_1, n_2, n_3, n_4 $。
根据题目已知：
- 度为 0 的结点数 $ n_0 = 14 $
- 度为 1 的结点数 $ n_1 = 4 $
- 度为 2 的结点数 $ n_2 = 3 $
- 度为 3 的结点数 $ n_3 = 2 $
因此，结点总数可以表示为： $ n = n_0 + n_1 + n_2 + n_3 + n_4 $ 代入已知值： $ n = 14 + 4 + 3 + 2 + n_4 = 23 + n_4 $
树的度数性质：树中所有结点的度数之和加上 1 等于结点总数 $ n $。用数学表达式为：$ n = n_1 + 2n_2 + 3n_3 + 4n_4 + 1 $ 代入已知值： $ n = 4 + 2 + 3 + 4 n_4 + 1 = 4 + 6 + 6 + 4n_4 + 1 = 17 + 4n_4 $
将结点总数的两个表达式结合： $ 23 + n_4 = 17 + 4n_4 $
解方程： $ 23 - 17 = 4n_4 - n_4 $ $ 6 = 3n_4 $ $ n_4 = 2 $
代入 $ n_4 = 2 $ 到 $ n = 23 + n_4 $ 中，得： $ n = 23 + 2 = 25 $

答案

该树的结点总数 $ n = 25 $。
该树的度为 4 的结点个数 $ n_4 = 2 $。

解释

通过题目给出的度数信息，利用树的基本性质（即树中所有结点的度数之和加上 1 等于结点总数），我们得到了方程，解出总结点数和度为 4 的结点数。

题目03.已知一棵度为 $ m $ 的树中，有 $ n_1 $ 个度为 1 的结点，有 $ n_2 $ 个度为 2 的结点，……，有 $ n_m $ 个度为 $ m $ 的结点。问该树有多少个叶子结点？

解答

根据树的基本性质“树中所有结点的度数之和加 1 等于结点数”，我们可以推导出叶子结点的个数。

总结点数表达式：
树中的总结点数可以表示为： $ n = n_0 + n_1 + n_2 + + n_m $ 其中，$ n_0 $ 表示叶子结点的个数，$ n_1, n_2, , n_m $ 分别表示度为 1, 2, , $ m $ 的结点个数。
度数总和公式：
树中所有结点的度数之和加 1 等于总结点数 $ n $，可以表示为：$ n = n_1 + 2n_2 + 3n_3 + + mn_m + 1 $
叶子结点个数：
利用总结点数和度数关系，结合公式 $ n = n_0 + n_1 + n_2 + + n_m $，我们可以推导出叶子结点 $ n_0 $ 的个数： $ n_0 = (n_1 + 2n_2 + 3n_3 + + mn_m + 1) - (n_1 + n_2 + + n_m) $
简化表达式：
通过简化，可以得到： $ n_0 = (n_2 + 2n_3 + + (m-1)n_m + 1) $

这意味着叶子结点的个数等于总结点数与各个度数结点之间的关系差减后的结果。