admin管理员组文章数量:1444890
【数据结构】C语言实现树和森林的遍历
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种树与森林的存储结构。其中我们经常使用的是与孩子兄弟表示法相同的二叉链表，因此在今天的实现中，我们会通过孩子兄弟表示法的方式实现上图所示的树与森林：
代码语言：javascript代码运行次数：0运行复制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 树与森林的创建
通过孩子兄弟表示法实现的是树与森林转换后的一棵二叉树，而二叉树的创建过程，我们依旧通过先序遍历的方式创建，其对应的二叉树先序序列如下所示：
代码语言：javascript代码运行次数：0运行复制//树
[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]]创建的先序递归算法如下所示：
代码语言：javascript代码运行次数：0运行复制//先序创建孩子兄弟树
CBTree CreateCBTree(ElemType* arr, int* pi, int len) {
//arr——树的先序序列
//pi——当前访问下标
//len——先序序列长度
assert(arr && pi);//判断数组与下标是否为空指针
if (*pi == len || arr[*pi] == 0) {
return NULL;
}
CBNode* p = (CBNode*)calloc(1, sizeof(CBNode));
assert(p);
//访问根结点
p->data = arr[*pi];
*pi += 1;
//创建左子树
p->lchild = CreateCBTree(arr, pi, len);
*pi += 1;
//创建右兄弟
p->rbrother = CreateCBTree(arr, pi, len);
return p;
}
//创建森林
CBForest* CreateCBForest(ElemType** arr, int* n, int len) {
//arr——森林中各树的先序序列
//n——森林中各树先序序列的长度
//len——森林中树的数量
assert(arr && n);
CBForest* forest = (CBForest*)calloc(1, sizeof(CBForest));
assert(forest);
forest->n = len;//森林中树的个数
//为树申请根结点空间
forest->trees = (CBTree*)calloc(len, sizeof(CBTree));
assert(forest->trees);
//让森林中的每棵树都以孩子兄弟树的形式创建
for (int i = 0; i < len; i++) {
int pi = 0;
//先序创建孩子兄弟树
forest->trees[i] = CreateCBTree(arr[i], &pi, n[i]);
}
//返回创建好的森林
return forest;
}森林是多棵二叉树的集合，而我们要将森林转化为孩子兄弟二叉树，我们只需要将各棵树的根结点通过右兄弟指针进行关联：
代码语言：javascript代码运行次数：0运行复制//森林转化孩子兄弟二叉树
CBTree Forest_to_CBTree(CBForest* forest) {
assert(forest);
//创建一个新的孩子兄弟树的根结点
CBTree forest_tree = (CBTree)calloc(1, sizeof(CBNode));
assert(forest_tree);
//根结点中存储的值为森林中第一棵树的根结点的值
forest_tree->data = forest->trees[0]->data;
//根结点的左子树指向的是森林中第一棵树的左子树
forest_tree->lchild = forest->trees[0]->lchild;
//通过指针p来完成森林中的树的连接
CBNode* p = forest_tree;
for (int i = 1; i < forest->n; i++) {
//创建新的根节点
CBNode* root = (CBNode*)calloc(1, sizeof(CBNode));
assert(root);
//新的根节点记录当前根结点的信息
root->data = forest->trees[i]->data;
root->lchild = forest->trees[i]->lchild;
//处理第一棵树与第二棵树之间的连接
if (i == 1) {
//第一棵树的根结点的右兄弟指针指向第二棵树的根结点
forest_tree->rbrother = root;
}
//处理其它树之间的连接
else {
//当前根结点的右兄弟指针指向下一棵树的根结点
p->rbrother = root;
}
//p指针移动到下一棵树
p = root;
}
return forest_tree;
}为了不影响后续遍历的测试，这里我们采用创建新的根结点指向森林中各个根结点的子树，并将这新创建的根结点通过右指针相连。
如果是不需要观察森林与其生成的二叉树的遍历的关系的话，我们是可以直接选择修改森林中各棵树的根结点右兄弟的指向；
3.4 树与森林的遍历
在树的变量中，我们主要实现先根遍历与后根遍历，下面我们就来一一实现这两种遍历方式：
3.4.1 先根遍历
先根遍历的基本逻辑为：
- 先访问根结点
- 再从左向右以此访问各子树，直到完成所有子树的访问
根据该逻辑，我们可以得到一个初步的实现框架：
代码语言：javascript代码运行次数：0运行复制//先根遍历
void PreOrderTree(CBTree tree) {
if (!tree) {
return;
}
//访问根结点
visit(tree->data);
//当前结点的孩子
CBNode* child = tree->lchild;
while (child) {
//当孩子存在时，继续先根遍历孩子
PreOrderTree(child);
//遍历下一个孩子
child = child->rbrother;
}
}访问根结点的方式，我们还是以打印的方式完成访问，打印的话我们可以直接通过库函数printf实现，如下所示：
//先根遍历
void PreOrderTree(CBTree tree) {
if (!tree) {
return;
}
//访问根结点
printf("%c\t", tree->data);
//当前结点的孩子
CBNode* child = tree->lchild;
while (child) {
//当孩子存在时，继续先根遍历孩子
PreOrderTree(child);
//遍历下一个孩子
child = child->rbrother;
}
}下面我们还会对其生成的二叉树实现先根遍历：
代码语言：javascript代码运行次数：0运行复制//其转换的二叉树的遍历
void PreOrderCBTree(CBTree tree) {
if (!tree) {
return;
}
printf("%c\t", tree->data);
PreOrderCBTree(tree->lchild);
PreOrderCBTree(tree->rbrother);
}这个实现就是最简单的二叉树遍历的逻辑，这里我就不再赘述；
3.4.2 后根遍历
后根遍历的基本逻辑为：
- 先访问所有的孩子结点
- 再访问根结点
与先根遍历一样，后根遍历对根结点的访问我们同样是通过printf实现，如下所示：
//后根遍历
void PostOrderTree(CBTree tree) {
if (!tree) {
return;
}
//当前结点的孩子
CBNode* child = tree->lchild;
while (child) {
//当孩子存在时，继续后根遍历孩子
PostOrderTree(child);
//遍历下一个孩子
child = child->rbrother;
}
//访问根结点
printf("%c\t", tree->data);
}同时我们还会实现其生成的二叉树的中序遍历以及后序遍历：
代码语言：javascript代码运行次数：0运行复制//其转换的二叉树的中序遍历
void InOrderCBTree(CBTree tree) {
if (!tree) {
return;
}
InOrderCBTree(tree->lchild);
printf("%c\t", tree->data);
InOrderCBTree(tree->rbrother);
}
//其转换的二叉树的后序遍历
void PostOrderCBTree(CBTree tree) {
if (!tree) {
return;
}
PostOrderCBTree(tree->lchild);
PostOrderCBTree(tree->rbrother);
printf("%c\t", tree->data);
}由于我们在结点中存储的是字符，所以我们在打印时使用的占位符为%c。
3.4.3 森林的遍历
在森林的先序遍历后中序遍历中，如果我们只看单棵树的遍历，我们就会发现：
- 森林的先序遍历与树的先根遍历一致
- 森林的中序遍历与树的后根遍历一致
如果无法理解这两句话，下面我们就来通过图片理解：
树的遍历我们已经明白其原理了，而森林的遍历我们实际上还是完成的树的遍历，只不过此时对于每棵树的根结点而言，它不再是空指针，而是指向的其他树。
森林的先序遍历与中序遍历是根据我们遍历一棵树时使用的遍历方式而进行区分的：
- 先序遍历：
- 先访问当前根节点
- 再访问当前根结点的子树
- 最后访问其它树组成的森林
- 中序遍历
- 先访问当前根结点的子树
- 在访问当前根结点
- 最后访问其它树组成的森林
森林遍历的前面两步是不是很熟悉？没错，它就是树的先根遍历与后根遍历。因此我们可以直接将森林的遍历归纳为：
- 先序遍历：
- 完成一棵树的先根遍历
- 再访问其它的树组成的森林
- 中序遍历：
- 完成一棵树的后根遍历
- 再访问其它的树组成的森林
在理解了这个点后，森林的遍历就很容易了如下所示：
代码语言：javascript代码运行次数：0运行复制//森林的遍历
//先序遍历
void PreOrderForest(CBForest* forest) {
if (!forest) {
return;
}
for (int i = 0; i < forest->n; i++) {
PreOrderCBTree(forest->trees[i]);
}
}
//森林生成的二叉树的先序遍历
void PreOrderCBForest(CBTree cbforest) {
if (!cbforest) {
return;
}
PreOrderCBTree(cbforest);
}
//中序遍历
void InOrderForest(CBForest* forest) {
if (!forest) {
return;
}
for (int i = 0; i < forest->n; i++) {
PostOrderTree(forest->trees[i]);
}
}
//森林生成的二叉树的中序遍历
void InOrderCBForest(CBTree cbforest) {
if (!cbforest) {
return;
}
InOrderCBTree(cbforest);
}
//森林生成的二叉树的后序遍历
void PostOrderCBForest(CBTree cbforest) {
if (!cbforest) {
return;
}
PostOrderCBTree(cbforest);
}现在我们也完成了树、森林与二叉树的遍历操作，接下来，我们还需要实现销毁操作；
3.5 树与森林的销毁
树的销毁逻辑都是从最底层开始从下往上销毁，因此四棵树的销毁都是采用的后根遍历的方式完成的销毁，代码如下所示：
代码语言：javascript代码运行次数：0运行复制//树的销毁
void DestroyCBTree(CBTree* tree) {
assert(tree);
if (*tree == NULL) {
return;
}
//后根遍历完成销毁
DestroyCBTree(&(*tree)->lchild);
DestroyCBTree(&(*tree)->rbrother);
free(*tree);
*tree = NULL;
}
//森林的销毁
void DestroyForest(CBForest** forest) {
assert(forest);
if (*forest == NULL) {
return;
}
//依次销毁森林中的每一棵树
for (int i = 0; i < (*forest)->n; i++) {
DestroyCBTree(&((*forest)->trees[i]));
if ((*forest)->trees[i] == NULL) {
printf("森林中的第 %d 棵树已销毁\n", i + 1);
}
}
free((*forest)->trees);
(*forest)->trees = NULL;
free(*forest);
*forest = NULL;
}在森林的销毁中，因为我们在前面创建孩子兄弟树时，已经通过各棵树的右兄弟指针将其关联起来，所以在销毁时，我们只需要传入第一棵树的根结点即可完成森林中所有树的销毁。
结语
在今天的内容中我们介绍了树与森林遍历的C语言实现。
今天的内容到这里就全部结束了，在下一篇内容中我们将介绍《哈曼夫树》，大家记得关注哦！如果大家喜欢博主的内容，可以点赞、收藏加评论支持一下博主，当然也可以将博主的内容转发给你身边需要的朋友。最后感谢各位朋友的支持，咱们下一篇再见！！！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-18，如有侵权请联系 cloudcommunity@tencent 删除存储二叉树数据结构遍历指针本文标签： 数据结构C语言实现树和森林的遍历
版权声明：本文标题：【数据结构】C语言实现树和森林的遍历 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/biancheng/1748213636a2827260.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论