【二叉树】层序遍历

层序遍历概念&结构

层序遍历的实现

整体思路

代码实现

图示理解

BT升级

整体思路

代码实现

图示理解

应用

题目

前序&中序&后序遍历：深度优先遍历dfs

层序遍历：广度优先遍历bfs

层序遍历概念&结构

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。

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

层序遍历的实现

层序遍历用队列实现，需要把队列的代码拷贝到多文件项目里面：单链表实现【队列】_单链表队列出队-CSDN博客

整体思路

把根节点放入队列
保存根节点在tmp，打印根节点（遍历），然后把根节点的左右孩子入队列
根节点出队列
循环上诉过程（父亲出的时候就带入父亲的左右孩子）
若为NULL则不入队列
达到一层一层遍历（层序遍历）
注意

tmp保存的是树节点的地址

销毁的是队列的头节点（里面也是树节点的地址）

不会销毁树的节点

代码实现

测试代码在前面博文有：链式二叉树（1）-CSDN博客

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue pq;
	QueueInit(&pq);
	if(root)
	QueuePush(&pq, root);

	while (!QueueEmpty(&pq))
	{
		BTNode* tmp = QueueFront(&pq);//队列头的元素
		QueuePop(&pq);//出元素到队头
		printf("%d ", tmp->data);

		if(tmp->left)
		QueuePush(&pq, tmp->left);

		if(tmp->right)
		QueuePush(&pq, tmp->right);
	}
	QueueDestroy(&pq);
}

int main()
{
	BTNode* root = CreatBinaryTree();
	LevelOrder(root);
	BinaryTreeDestory(root);
	root = NULL;
	return 0;
}

图示理解

BT升级

若我们想要一层一层打印，怎样去一层一层打印？

整体思路

设置一个变量LeveSize记录每层的个数
每一层的数据个数，控制一层一层数据出队列
换行打印

代码实现

//BT升级换行打印
//层序遍历
void LevelOrder(BTNode* root)
{
	Queue pq;
	QueueInit(&pq);
	if (root)
		QueuePush(&pq, root);
	int levesize = 1;

	while (!QueueEmpty(&pq))
	{
		while (levesize--)
		{
			BTNode* tmp = QueueFront(&pq);//队列头的元素
			QueuePop(&pq);//出元素到队头
			printf("%d ", tmp->data);

			if (tmp->left)
				QueuePush(&pq, tmp->left);

			if (tmp->right)
				QueuePush(&pq, tmp->right);
		}
		printf("\n");
		levesize = QueueSize(&pq);//队列里面的元素个数
	}
	QueueDestroy(&pq);
}

int main()
{
	BTNode* root = CreatBinaryTree();
	LevelOrder(root);
	BinaryTreeDestory(root);
	root = NULL;
	return 0;
}

图示理解

应用

大家可以思考扫雷用递归去实现？QQ加好友的好友？

展开形式：广度优先遍历
展开形式：深度优先遍历
八度递归
层序遍历：加好友的好友（搜索算法）>>>>后面的算法篇章我们会介绍

题目

练习：请写出下面的前序/中序/后序/层序遍历

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为（）
A E
B F
C G
D H
3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde
4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF

答案：AADA