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]]
创建的先序递归算法如下所示：