文章目录

前言
一、开场白
二、二叉树结点的设计
三、二叉树的遍历
四、二叉树的创建
- 递归建树
- 层序非递归建树
五、结尾语

前言

《数据结构系列首页》是数据结构系列文章的首页，其中会逐步更新各种数据结构的实现，有兴趣的选手可以一看。
首页中不仅有各种数据结构的实现，还有学习数据结构必备的基础知识，如果有选手觉得自己的基础不太牢固，可以先将搞定基础知识，之后再攻克数据结构这一部分的内容。
由于我也是刚开始学习数据结构这门课程，所以如果发现文章中存在错误，希望大家可以直接指出，我将第一时间修改。
更多数据结构的实现请见《数据结构系列文章》，我会在学习完新的数据结构后不断更新其中的内容。

一、开场白

树是一种比起线性表更加复杂的存储结构，其是一种非常重要的非线性数据结构，树结构在客观世界中普遍存在，其中二叉树的运用最为广泛。本篇文章主要介绍了二叉树的链式存储结构（即二叉链表）的创建与遍历，这将为以后对二叉树的研究起到至关重要的作用。

二、二叉树结点的设计

考虑到二叉树中的每个结点最多可以指向两个结点，所以为二叉树的结点设置一个数据域和两个指针域是非常自然的想法。

typedef char TreeElemType; // 定义二叉树的元素类型为字符类型

// 定义二叉树结点
typedef struct TreeNode
{
	TreeElemType data; // 数据域
	struct TreeNode* leftchild;  // 左指针域
	struct TreeNode* rightchild; // 右指针域
}TreeNode, * TREE; // TREE 等同于 struct TreeNode *

二叉树结点结构如下图所示：
在这里插入图片描述

三、二叉树的遍历

先序遍历

先序遍历规则

若二叉树为空，则不进行遍历；否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如下图所示，先序遍历的结果为ABDGHCEIF。由遍历结果可知，先序遍历属于深度优先遍历，即优先向树的最深处探索。
在这里插入图片描述

先序遍历递归算法

void pre_order_traverse(TREE T)
{
	if (T) // T为空是递归结束的条件
	{
		putchar(T->data); // 打印根结点的数据
		pre_order_traverse(T->leftchild);  // 先序遍历左子树
		pre_order_traverse(T->rightchild); // 先序遍历右子树
	}
}

中序遍历

中序遍历规则

若二叉树为空，则不进行遍历；否则先中序遍历左子树，然后访问根结点，再中序遍历右子树。如下图所示，中序遍历的顺序为GDHBAEICF。
在这里插入图片描述
在写二叉树的中序遍历结果时，有个更加快捷的方法：从树根向下将二叉树一脚踩扁，之后按照踩扁后的树，从左至右依次写出各结点的数据即可。以上图中的树为例，踩扁之后就变成了下图：

根据结点从左到右出现的次序，想象所有的结点都在一条线上，这样写出各结点的数据后得到的便是该树的中序遍历结果，即GDHBAEICF。

中序遍历递归算法

void in_order_traverse(TREE T)
{
	if (T) // T为空是递归结束的条件
	{
		in_order_traverse(T->leftchild);  // 中序遍历左子树
		putchar(T->data); // 打印根结点的数据
		in_order_traverse(T->rightchild); // 中序遍历右子树
	}
}

中序遍历非递归算法

中序遍历非递归算法用到了链栈的部分知识，，详细内容可以参见《链栈的实现》这篇文章。

链栈结构的设计

typedef TREE StackElemType; // 定义栈的元素类型为树结点的指针

// 定义栈的结点
typedef struct StackNode
{
	StackElemType data; // 数据域
	struct StackNode* next; // 指针域
}StackNode, * STACK; // STACK 等同于 struct StackNode *

// 定义链栈结构
typedef struct LinkedStack
{
	STACK top; // 栈顶指针
	int length; // 当前栈中元素的个数
}LinkedStack;

链栈操作函数的声明

void init_stack(LinkedStack&);
void push_stack(LinkedStack&, StackElemType);
bool stack_is_empty(LinkedStack&);
bool pop_stack(LinkedStack&, StackElemType&);
void destroy_stack(LinkedStack&);

链栈操作函数

// 初始化链栈S
void init_stack(LinkedStack& S)
{
	S.top = (STACK)calloc(1, sizeof(StackNode)); // 生成头结点
	if (!S.top) // 如果S.top不存在，则分配失败并退出程序
		exit(OVERFLOW);

	S.length = 0; // 将栈当前长度置为0
}

// 将元素e压入链栈S的栈顶
void push_stack(LinkedStack& S, StackElemType e)
{
	STACK newnode = (STACK)calloc(1, sizeof(StackNode)); // 创建新结点
	if (!newnode) // 如果newnode不存在，则分配失败并退出程序
		exit(OVERFLOW);

	newnode->data = e; // 将e的值赋给新结点的数据域
	newnode->next = S.top; // 将当前栈顶结点的地址赋给新结点的指针域
	S.top = newnode; // 将新节点的地址赋给当前栈顶指定，即让栈顶指定指向新结点
	S.length++; // 栈的当前长度加1
}

// 判断链栈S是否为空
bool stack_is_empty(LinkedStack& S)
{
	if (S.length == 0) // 如果栈的当前长度为0，则栈为空
		return true;
	else
		return false;
}

// 将链栈S的栈顶元素出栈，并用e返回该元素的值
bool pop_stack(LinkedStack& S, StackElemType& e)
{
	if (stack_is_empty(S)) // 如果当前栈为空，则无法执行出栈操作
		return false;
	
	STACK p = S.top;  // 定义一个指向栈顶结点的指针p

	e = p->data; // 将栈顶结点的数据域赋给e
	S.top = p->next; // 将栈顶指针指向当前栈顶结点的下一结点
	free(p); // 释放当前栈顶结点
	p = NULL; // 将p置为空
	
	S.length--; // 栈的当前长度减1
	return true;
}

// 销毁链栈S
void destroy_stack(LinkedStack& S)
{
	STACK p = S.top; // 定义一个指向栈顶结点的指针p

	while (p) // 只要p存在，则证明仍有未释放的结点，则进入循环释放
	{
		S.top = S.top->next; // 先将栈顶指针下移至栈顶的下一个结点
		free(p); // 将当前栈顶结点释放
		p = S.top; // 将指针p指向下一结点
	}

	S.length = 0; // 将栈当前长度置为0
}

中序遍历非递归算法

void in_order_traverse_2(TREE T)
{
	LinkedStack S; // 定义栈
	TREE p = T;

	init_stack(S); // 初始化栈

	while (p || !stack_is_empty(S)) // p不存在同时栈为空是该循环结束的条件
	{
		if (p) // p不空则将p压栈并找被压栈结点的左孩子
		{
			push_stack(S, p); // 将p压栈
			p = p->leftchild; // 索引p的左孩子
		}
		else // p为空则栈顶元素出栈输出并找出栈结点的右孩子
		{
			pop_stack(S, p); // 出栈
			putchar(p->data); // 输出
			p = p->rightchild; // 索引p的右孩子
		}
	}
	// 循环执行完毕表明已遍历完成
	destroy_stack(S); // 销毁栈
}

中序遍历的非递归算法大家可以通过画整个算法的执行流程图以及单步调试的方式理解其中的原理，整体而言非常容易理解和记忆，我将整个算法总结为：存在压栈找左孩，不存在出栈找右孩，而压栈的目的是保存结点的左孩子与右孩子，如果遍历到一个节点就把该结点输出，则其左右孩子就会丢失。

后序遍历

后序遍历规则

若二叉树为空，则不进行遍历；否则先后序遍历左子树，然后后序遍历右子树，最后访问根结点。如下图所示，后序遍历的结果为GHDBIEFCA。
在这里插入图片描述

后序遍历递归算法

void post_order_traverse(TREE T)
{
	if (T) // T为空是递归结束的条件
	{
		post_order_traverse(T->leftchild);  // 后序遍历左子树
		post_order_traverse(T->rightchild); // 后序遍历右子树
		putchar(T->data); // 打印根结点的数据
	}
}

层序遍历

层序遍历规则

若二叉树为空，则不进行遍历；否则从二叉树的第一层开始，自上而下逐层遍历，在同一层中，按从左到右的顺序对每个结点依次访问。如下图所示，遍历的顺序为ABCDEFGHI。
在这里插入图片描述

层序遍历非递归算法

层序遍历非递归算法用到了链队列的部分知识，详细内容可以参见《链队列的实现》这篇文章。

链队列结构的设计

typedef TREE QueueElemType; // 定义队列的元素类型为树结点的指针

// 定义链队列结点
typedef struct QueueNode
{
	QueueElemType data; // 数据域
	struct QueueNode* next; // 指针域
}QueueNode, * QUEUE; // QUEUE 等同于 struct QueueNode *

// 定义链队列结构
typedef struct LinkedQueue
{
	QUEUE front; // 队头指针
	QUEUE rear;  // 队尾指针
}LinkedQueue;

链队列操作的函数声明

void init_queue(LinkedQueue&);
void en_queue(LinkedQueue&, QueueElemType);
bool queue_is_empty(LinkedQueue&);
bool de_queue(LinkedQueue&, QueueElemType&);
void destroy_queue(LinkedQueue&);

链队列操作函数

// 初始化链队列Q
void init_queue(LinkedQueue& Q)
{
	Q.front = (QUEUE)calloc(1, sizeof(QueueNode)); // 生成头结点
	/* 
		calloc函数与malloc的功能基本一致
		calloc函数增加了分配后的初始化功能
		例如上行代码，如果分配成功，则自动将Q.front->data置0，将Q.front->next置为NULL
		calloc分配的字节数等于第一个实参乘以第二个实参
	*/
	if (!Q.front) // 如果Q.front不存在，则分配失败并退出程序
		exit(OVERFLOW);

	Q.rear = Q.front; // 分配成功后，令Q.rear与Q.front均指向头结点
	/* 
		由于calloc函数已经将头结点的指针域置为空
		所以不需要再将头结点的指针域置为空
		即不需要写 Q.front->next = NULL; 这行代码
		这也体现出calloc函数的好处
	*/
}

// 在链队列Q中入队元素e
void en_queue(LinkedQueue& Q, QueueElemType e)
{
	QUEUE newnode = (QUEUE)calloc(1, sizeof(QueueNode)); // 生成新结点
	if (!newnode) // 如果newnode不存在，则分配失败并退出程序
		exit(OVERFLOW);

	newnode->data = e; // 将e赋给新结点的数据域
	Q.rear->next = newnode; // 将新结点赋给当前尾结点的指针域
	Q.rear = newnode; // 将新结点置为当前的尾结点
}

// 判断链队列Q是否为空
bool queue_is_empty(LinkedQueue& Q)
{
	if (Q.front == Q.rear) // 如果队头指针与队尾指针相等，则队列为空
		return true;
	else
		return false;
}

// 将链队列Q中的队头元素出队，并用e返回该元素的值
bool de_queue(LinkedQueue& Q, QueueElemType& e)
{
	if (queue_is_empty(Q)) // 如果队列为空，则无法出队
		return false;

	QUEUE p = Q.front->next; // 定义指向队头结点的指针p
	
	e = p->data; // 将队头结点的值赋给e
	Q.front->next = p->next; // 将队头结点的指针域赋给头结点的指针域，即让头结点的指针域指向队头结点的下一结点

	if (p == Q.rear) // 如果出队的元素为队尾结点
		Q.rear = Q.front; // 修改队尾指针指向头结点(此时队列变为空队列)

	free(p); // 释放队头指针对应的空间
	p = NULL; // 将队头指针置为空

	return true;
}

// 销毁链队列Q
void destroy_queue(LinkedQueue& Q)
{
	while (Q.front) // 只要Q.front存在，则进入循环
	{
		Q.rear = Q.front->next; // 此时让Q.rear指向Q.front的下一个结点，用以保存下一个结点的位置
		free(Q.front); // 释放当前结点
		Q.front = Q.rear; // Q.front指向下一结点，Q.front始终指向第一个要释放的结点
	}
}

层序遍历算法

void level_order_traverse(TREE T)
{
	LinkedQueue Q; // 定义队列
	QueueElemType p; // p用以接收出队后的队列元素

	init_queue(Q); // 初始队列
	en_queue(Q, T); // 首先将树根入队

	while (!queue_is_empty(Q)) // 队列不为空则进入循环
	{
		de_queue(Q, p); // 出队
		putchar(p->data); // 打印队头元素的值

		if (p->leftchild) // 判断出队元素是否有左孩子
			en_queue(Q, p->leftchild); // 左孩子存在则将左孩子入队
		if (p->rightchild) // 判断出队元素是否有右孩子
			en_queue(Q, p->rightchild); // 右孩子存在则将右孩子入队
	}
	// 循环执行完毕表明已遍历完成
	destroy_queue(Q); // 销毁队列
}

借助队列实现的层序遍历算法可以通过画算法的执行流程图以及单步调试的方式来理解，整体而言非常容易理解，如果有不理解的地方也欢迎大家跟我讨论。

四、二叉树的创建

二叉树的遍历研究了半天，有的人可能有点坐不住了，还没有二叉树呢我怎么遍历它？！莫要着急，接下来就来看看二叉树该如何建立。

递归建树

先来看看第一种建立二叉树的方式——递归建树。在使用递归进行创建二叉树时，首先要做的是将普通的二叉树转为扩展二叉树，那什么是扩展二叉树呢？看看下面的图片就明白了。

我们把想要创建的二叉树称为普通二叉树，也就是下图中的二叉树。
在这里插入图片描述
如果我们要建立一颗上图这样的二叉树，那我们首先要将这颗二叉树转换为下面的扩展二叉树。将每个结点的空指针引出一个虚节点，令其值为一个特定值，这个值可以自己选定，例如#，我们称经过这样处理的二叉树为原普通二叉树的拓展二叉树。
在这里插入图片描述
此时就可以采取一种遍历方式来遍历整个拓展二叉树，例如该拓展二叉树先序遍历的结果为AB#D##C##，接下来我们就要用这样一种前序遍历的结果来建立整颗二叉树。这也是为什么要先研究二叉树的遍历。让我们来看看算法：

void create_tree(TREE& T)
{
	TreeElemType c;
	scanf("%c", &c); // 输入数据

	if (c == '#') // 判断数据是否为#
		T = NULL; // 如果数据为#，则将该结点赋为空(不创建新结点)
	else
	{
		T = (TREE)calloc(1, sizeof(TreeNode)); // 创建结点
		if (!T) // 如果T不存在，则分配失败并退出程序
			exit(OVERFLOW);

		T->data = c; // 将数据放入结点的数据域
		create_tree(T->leftchild);  // 采用同样的方式递归建立左子树
		create_tree(T->rightchild); // 采用同样的方式递归建立右子树
	}	
}

运行算法并将二叉拓展树的前序遍历序列输入到黑窗口中，即可完成上面图中普通二叉树的创建。也就是说，创建一颗普通二叉树，需要先将该普通二叉树转为对应的拓展二叉树，然后将其前序遍历序列手动输入到黑窗口中，即可完成创建。

算法我们研究完了之后，还有一个问题值得思考：为什么要将一颗普通二叉树转为拓展二叉树才可以建树呢？拓展二叉树的作用到底是什么呢？其作用是以一个遍历序列唯一确定一颗二叉树，大家可以思考一下这一点。

思考得差不多了，那我们来看看第二种建树的方式。

层序非递归建树

层序建树顾名思义，就是一层一层地建，当然，用其建树的过程就要比递归稍微复杂一些，但是其过程也是很好理解的，只不过同层序遍历一样又一次用上了队列的知识，如果你对队列的知识还不是很了解，那么还是建议你搞定队列后再来研究这一算法。

void level_create_tree(TREE& T)
{
	LinkedQueue Q; // 定义队列Q
	TreeElemType c; // 定义树中元素c
	QUEUE current; // 定义指向当前队列中待插入结点的指针current
	QueueElemType e; // 定义接收出队后的队头元素e，无实际作用，只是为了满足出队函数实参的要求

	init_queue(Q); // 初始化队列Q
	current = Q.front; // current最先指向队列的头结点，无实际作用，该赋值语句只是为了让current暂时有指向

	while (scanf("%c", &c) != EOF) // 循环输入
	{
		if (c == '\n') // 循环结束的条件
			break;

		TREE newtreenode = (TREE)calloc(1, sizeof(TreeNode)); // 创建树的新结点
		if (!newtreenode) // 如果newtreenode不存在，则分配失败并退出程序
			exit(OVERFLOW);

		newtreenode->data = c; // 将元素c放入树结点的数据域
		en_queue(Q, newtreenode); // 将树的新结点入队

		if (!T) // 第一次进入循环时，树必然为空
		{
			T = newtreenode; // 将生成的新结点赋给树根的指针
			current = Q.front->next; // current指向队头元素
			continue; // 结束第一次循环
		}

		// 从第二次循环开始
		if (!current->data->leftchild) // 当树中待插入结点的左指针域为空时
			current->data->leftchild = newtreenode; // 将新结点赋给其左指针域
		else if (!current->data->rightchild) // 当树中待插入结点的右指针域为空时
		{
			current->data->rightchild = newtreenode; // 将新结点赋给其右指针域
			// 对右指针域赋值完成后，表明树中当前待插入结点的左右指针域已满
			current = current->next; // 待插入结点的指针current指向下一个待插入结点
			de_queue(Q, e); // 将队头元素出队
		}
	}

	destroy_queue(Q); // 待树中的所有结点插入完毕后，销毁队列
}

与递归建树不同的是，层序建树不需要将普通二叉树转为对应的拓展二叉树，也不需要在输入数据的过程中输入无效的标志符(#)，层序建树的过程就显得更加直观。

算法执行的过程其实就是判断待插入结点的左右指针域是否已经插满的过程，如果没插满就接着插，如果插满了就换下一个结点。给大家留一个思考题：当所有节点都插入成功后，在不销毁队列前，队列中是否还有元素？

五、结尾语

二叉树在整个树这一章节中占有主导地位，是学习树相关知识的重中之重。
遍历是二叉树的一门学问，其四种遍历方式都需要熟练掌握。
通过二叉树的学习可以帮助我们加深对递归算法的理解，大家可以尝试一下模拟递归的实现。
大家应重点理解各算法中的细节，而不是仅仅大概明白算法的思路。
更重要的是，一定要通过程序将各算法自行实现一遍，这对数据结构的学习将大有裨益。
如果大家有不明白的地方，或者发现程序中有错误之处，欢迎大家通过评论区与我交流。

本文含有隐藏内容，请开通VIP 后查看

【数据结构】二叉树的创建和四种遍历（附带详细注释）