【数据结构】树的基本：结点、度、高度与计算

树是数据结构中一种重要的非线性结构，广泛应用于计算机科学的各个领域，例如文件系统、数据库索引、编译器等。理解树的各种性质，如结点数、度、高度等，对于解决实际问题至关重要。

本文将会探讨树的基本概念，以及给出几个王道考研例题和常见公式，不对树的数据结构做出过多原理解释

1. 树的基本概念

• 结点 (Node)： 树中的每个元素称为结点。结点包含数据和指向子结点的指针。
• 边 (Edge)： 连接两个结点的线称为边。
• 根结点 (Root)： 树的顶端结点，没有父结点。
• 父结点 (Parent)： 若一个结点包含指向另一个结点的指针，则称前者为后者的父结点。
• 子结点 (Child)： 若一个结点被另一个结点指向，则称前者为后者的子结点。
• 兄弟结点 (Sibling)： 拥有同一个父结点的结点互称为兄弟结点。
• 叶结点 (Leaf)： 没有子结点的结点称为叶结点。
• 度 (Degree)： 一个结点的子结点个数称为该结点的度。
• 树的度 (Degree of a Tree)： 树中所有结点的度的最大值称为树的度。
• 路径 (Path)： 从一个结点到另一个结点所经过的结点序列称为路径。
• 路径长度 (Path Length)： 路径上边的数量。
• 层 (Level)： 根结点为第 1 层，其子结点为第 2 层，以此类推。
• 高度 (Height)： 从根结点到最远叶子结点的最长路径上的结点数（或边的数量加 1）。
• 深度 (Depth)： 从根结点到该结点的路径长度加 1。

2. 树的重要性质和公式

1. 结点数与度数的关系： 设 $n$ 为树的结点总数，$n_i$ 表示度为 $i$ 的结点个数，则有：

   $$n=\sum _{i=0}^m{n}_i$$

   其中 $m$ 是树的度。同时，根据每个结点（除根结点外）都恰好有一个父结点，可以得到：

   $$n=\sum _{i=0}^{m}i\cdot n_i+1$$

   这个公式非常重要，在很多题目中都会用到。

2. 第 $i$ 层最多结点数： 度为 $m$ 的树中，第 $i$ 层上至多有 $m^{i-1}$ 个结点 ($i\ge 1$)。这个性质可以通过数学归纳法证明。

3. 高度为 $h$ 的 $m$ 叉树最多结点数： 高度为 $h$ 的 $m$ 叉树至多有 $\frac{m^h-1}{m-1}$ 个结点。当每一层的结点数都达到最大值时，总结点数达到最大。这个公式可以通过等比数列求和公式推导得出：

   $$1+m+m^2+\cdots +m^{h-1}=\frac{m^h-1}{m-1}$$

4. $n$ 个结点的 $m$ 叉树最小高度： 度为 $m$、具有 $n$ 个结点的树的最小高度 $h$ 为 $\lceil {\log }_m(n(m-1)+1)\rceil$，其中 $\lceil x\rceil$ 表示向上取整。为了使高度最小，应尽可能使每一层的结点数都达到最大值，即形成完全 $m$ 叉树。

   推导过程如下：假设前 $h-1$ 层都是满的，则前 $h-1$ 层的结点数为 $\frac{m^{h-1}-1}{m-1}$。加上第 $h$ 层的结点，总结点数 $n$ 满足：

   $$\frac{m^{h-1}-1}{m-1}<n\le \frac{m^h-1}{m-1}$$

   化简不等式，可得最小高度 $h$。

5. $n$ 个结点的 $m$ 叉树最大高度： 度为 $m$、具有 $n$ 个结点的树的最大高度 $h$ 为 $n-m+1$。为了使高度最大，应尽可能使除少数结点外，其他结点都只有一个子结点，形成“链状”结构。

---

3. 例题实战

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

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

解析： 根据性质 5，度为 4 的树，其最大高度为 $n-4+1=n-3$，故 A 正确。C 选项根据性质 2，第 $i$ 层最多有 $4^{i-1}$ 个结点，而不是 $4(i-1)$ 个。D 不一定成立，例如只有根结点和四个子结点的树，只有一层有 4 个结点。

答案： A

---

例题 05： 度为 4、高度为 $h$ 的树，()。

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

解析： 根据性质 5 的逆推，高度为 $h$、度为 $m$ 的树至少有 $h+m-1$ 个结点，所以度为 4、高度为 $h$ 的树至少有 $h+4-1=h+3$ 个结点，故 A 正确。

答案： A

---

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

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

解析： 根据性质 4，最小高度 $h=\lceil {\log }_3(50(3-1)+1)\rceil =\lceil {\log }_3(101)\rceil$。因为 $3^4=81$， $3^5=243$，所以 ${\log }_3(101)$ 介于 4 和 5 之间，向上取整为 5。

答案： C

---

例题 07： 若森林 $F$ 有 15 条边、25 个结点，则 $F$ 包含树的个数是（ ）。

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

解答：
森林的性质：对于一片森林，树的个数 $t=n-e$，其中 $n$ 是结点数，$e$ 是边数。
代入数据：

$t=25-15=10$

因此，森林 FF 包含 10 棵树。

答案： C

---

例题8： 设呀一颗 $m$ 叉树中有 $N_1$ 个度数为 $1$ 的节点，$N_2$ 个度数为 $2$ 的节点 $...$ $N_m$ 个度数为 $m$ 的节点，则该树中共有( )个叶子节点

A. ${\sum }_{i=1}^m(i-1)N_i$

B. ${\sum }_{i=1}^m{N}_i$

C. ${\sum }_{i=2}^m(i-1)N_i$

D. ${\sum }_{i=2}^m(i-1)N_i+1$

**答案：**D

解答：

在一颗 $m$ 叉树中，除了叶节点之外，每个节点都有一个父节点，因此我们可以利用下面两个等式：

1. 总节点数 = 叶子节点 + 非叶子节点
2. 总节点数 = 总度数 + 1 -> 总度数 = 总节点数 - 1

所以，我们假设总节点数为$N$，叶子节点数为$N_0$，则

• 总结点数 $N=N_0+N_1+N_2+...+Nm$
• 总度数 = $1\ast N_1+2\ast N_2+...+m\ast N_M$

联立等式

$N_0+N_1+N_2+...+Nm-1=1\ast N_1+2\ast N_2+3\ast N_3+...+m\ast N_M$

可解的

$N_0=1\ast N_2+...+(m-1)\ast N_m+1$

$N_0={\sum }_{m=2}^m(m-1)N_m+1$

---

例题9：【2010 统考真题】在一棵度为 4 的树 $T$ 中，若有 20 个度为 4 的结点， 10 个度为 3 的结点， 1 个度为 2 的结点， 10 个度为 1 的结点，则树 $T$ 的叶结点个数是（ ）。
A． 41
B． 82
C． 113
D． 122

答案： B

解答：

这个问题是问题 08 的一个具体应用。已知了每个度数的结点数量，我们可以直接套用问题 08 中推导出的公式。

根据问题 08 的公式：

$$N_0=\sum _{i=2}^m(i-1)N_i+1$$

在问题 09 中，$m=4,N_1=10,N_2=1,N_3=10,N_4=20$ 。将这些直代入公式：

$$\begin{array}{rl}& N_0=(2-1)\ast N_2+(3-1)\ast N_3+(4-1)\ast N_4+1\\ & N_0=(1)\ast 1+(2)\ast 10+(3)\ast 20+1\\ & N_0=1+20+60+1\\ & N_0=82\end{array}$$

6. 关键点总结

• 结点数与度数的关系： $n={\sum }_{i=0}^{m}i\cdot n_i+1$
• 第 $i$ 层最多结点数： $m^{i-1}$
• 高度为 $h$ 的 $m$ 叉树最多结点数： $\frac{m^h-1}{m-1}$
• $n$ 个结点的 $m$ 叉树最小高度： $\lceil {\log }_m(n(m-1)+1)\rceil$
• $n$ 个结点的 $m$ 叉树最大高度： $n-m+1$
• 对于一片森林，树的个数 $t=n-e$，其中 $n$ 是结点数，$e$ 是边数