【数据结构】C语言实现树和森林的遍历

导读

大家好，很高兴又和大家见面啦！！！

在上一篇内容中我们介绍了树、森林与二叉树之间的相互转换，其核心逻辑就是通过孩子兄弟存储结构对树、森林进行存储，完成存储后的树和森林就被转换成了一棵二叉树。

说到二叉树，那我们就不能介绍一下遍历操作了。在二叉树中我们可以进行四中遍历：

• 先序遍历：按根->左->右的方式进行遍历
• 中序遍历：按左->根->右的方式进行遍历
• 后序遍历：按左->右->根的方式进行遍历
• 层序遍历：按从上到下，从左到右的方式进行遍历

在树和森林中，并没有像二叉树一样有这么多的遍历方式。我们以中序遍历为例：

• 在二叉树中结点是标准的左子树、根结点、右子树的形态，因此我们可以按照左->根->右的形式完成遍历；
• 在树中，每个结点的孩子结点不一定是2个孩子，可能会出现多个孩子的情况，此时我们无法准确的划分左->根->右三部分；

如上图所示，当一棵树的度大于2时，我们只能够划分根结点与孩子结点，并不能划分左子树与右子树。因此在树中不存在中序遍历。

那么树与森林我们应该如何实现遍历操作呢？在今天的内容中，我们将详细探讨树与森林的遍历操作，并通过C语言实现树与森林的遍历；

一、树的遍历

遍历也就是访问树中的所有结点，完成访问后，我们会得到一个对应的遍历序列。在同一棵树中，根据遍历方式的不同，我们会得到不同的遍历序列。

在树中常见的有两种遍历方式：

• 先根遍历
  • 先访问根结点
  • 再依次访问根结点的每一棵子树
  • 遍历子树时，同样按照先根后子树的规则进行访问
• 后根遍历
  • 先访问根结点的每一棵子树
  • 再访问根结点
  • 遍历子树时，同样按照先子树后根的规则进行访问

另外，树和二叉树也可以进行层序遍历，遍历的规则依旧是从上到下，从左到右。

在树的遍历中，整个遍历的过程与二叉树一致，唯一不同的就是孩子结点的数量：

• 在二叉树中，孩子结点的数量不会超过2个
• 在树中，孩子结点的数量则不可控，根据结点的度不同，孩子的数量也不相同

但是整个遍历的过程中，遍历的顺序一定是从左往右进行遍历。

二、森林的遍历

在森林中，可能会同时存在多棵非空树，如果我们以结点为分界线来将森林进行划分，我们就会得到3部分：

• 左侧的子树
• 根结点
• 右侧的其他树组成的森林

因此，在森林中我们的遍历方式有两种方式：

• 先序遍历：
  • 先访问根结点
  • 再访问当前根结点的子树
  • 最后访问右侧森林
• 中序遍历：
  • 先访问当前根结点的子树
  • 再访问根结点
  • 最后访问右侧森林

此时有朋友可能会奇怪，为什么我们可以将森林分为三个部分，但是我们无法进行后序遍历呢？在森林中可不可以进行层序遍历呢？

下面我们就来对这两个问题进行探讨；

2.1 为什么森林没有后序遍历？

前面我们对森林的划分，虽然我们将其分为了3部分，但是实际上我们是将森林划分成了两部分：

• 一棵树
• 其他树组成的森林

并且森林的两种遍历方式的底层逻辑也是如此：

• 先完成一棵树的遍历
• 再遍历森林中的其它树
• 直到完成森林中所有树的遍历

在二叉树中，之所以能够实现后序遍历，这是因为左右子树与根结点之间是有一定的关联的。

但是在森林中，其他树组成的森林与当前遍历的树的根结点之间并无任何联系，因此我们无法通过当前的结点找到其它树的结点，同时我们也无法从其他树的结点找到当前树的根结点。

正是因为森林中的树互不相交这个特性，所以我们无法完成对森林的后序遍历。

2.2 森林中存不存在层序遍历？

在二叉树中，层序遍历是借助队列实现的，而我们在进行入队操作时，是根据结点之间的联系完成的入队操作；

而在森林中，各棵树之间并无联系，因此当我们在执行入队操作时，无法从一棵树的结点找到另一棵树的结点，也就无法在对当前的树进行遍历时去遍历其他的树，所以在森林中无法实现层序遍历。

树与森林的遍历逻辑我们就介绍完了，接下来我们就尝试着通过C语言来实现一棵树与森林的遍历；

三、C语言实现

3.1 准备工作

在开始编写C语言代码之前，我们还是先要完成最基本的准备工作：

• 打开编辑器：我使用的是VS2019
• 创建空项目
• 创建头文件与源文件

这里我选择创建3个文件——树与森林的头文件、树与森林遍历实现的源文件以及测试源文件，文件的命名就根据自己的喜好了，我这里是用于博客，所以我的文件命名为："blog.h"、"blog.c"、"test.c"。

完成文件创建后，就是头文件的引用了。实现树与森林的遍历，我们需要实现至少4个功能：

• 树与森林的创建
• 树与森林的遍历
• 树与森林的销毁
• 树与森林的打印

这里我们还是采用的动态函数来实现树与森林的内存管理，因此需要引用动态函数头文件：<stdlib.h>以及断言头文件<assert.h>；

要完成正常的输入输出，那我们肯定需要引入标准输入输出的头文件：<stdio.h>；

完成了初步的准备工作后，接下来我们就需要一步一步的进行算法的实现了；

3.2 数据结构的选择

今天我们会实现如下图所示的树与森林遍历：

在前面的介绍中，我们介绍了3种树与森林的存储结构。其中我们经常使用的是与孩子兄弟表示法相同的二叉链表，因此在今天的实现中，我们会通过孩子兄弟表示法的方式实现上图所示的树与森林：

typedef char ElemType;
//孩子兄弟表示法
typedef struct ChildBrotherNode {ElemType data;//数据域struct ChildBrotherNode* lchild;//左孩子struct ChildBrotherNode* rbrother;//右兄弟
}CBNode, * CBTree;
//CBNode——孩子兄弟结点
//CBTree——孩子兄弟树
typedef struct ChildBrotherForest {CBTree* trees;//森林中的树int n;//树的个数
}CBForest;
//CBForest——孩子兄弟森林

为了区分树与森林，这里我将森林单独分离出来，通过线性表来记录森林中的树，这个与上一篇中的森林的孩子兄弟表示法的介绍有些区别，希望大家能够理解，如果和什么疑问可以评论区留言。

3.3 树与森林的创建

通过孩子兄弟表示法实现的是树与森林转换后的一棵二叉树，而二叉树的创建过程，我们依旧通过先序遍历的方式创建，其对应的二叉树先序序列如下所示：

//树
[A,B,E,0,0,C,F,0,G,0,0,D,H,0,I,0,J,0,0,0,0]
//森林
[[A,0,0],[B,E,0,0,0],[C,F,0,G,0,0,0],[D,H,0,I,0,J,0,0,0]]

创建的先序递归算法如下所示：