二叉树的广度优先遍历

二叉树的广度优先遍历

层序遍历

设二叉树的根节点所在层数为第一层，层序遍历就是从二叉树的根节点出发，先访问第一层的根节点，然后从左到右访问第2层上的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

要想用代码实现队列的层序遍历我们需要借助队列：

1、先把根结点入队列，然后开始从队头出数据；

2、出队头的数据，把它的左孩子和右孩子依次从队尾入队列（NULL不入队列）；

3、重复进行操作2，直到队列为空为止。

借助队列先进先出的特性，上一层数据出队列的时候将下一层数据带入到队列中。

代码：

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);//队列初始化
	if (root != NULL)
	{
		QueuePush(&q, root);//将根结点插入
	}
	while (!QueueEmpty(&q))//如果队列不为空
	{
		//读取队头元素
		BTNode* front = QueueFront(&q);
		//删除队头元素
		QueuePop(&q);
		//打印队头元素
		printf("%d ", front->data);
		//如果左孩子不为空，插入左孩子结点
		if (front->left)
		{
			QueuePush(&q, front->left);//将左结点插入
		}
		if (front->right)
		{
			QueuePush(&q, front->right);//将右节点插入
		}
	}
	QueueDestroy(&q);//销毁队列
}

测试前中后序遍历和层序遍历：

//队列结构体的声明和定义
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;
typedef struct Queue {
	QNode* head;
	QNode* tail;
	int size;
}Queue;

//测试
int main()
{
	BTNode* root = CreatBinaryTree();
	PrevOrder(root);//输出1 2 3 4 5 6
	printf("\n");
	InOrder(root);//输出3 2 1 5 4 6
	printf("\n");
	PostOrder(root);//输出3 2 5 6 4 1
	printf("\n");
	LevelOrder(root);//输出1 2 4 3 5 6
	printf("\n");
}