C语言数据结构(15)--二叉树的层序遍历代码实现

背景

在上一篇中，我们利用递归很轻易的就实现了二叉树的前序、中序、后续遍历，但是层序遍历仅仅利用递归貌似是解决不了的。

在如上图的树中，我们如何先从上至下，然后从左至右的按层次进行遍历，即A-B-C-D-E-F-G这样的顺序呢。

思路

每次在访问下一层次节点之前，应该将上一级节点输出，而上一级节点无疑从层次上先于下一级，我们联想到先进先出的队列模型，我们可以利用一个队列，在递归访问二叉树下一层次之前，将本层次的节点放入队列，这样就实现了输出时，也是按层次先后输出的。

代码实现

#include<stdio.h>
#define QUEUE_LENGTH 100 //队列最大元素个数
/*
* 二叉树的层序遍历演示DEMO
* 作者：熊猫大大
* 时间：2019-12-15
*/

// 队列结构体
struct Queue
{
	char element[QUEUE_LENGTH];//队列元素
	int head;//头部位置
	int tail;//尾部位置
};

//入队
int queueIn(struct Queue* p, char num)
{
	//满了
	if (p->tail>QUEUE_LENGTH - 1)
	{
		return 0;//入队失败
	}
	p->element[p->tail] = num;
	p->tail++;
	return 1;
}
//出队
int queueOut(struct Queue* p, char *result)
{
	if (p->head == p->tail)
		return 0;//出队失败
	*result = p->element[p->head++];
	return 1;
}
//定义一个全局的队列，用来层序遍历二叉树
struct Queue queue;

//二叉树结构体
typedef struct {
	char data;//数据区域(为了保存ABCD，直接用char当做数据域，便于和文章中的插图对应，稳！)
	struct BinaryTreeNode* left;//左子节点
	struct BinaryTreeNode* right;//右子节点
}BinaryTreeNode;

//为树的当前节点添加左子节点
int addLeftChild(BinaryTreeNode* curNode, char leftData)
{
	//分配新节点
	BinaryTreeNode* leftNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
	//为新节点挂载数据
	leftNode->data = leftData;
	//新节点暂时无子节点
	leftNode->left = NULL;
	leftNode->right = NULL;
	//将新节点挂到当前节点下
	curNode->left = leftNode;
	return 1;
}

//为树的当前节点添加右子节点
int addRightChild(BinaryTreeNode* curNode, char rightData)
{
	//分配新节点
	BinaryTreeNode* rightNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
	//为新节点挂载数据
	rightNode->data = rightData;
	//新节点暂时无子节点
	rightNode->left = NULL;
	rightNode->right = NULL;
	//将新节点挂到当前节点下
	curNode->right = rightNode;
	return 1;
}

// 层序遍历
void leverOrder(BinaryTreeNode *node)
{
	if (node == NULL) {
		return;
	}
	//输出队列中保存的信息
	char result;
	while (queueOut(&queue, &result) == 1) {
		printf("%c",result);
	}
	//将子节点先加入队列，后续再遍历更深的层次
	if (node->left != NULL) {
		BinaryTreeNode *temp = node->left;
		queueIn(&queue, temp->data);
	}
	if (node->right != NULL) {
		BinaryTreeNode *temp = node->right;
		queueIn(&queue, temp->data);
	}
	leverOrder(node->left);
	leverOrder(node->right);
}

//----------------------------------------------------------------------------------------------------测试入口区域
int main()
{
	//初始化队列
	queue.head = 0;
	queue.tail = 0;
	//设定根节点
	BinaryTreeNode root;
	//根节点A
	root.data = 'A';
	addLeftChild(&root, 'B');
	addRightChild(&root, 'C');
	//为B节点增加子节点
	addLeftChild(root.left, 'D');
	addRightChild(root.left, 'E');
	//为C节点增加子节点
	addLeftChild(root.right, 'F');
	addRightChild(root.right, 'G');
	printf("\n层序遍历：");
	//根节点第一个进入队列
	queueIn(&queue, root.data);
	leverOrder(&root);
	return 1;
}