26考研——树与二叉树_树、森林（5）

408答疑

二、树、森林

树的基本概念

树的定义和特性

树的定义

树是一个递归的概念，由 $n(n\ge 0)$ 个结点的有限集组成。当 $n=0$ 时，称为空树。在任意一棵非空树中应满足：

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

树的特性

树作为逻辑结构，同时也是一种分层结构，具有以下两个特点：

1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
2. 树中所有结点都可以有零个或多个后继。

树适用于表示具有层次结构的数据。树中的某个结点（除根结点外）最多只和上一层的一个结点（其父结点）有直接关系，根结点没有直接上层结点，因此在 $n$ 个结点的树中有 $n-1$ 条边。而树中每个结点与其下一层的零个或多个结点（其孩子结点）都有直接关系。

基本术语

树的基本术语和概念

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

• 祖先：从根结点到某一结点的唯一路径上的所有其他结点。
  • 结点$K$的祖先是从根$A$到$K$的唯一路径上的所有其他结点。
• 子孙：某一结点的子树中所有结点。
  • 如结点$B$是$K$的祖先，而$K$是$B$的子孙，结点$B$的子孙包括$E,F,K,L$。
• 双亲：某一结点的直接前驱，即指向该结点的结点。
• 孩子：某一结点的直接后继，即该结点指向的结点。
  • 路径上最接近$K$的结点$E$称为$K$的双亲，$K$为$E$的孩子。
• 兄弟：有相同双亲的结点。
• 堂兄弟：在同一层的结点互为堂兄弟。
  • 有相同双亲的结点称为兄弟（如$K$和$L$）。
  • 双亲在同一层的结点互为堂兄弟（如$G$与$E$、$F$、$H$、$I$、$J$）。
• 根$A$是树中唯一没有双亲的结点。

结点的层次、度、深度和高度

• 层次：从树根开始定义，根结点为第1层，它的孩子为第2层，以此类推。
• 结点的度：一个结点的孩子个数称为该结点的度。
  • 如结点$B$的度为2，结点$D$的度为3。
• 深度：结点所在的层次。
• 高度：以该结点为根的子树的高度。

树的度和高度

• 树的度：树中结点的最大度数称为树的度。
  • 上图中树的度为3。
• 树的高度：树的高度（或深度）是树中结点的最大层数。
  • 上图中树的高度为4。

分支结点和叶结点

• 分支结点：度大于0的结点称为分支结点（也称非终端结点）。
• 叶结点：度为0（没有孩子结点）的结点称为叶结点（也称终端结点）。

有序树和无序树

• 有序树：树中结点的各子树从左到右是有次序的，不能互换。
• 无序树：树中结点的各子树从左到右没有次序，可以互换。
  • 假设上图为有序树，若将子结点位置互换，则变成一棵不同的树。

路径和路径长度

• 路径：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。
  • 因为树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径。
• 路径长度：路径上所经过的边的个数。

森林的基本术语和概念

森林的定义

• 森林：是 $m(m\ge 0)$ 棵互不相交的树的集合。

森林与树的关系

• 森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给 $m$ 棵独立的树加上一个结点，并把这 $m$ 棵树作为该结点的子树，则森林就变成了树。

树的性质

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

   • 结点的度数是指该结点的孩子数量，每个结点与其每个孩子都由唯一的边相连，因此树中所有结点的度数之和等于树中的边数之和。
   • 树中的结点（除根外）都有唯一的双亲，因此结点数 $n$ 等于边数之和加1，即所有结点的度数之和加1。

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

   • 第1层至多有1个结点（根结点），第2层至多有 $m$ 个结点，第3层至多有 $m^2$ 个结点，以此类推。
   • 使用数学归纳法可推出第 $i$ 层至多有 $m^{i-1}$ 个结点。

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

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

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

   • 为使树的高度最小，在前 $h-1$ 层中，每层的结点数都要达到最大，前 $h-1$ 层最多有 $\frac{(m^{h-1}-1)}{(m-1)}$ 个结点，前 $h$ 层最多有 $\frac{(m^h-1)}{(m-1)}$ 个结点。
   • 因此 $\frac{(m^{h-1}-1)}{(m-1)}<n\le \frac{(m^h-1)}{(m-1)}$，即 $h-1<{\log }_m(n(m-1)+1)\le h$，解得 $h_{\text{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$ 个结点。

总结

• 树中的结点数等于所有结点的度数之和加1。
• 度为 $m$ 的树中第 $i$ 层上至多有 $m^{i-1}$ 个结点。
• 高度为 $h$ 的 $m$ 叉树至多有 $\frac{m^h-1}{m-1}$ 个结点。
• 具有 $n$ 个结点的 $m$ 叉树的最小高度为 $\lceil {\log }_m(n(m-1)+1)\rceil$。

树的存储结构

概述

树的存储方式有多种，既可采用顺序存储结构，又可采用链式存储结构，但无论采用何种存储方式，都要求能唯一地反映树中各结点之间的逻辑关系。这里介绍3种常用的存储结构。

双亲表示法

• 定义：这种存储结构采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。
• 特点：根结点下标为0，其伪指针域为-1。双亲表示法利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的双亲结点，但求结点的孩子时则需要遍历整个结构。
• 图示：如下图所示，展示了树的双亲表示法及其指针图示。

注意事项

• 顺序存储结构与链式存储结构：树的顺序存储结构中，数组下标代表结点的编号，下标中所存的内容指示了结点之间的关系。而在二叉树的顺序存储结构中，数组下标既代表了结点的编号，又指示了二叉树中各结点之间的关系。
• 存储结构选择：二叉树属于树，因此二叉树也可用树的存储结构来存储，但树却不都能用二叉树的存储结构来存储。

孩子表示法和孩子兄弟表示法

孩子表示法

• 定义：孩子表示法是将每个结点的孩子结点视为一个线性表，且以单链表作为存储结构，则 $n$ 个结点就有 $n$ 个孩子链表（叶结点的孩子链表为空表）。
• 特点：$n$ 个头指针又组成一个线性表，为便于查找，可采用顺序存储结构。
• 图示：下图的是树的孩子表示法。

孩子兄弟表示法

• 定义：孩子兄弟表示法也称二叉树表示法，即以二叉链表作为树的存储结构。每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，以及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）。
• 图示：下图的是树的孩子兄弟表示法。
• 优点：孩子兄弟表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。

存储结构选择

• 孩子表示法：寻找孩子的操作非常方便，而寻找双亲的操作则需要遍历 $n$ 个结点中孩子链表指针域所指向的 $n$ 个孩子链表。
• 孩子兄弟表示法：若为每个结点增设一个 parent 域指向其父结点，则查找结点的父结点也很方便。

树、森林与二叉树的转换

树转为二叉树

转换规则

树转换为二叉树的规则是：每个结点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称为“左孩子右兄弟”。由于根结点没有兄弟，因此转换得到的二叉树没有右子树。

转换方法

1. 在兄弟结点之间加一连线：将树中每个结点的兄弟结点通过连线连接起来。
2. 保留第一个孩子的连线：对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉。
3. 旋转树结构：以树根为轴心，顺时针旋转45°。

转换性质

• 二叉树和树都可以用二叉链表作为存储结构。
• 从物理结构上看，树的孩子兄弟表示法与二叉树的二叉链表表示法是相同的，因此可以用同一存储结构的不同解释将一棵树转换为二叉树。

转换示例

下图展示了树与二叉树的对应关系，通过上述转换规则和方法，可以将树转换为二叉树。

森林转为二叉树

将森林转换为二叉树的规则与树类似。先将森林中的每棵树转换为二叉树，由于任意一棵树对应的二叉树的右子树必空，森林中各棵树的根也可视为兄弟关系，将第二棵树对应的二叉树当作第一棵二叉树根的右子树……以此类推，就可以将森林转换为二叉树。

转换方法

1. 将森林中的每棵树转换成相应的二叉树。
2. 每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线。
3. 以第一棵树的根为轴心顺时针旋转45°。

二叉树转换为森林

二叉树转换为森林的规则：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，所以将根的右链断开。二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树，应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止，最后将每棵二叉树依次转换成树，就得到了原森林。

二叉树转换为树或森林是唯一的。

树和森林的遍历

树的遍历

遍历定义

树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有两种方式：

先根遍历

• 若树非空，先访问根结点。
• 再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。
• 其遍历序列与这棵树相应二叉树的先序序列相同。

后根遍历

• 若树非空，先依次遍历根结点的每棵子树，遍历子树时仍遵循先子树后根的规则。
• 再访问根结点。
• 其遍历序列与这棵树相应二叉树的中序序列相同。

遍历序列

• 下图的树的先根遍历序列为 $ABEFCDG$，后根遍历序列为 $EFBCGDA$。
• 另外，树也有层次遍历，与二叉树的层次遍历思想基本相同，即按层序依次访问各结点。

森林的遍历

先序遍历森林

按照森林和树相互递归的定义，可得到森林的两种遍历方法。先序遍历森林的规则如下：

1. 访问森林中第一棵树的根结点。
2. 先序遍历第一棵树中根结点的子树森林。
3. 先序遍历除去第一棵树之后剩余的树构成的森林。

中序遍历森林

中序遍历森林的规则如下：

1. 中序遍历森林中第一棵树的根结点的子树森林。
2. 访问第一棵树的根结点。
3. 中序遍历除去第一棵树之后剩余的树构成的森林。
   下图的森林的先序遍历序列为 $ABCDEFGHIJ$，中序遍历序列为 $BCDAFEHIG$。

森林与二叉树遍历方法的对应关系

当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换成右子树，可知森林的先序和中序遍历即为其对应二叉树的先序和中序遍历。

下表树和森林的遍历与二叉树遍历的对应关系

注意事项

部分教材也将森林的中序遍历称为后序遍历，称中序遍历是相对其二叉树而言的，称后序遍历是因为根确实是最后才访问的，若遇到这两种称谓，则可理解为同一种遍历方法。

四、参考资料

鲍鱼科技课件

b站免费王道课后题讲解:

网课全程班:

26王道考研书