一、树的基本概念

1、树的定义

树是 $n$（$n \ge 0$）个结点的有限集。当 $n \eq 0$ 时，称为空树。在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点。

2. 当 $n \gt 1$ 时，其余节点可分为 $m$（$m \gt 0$）个互不相交的有限集 $T_1,T_2,...,T_m$，其中每个集合本身又是一棵树，并且称为根的子树。

3. 显然，树的定义是递归的，即在树的定义中又用到了自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

   • 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱(也叫父亲结点）。
   • 树中所有结点可以有零个或多个后继（也叫儿子节结）。
   • 因此 $n$ 个结点的树中有 $n-1$ 条 边。

2、基本术语

下面结合图示来说明一下树的一些基本术语和概念。

1. 考虑结点 $K$。根 $A$ 到结点 $K$ 的唯一路径上的任意结点,称为结点 $K$ 的祖先。如结点 $B$ 是结点 $K$ 的祖先,而结点 $K$ 是结点 $B$ 的子孙。路径上最接近结点 $K$ 的结点 $E$ 称为 $K$ 的双亲,而 $K$ 为结点 $E$ 的孩子。根 $A$ 是树中唯一没有父亲的结点。有相同父亲的结点称为兄弟,如结点 $K$ 和结点 $L$ 有相同的父亲 $E$, 即 $K$ 和 $L$ 为兄弟。

2. 树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。如结点 $B$ 的度为$2$,结点 $D$ 的度为 $3$ ,树的度为 $3$。

3. 度大于 $0$ 的结点称为分支结点(又称非终端结点); 度为 $0$ (没有子女结点)的结点称为叶子结点(又称终端结点)。在分支结点中，每个结点的分支数就是该结点的度。

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

   • 结点的层次从树根开始定义,根结点为第1层,它的子结点为第 $2$ 层,以此类推。双亲在同一层的结点互为堂兄弟,图中结点 $G$ 与 $E$, $F$, $H$, $I$ ,$J$ 互为堂兄弟。
   • 结点的深度是从根结点开始自顶向下逐层累加的。
   • 结点的高度是从叶结点开始自底向上逐层累加的。
   • 树的高度(或深度)是树中结点的最大层数。图中树的高度为4。

5. 有序树和无序树。树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。假设图为有序树,若将子结点位置互换,则变成一棵不同的树。

6. 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。

注意:由于树中的分支是有向的,即从双亲指向孩子,所以树中的路径是从上向下的,同一双亲的两个孩子之间不存在路径。

7. 森林。森林是 $m$ ($m \ge 0$ )棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

注意:上述概念无须刻意记忆， 根据实例理解即可。

3、树的性质

树具有如下最基本的性质：

1. 树中的任意两个顶点之间有且只有一条路径（如果没有路径，就是连棵树，如果多于一条路径，就构成环）
2. 出根结点之外的结点都有父亲；除叶子结点之外的结点都有儿子
3. 树中的结点数等于所有结点的度数加 1 。
4. 每个结点的度均不超过 $m$ 的树中第 $i$ 层上至多有 $m^(i − 1)$ 个结点（$i \ge 1$）
5. 高度为 $h$ 的 $m$ 叉树至多有( $m^h − 1$ ) / ( $m − 1$ ) 个结点。
6. 具有 $n$ 个结点的m叉树的最小高度为[ $\log_m ( n ( m − 1 ) + 1 )$ ] 。

本文内容参考了网络链接：https://blog.csdn.net/u011397981/article/details/129751663