[数据结构与算法]数据结构--树--二叉树的创建和遍历(前序、中序、后序、层序)

本文涉及完整代码已提交至Gitee，大家可以打开链接参考。

鄙人乃一介初学者，文中及代码中难免出错，恳请同志们批评指正！

1.有关树的定义和基本概念，请阅读：数据结构–树--树的定义和基本概念

2.有关二叉树的定义概念等基本知识，请阅读：数据结构–树--二叉树的定义、基本概念和性质

3.因为我的文字浅显，可能对二叉树的遍历创建过程描述的并不很清楚，又未配有插图，读者可参考网站visualgo中的二叉树部分，观察动画帮助理解。

本章内容：

1. 二叉树的存储结构；
2. 二叉树的创建；
3. 二叉树的遍历；
   1. 前序遍历
   2. 中序遍历
   3. 后序遍历
   4. 层序遍历

我们之前已经介绍了树和二叉树的基本概念，那么现在需要做的就是使用代码去实现树这种逻辑结构。所以和前面我们学过的每一种数据结构一样，我们首先要分析二叉树的存储结构，构建它的结构模型，再实现一些基本的操作。

🌳二叉树的存储方式

说到存储方式，我们自然而然地能够想到顺序存储结构和链式存储结构。那么二叉树是不是也可以使用这两种存储结构呢？我们分别来看一下。

🔅1.二叉树的顺序存储结构

我们先来分析一下树能否使用顺序存储结构。

对于上面这样的一棵树，我们发现如果使用顺序存储结构，那么如果子树特别多，且不同结点的子树个数完全不同，那么是很难使用顺序结构去实现树的存储的，因为我们并不容易去用下标来表示各个结点之间的关系。对于数组中的某个元素，如果使用编程语言，我们实现通过下标寻找它的双亲、子孙和兄弟是比较繁杂的。所以对于树来说使用顺序存储结构是很不方便的。

但是我们来看看二叉树。先来看完全二叉树：

对于这样一棵完全二叉树，我们可以从根结点开始编号排序。

我们发现，因为完全二叉树的特殊结构，使用顺序存储也是可以完美的实现存储的。但是如果是一般的二叉树呢？其实我们也可以将其补充成一个完全二叉树，只不过原先空的地方我们让其指向一个空元素。如下图：

对于这个二叉树，原本它不是完全二叉树，但是我们通过补充，让他成为了完全二叉树它的元素可以是这样存储：

我们可以发现，其中有一些空间被浪费掉了，并没有存储什么数据。但是为了保证能够完美存储二叉树，依旧需要浪费这些空间。

我们来想象一个更极端的场景，如果一棵二叉树是斜树，也就是说，从根结点到叶子结点只有左孩子或者只有右孩子，那么这棵二叉树要用顺序存储结构，就要浪费大量的空间，这显然是不够友好的。

综上所述，对于一棵完全二叉树来说，顺序结构是非常适用的。但是对于一般情况下的二叉树，我们需要寻求一种更节省空间的存储方式，就是我们的链式存储。

🔅2.二叉链表

我们说链表就是数个结点通过指针域的指向进行链接的一种结构。普通的单向链表中的结点包括数据域和指针域，但是二叉链表中的结点，我们发现只用一个指针域无法完成我们的需求，因此这里可以建立上图这种结点模型，一个结点包括数据域、左孩子域来指向该结点的左孩子、右孩子域来指向该结点的右孩子。

如下图1.1：

使用C语言来实现，依旧是一个结构体来构建结点模型：

//二叉树中的数据，这里我们先用字符类型ABCD...
typedef char tree_data;

//二叉树中每个结点的结构类型：
typedef struct node
{
	tree_data data;
	struct node* left;
	struct node* right;
}bintree;

🌳二叉树的创建及初始化

如何在内存中使用链式存储结构构建一棵二叉树呢？这似乎有点无从下手。那么我们首先来想一想，如果让一个用户去通过从键盘输入的方式构建一棵二叉树他该输入什么呢？为了搞明白如何输入，我们就要先确定怎么去读这棵二叉树，我们以上图1.1为例，讲讲以何种方式去读取这棵二叉树的元素。其实按照什么顺序去读就是按照什么顺序去遍历。

看到图1.1的这棵二叉树，我们的第一习惯肯定是从根结点A开始读取，然后再去看A的左孩子B，看完B后再看A的右孩子C。这里我们定下一个读取的顺序：先根结点，再左孩子，最后右孩子。

注意，我们这里不能直接先A再B最后C，而是应该从左孩子开始一直读到底。什么意思呢？就是应该读完B再以B为根结点继续向下读B的左孩子，如果B有左孩子就继续以B的左孩子为根结点这样读。这里可能你会想到一点什么？对，就是递归！我们把一整棵二叉树从根结点开始一层层剥离，一层层递归。那么什么时候就不继续剥离了呢？就是读到空之后，比如图1.1中，我们从A读到B了，下一步应该是读B的左孩子，但是发现B没有左孩子，那么B结点的左子树这一边就结束了，开始读B的右孩子D，读到D就开始以D为根结点，读D的左孩子，D也没有左孩子，那就接着读D的右孩子，D也没有右孩子，那D这一个结点就结束了，也标志着根结点A的左半边读完了。程序开始向上返回去读A的右孩子。

这一种先访问根结点的遍历方式就是前序遍历。
用一句话来描述就是：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。（根 左 右）

对于图1.1，前序遍历的顺序应该是A-B-D-C。
同理，根据访问根结点的顺序还分为中序遍历和后序遍历，这些我们放到下一节来讲，这里我们先使用前序遍历的方式来创建一个二叉树。

我们前面说，如何让用户在键盘上输入一个他想要构建的二叉树，其实如何输入和如何读取是一模一样的，只不过一个是在遍历时读取，另一个是在遍历时键入。所以这里，我们使用前序遍历的方式创建二叉树。

为了让程序知道何时该返回空值来结束二叉树的分支的键入，我们约定用户如果在该输入这个结点的元素时键入“#”，程序就认为这个结点是个空结点。我们先将图1.1中的二叉树补齐，如图2.1：

也就是说，当程序遍历到B的左孩子时，用户输入#号，那此时程序返回一个NULL，说明B这个结点的左指针域left child是一个空指针，其他同理。
这里关键在于一个递归的思想，因为我们从根结点开始，递归开始时应该把根结点的左孩子作为新的根结点，依此类推。而递归出口则是检测到输入了“#”号。
具体请看代码如何实现：

//1.二叉树的建立（前序遍历）
bintree* tree_creat()
{
	//让用户输入：
	tree_data ch;
	int retscanf = scanf("%c", &ch);
	if ('#' == ch)
	{
		return NULL;//递归出口：检测到#就退出这个函数，返回到上一个函数中
	}

	//申请一个结点：
	bintree* t = (bintree*)malloc(sizeof(bintree));
	if (t == NULL)
	{
		return NULL;//判断申请空间是否成功
	}

	t->data = ch;//把当前数据存入结点data域

	t->left = tree_creat();//递归：让该结点的左孩子进入递归
	t->right = tree_creat();//递归：让该结点的右孩子进入递归
	
	return t;//返回整棵二叉树的根结点
}

针对上面这个代码，我们如果要键入图2.1这棵二叉树，如何键入呢？
应该是：AB#D##C##

具体的实现效果我们看文章最后的例子展示

🌳二叉树的遍历

二叉树的遍历( traversing binary tree )是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

这里有两个关键词：访问和次序。

访问其实是要根据实际的需要来确定具体做什么，比如对每个结点进行相关计算，输出打印等，它算作是一个抽象操作。在这里我们可以简单地假定就是输出结点的数据信息。
二叉树的遍历次序不同于线性结构，树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择。是访问左边还是右边呢？由于选择方式的不同，遍历的次序就完全不同了。

二叉树的遍历方式总的来说有这么四种：前序遍历、中序遍历、后序遍历、层序遍历。

🔅1.前序遍历

前序遍历我们前面介绍了，就是先访问根结点，然后访问左子树，再访问右子树。
下面举例：这个二叉树中的访问顺序是：ABDEKCF

代码实现：注意递归。

//2.先序遍历：
void preorder(bintree* t)
{
	if (t == NULL)
	{
		return;//递归出口
	}
	printf("%c ", t->data);//显示结点数据，可以根据需要改为其他对结点的操作
	preorder(t->left);//去遍历左子树，形成递归
	preorder(t->right);//去遍历右子树，形成递归
}

🔅2.中序遍历

若树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
下面举例：顺序应该是DBEKAFC

代码：

//3.中序遍历：
void inorder(bintree* t)
{
	if (NULL == t)
	{
		return;//递归出口
	}
	inorder(t->left); //去遍历左子树，形成递归
	printf("%c ", t->data);
	inorder(t->right);//去遍历右子树，形成递归
}

🔅3.后序遍历

若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。
下面举例：顺序是DKEBFCA

代码：

//4.后序遍历：
void postorder(bintree* t)
{
	if (NULL == t)
	{
		return;//递归出口
	}
	postorder(t->left);//去遍历左子树，形成递归
	postorder(t->right);//去遍历右子树，形成递归
	printf("%c ", t->data);
}

🔅4.层序遍历

若树为空，则空操作返回，否则从树的第一层， 也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
下面举例：这个很好理解，ABCDEFK

代码的实现：层序遍历的代码不如上面那么简单。我们访问完第一层也就是根结点A后，要访问第二层，也就是根结点的左孩子B和右孩子C，此时我们直接通过A的左右两个指针域就可以定位到B和C了。但是先访问B后，我们知道B还有用，因为我们访问完C后还要去访问B的孩子。那么在之前访问完B后应该找个东西把B的地址存下来。而且我们发现，在第二层先访问的B，那么在第三层先访问的一定是B的孩子，所以存放B的这个东西还应该满足先进先出。这里大家就明白了，我们是要用到队列的。

那么如何使用这个队列来满足层序遍历的要求呢？我们说有以下的步骤：

1. 先访问根结点A，然后让A入队。根结点访问完毕。

访问：A
队列：A

2. 开始访问第二层，让A出队来查看A的左右子树情况：

访问：A
队列：A

3. 先判断左子树：A存在左子树B，所以访问B，并让B入队。再判断右子树：A存在右子树C，所以访问C，并让C入队。第二层访问完毕。

访问：ABC
队列：ABC

4. 开始访问第三层，让队列出队B来查看B的左右子树情况。和上面相同步骤，B存在左右子树，所以访问D、E并依次让他俩入队。

访问：ABCDE
队列：ABCDE

5. 让C出队，观察C的左右子树情况。C只有左子树F，访问F后让F入队。第三层访问完毕。

访问：ABCDEF
队列：ABCDEF

6. D出队，观察D左右子树情况，D没有左右子树。

访问：ABCDEF
队列：ABCDEF

7. 让E出队，观察E左右子树，E只有右子树K，访问K并让K入队。

访问：ABCDEFK
队列：ABCDEFK

8. 让F出队，没有左右子树。

访问：ABCDEFK
队列：ABCDEFK

9. 让K出队，没有左右子树。此时队列空了。也全部都访问完毕。退出函数。

访问：ABCDEFK
队列：ABCDEFK

观察上面的步骤，我们发现，每判断一次某个结点的左右子树就要有出队到入队这个循环操作。所以从根结点开始，我们循环判断每一个结点，先让结点出队，再用两个if语句判断左右子树，如果有左右子树就访问后让子树结点入队并出队下一个结点，没有左右子树就直接出队下一个。这是一个循环，循环的终止条件就是队列为空的时候。

代码：

//5.层序遍历：
void layerorder(bintree* t)
{
	if (NULL == t)
	{
		return;
	}
	//创建队列
	linkqueue* queue = queue_init();
	if (queue == NULL)
	{
		return;
	}
	//访问根结点，并让根结点入队
	printf("%c ", t->data);
	queue_enter(queue, t);

	//开始循环：
	while (queue_empty(queue))
	{
		//出队一个结点：
		t = queue_delete(queue);
		//判断左右子树情况：
		if (t->left != NULL)
		{
			printf("%c ", t->left->data);
			queue_enter(queue, t->left);
		}
		if (t->right != NULL)
		{
			printf("%c ", t->right->data);
			queue_enter(queue, t->right);
		}

	}
}

注意，因为我们入队的是一个结点，因此调用我们写过的队列的.h文件时，要将队列中的数据改成二叉树结点类型：

typedef bintree* data_t;

🌳程序测试及效果

我们用遍历时举例的二叉树来测试。首先按照我们输入的字符将其补全。补全时要记住，每个结点的最后都必须补上空结点也就是#，这样程序才会认为是完全到头了。
按照我们编写的创建的函数，其中用了前序遍历，所以这个二叉树创建时输入的顺序应该是ABD##E#K##CF###

测试main函数：

#include "bintree.h"
int main()
{
	bintree* tree = tree_creat();

	printf("\n先序：");
	preorder(tree);

	printf("\n中序：");
	inorder(tree);

	printf("\n后序：");
	postorder(tree);

	printf("\n层序：");
	layerorder(tree);
	return 0;
}

我们再遍历中预测的是不同遍历分别是一下顺序：
前序：ABDEKCF
中序：DBEKAFC
后序：DKEBFCA
层序：ABCDEFK

看下效果：

可以发现，结果和我们想的一样。

创作挑战赛

新人创作奖励来咯，坚持创作打卡瓜分现金大奖