C++详解 二叉树的层序遍历(BFS）

上一节讲了二叉树的三种基本遍历方法:先序、中序、后续，C++详解 二叉树的三种遍历方式,这三种方法都是利用栈，DFS(深度优先遍历)的方法，那么我们最后来讲最后一种遍历方法——层序遍历，BFS(Breadth First Search)宽度优先遍历

1.二叉树遍历的核心问题

二叉树是二维结构。遍历二叉树，就是为了产生一个一维的线性序列，不同的遍历方法就产生不同的一维序列。访问了左结点后，如果把根结点忘了，或者把右结点忘了，那么永远都无法访问右结点。那么在访问了一个左儿子后，右儿子怎么办，或者父亲结点本身怎么办？

答:①在先序、中序、后续遍历中，我们通过根结点来访问它的左、右结点。如果不访问父亲结点，是访问不到左右儿子的，所以根结点显得尤为重要。我们把根结点放在栈中，作为联系左右儿子的纽带

②在层序遍历中，我们用队列来保存右结点，遍历过程为：从根结点出发，访问结点数据，队列中的第一个结点出队，同时把出队结点的左右结点保存到队列里面去

2.具体代码

void Level_Order_Traversal(Bintree_Node* p)
{
	if (!p)return;
	deque<Bintree_Node*>queue;
	queue.push_back(p);//根结点入队
	while (!queue.empty())//当整个队列为空的时候，遍历就完成了
	{
		Bintree_Node* temp = queue.front();//返回队列中第一个结点
		queue.pop_front();//第一个结点出队
		cout << temp->data << endl;//访问出队的结点的数据
		//出队结点的左右结点入队
		if (temp->left)
			queue.push_back(temp->left);
		if (temp->right)
			queue.push_back(temp->right);
	}
}
           

结果

遍历顺序ABCDEFG，顾名思义，一层层的