5.1.1 树的定义#

树是 $n (n \geq 0)$ 个结点的有限集。当 n = 0 时，称为空树。在任意一棵非空树中必须满足：

1. 有且仅有一个特定的结点称为根结点。
2. 当 $n>1$ 时，其余结点可分为 $m$ ($m>0$) 个互不相交的有限集 $T_1, T_2, \cdots, T_m$，其中每个集合本身又是一棵树，称为根的子树。

显然，树的定义是递归的——在定义中引用了自身，因此树是一种典型的递归数据结构。作为一种逻辑结构，树同时也是一种分层结构，具有以下两个特征：

1. 根结点没有前驱，除根结点外的每个结点有且仅有一个前驱。
2. 所有结点均可拥有零个或多个后继。

树适用于表示具有层次结构的数据。除根结点外，树中任一结点最多只与上一层的一个结点(其父结点)存在直接关联；根结点则无上层结点。因此，在包含n个结点的树中，恰好存在n-1条边。同时，每个结点可与其下一层的零个或多个结点(其孩子结点)建立直接联系。

5.1.2 基本术语#

1. 祖先、子孙、双亲、孩子、兄弟和堂兄弟。

   考虑结点 K，从根 A 到结点 K 的唯一路径上所经过的所有其他结点，称为 K 的祖先。例如，结点 B 是 K 的祖先，而 K 是 B 的子孙；B 的子孙包括 E, F, K, L。该路径上最接近 K 的结点 E 称为 K 的双亲，K 则是 E 的孩子。根结点 A 是树中唯一没有双亲的结点。具有相同双亲的结点互为兄弟，如 K 与 L 的双亲均为 E，故 K 与 L 为兄弟。若两个结点的双亲位于同一层，则它们互为堂兄弟，如 G 与 E, F, H, I, J 互为堂兄弟。

2. 结点的层次、深度和高度。

   结点的层次从根开始定义：根为第1层，其孩子为第2层，以此类推。结点的深度即为其所在的层次。树的高度(或深度)是树中结点的最大层数。而结点的高度是指以其为根的子树的高度。

3. 结点的度和树的度。

   树中一个结点的孩子个数称为该结点的度；树中所有结点的度的最大值称为树的度。例如，结点 B 的度为 2，结点 D 的度为 3，因此该树的度为 3。

4. 分支结点和叶结点。

   度大于0的结点称为分支结点(也称非终端结点)；度为0(无孩子)的结点称为叶结点(也称终端结点)。在分支结点中，每个结点的分支数即为其度。

5. 有序树和无序树。

   若树中各结点的子树从左到右具有固定次序、不可互换，则称为有序树；否则称为无序树。

6. 路径和路径长度。

   树中两个结点之间的路径是由从一个结点到另一个结点所经过的结点序列构成的，路径长度则是该路径上边的数目。

7. 森林。

   森林是 $m (m \geqslant 0)$ 棵互不相交的树的集合。森林与树的概念密切相关：将树的根结点移除后，其各子树构成一个森林；反之，若为 m 棵独立的树添加一个新结点，并将其作为这 m 棵树的共同根，则森林便转化为一棵树。

NOTE

上述概念无须死记硬背，结合实例理解即可。考研通常不会直接考查定义，而是融入具体题目中综合考查。做题时若遇到不熟悉的概念，可随时查阅；随着练习增多，自然能够熟练掌握。

5.1.3 树的性质#

树具有如下基本性质：

1. 树的结点数 n 等于所有结点的度数之和加 1。

   结点与其每个孩子都有唯一的边相连，因此树中所有结点的度数之和等于边数；又因除根结点外每个结点均有唯一双亲，故结点数 n 等于边数加 1，即所有结点的度数之和加 1。

2. 度为 m 的树中，第 i 层上至多有 $m^{i-1}$ 个结点($i \geqslant 1$)。

   第1层至多有1个结点(根结点)；第2层至多有m个结点；第3层至多有 $m^{2}$ 个结点，以此类推。通过数学归纳法可以证明，第i层至多有 $m^{i-1}$ 个结点。

3. 高度为 h 的 m 叉树至多有 $(m^{h}-1)/(m-1)$ 个结点。

   当各层结点数达到最大时，树中至多有 $1+m+m^{2}+\cdots+m^{h-1}=(m^{h}-1)/(m-1)$ 个结点。

4. 度为 $m$、具有 $n$ 个结点的树的最小高度 $h$ 为 $\lceil \log_m(n(m-1)+1) \rceil$。

   要使高度最小，树应尽可能饱满，即前 $h-1$ 层每层的结点数均达到最大值。前 $h-1$ 层最多有 $(m^{h-1}-1)/(m-1)$ 个结点，前 $h$ 层最多有 $(m^h-1)/(m-1)$ 个结点。因此，$(m^{h-1}-1)/(m-1)<n \leq (m^h-1)/(m-1)$，即 $h-1<\log_m(n(m-1)+1)\leq h$，解得 $h_{\min}=\lceil \log_m(n(m-1)+1) \rceil$。

5. 度为 m、具有 n 个结点的树的最大高度 h 为 $n-m+1$。

   树的度为 m，因此至少有一个结点有 m 个孩子，它们处于同一层。为使树的高度最大，其他层可仅有一个结点，因此最大高度(层数)为 $n-m+1$。由此，也可逆推出高度为 h、度为 m 的树至少包含 $h+m-1$ 个结点。