二叉树的层序遍历就是从根节点开始，一层一层的显示节点数据，每一层都是从左往右。如下图所示，层序遍历的结构就为：‘*’->‘-’->‘C’->‘+’->‘B’->‘E’->‘F’。

要想实现层序遍历，可以使用队列的数据结构。借用其先进先出的特点，每当访问到一个节点时，就将节点的数据打印并把左右子节点放入队列中。过程如下图

具体实现的代码

1.树节点定义：

class TreeNode
{
public:
	char data;
	TreeNode *leftChild;
	TreeNode *rightChild;

	TreeNode();
	TreeNode(char _data) :data(_data), leftChild(nullptr), rightChild(nullptr){}
	TreeNode(char _data, TreeNode* _leftChild, TreeNode* _rightChild) 
		:data(_data), leftChild(_leftChild), rightChild(_rightChild){}
};

2.层序遍历代码：

void levelOrder(TreeNode* node)
{
	std::queue<TreeNode*> que;
	TreeNode* current = node;

	if (current != nullptr)
		que.push(current);

	while (!que.empty()){
		current = que.front();
		que.pop();

		std::cout << current->data;
		if (current->leftChild) que.push(current->leftChild);
		if (current->rightChild) que.push(current->rightChild);
	}
	std::cout << std::endl;
}

写到这里，我们工作基本完成，但是为了以后方便处理每个节点的数据，我们需要返回所有节点的数据。可以使用vector向量，将每个节点的数据放入vector中，然后返回这个vector。修改后的代码如下：

vector<char> levelOrderRetVect(TreeNode* node)
{
	std::queue<TreeNode*> que;
	TreeNode* current = node;
	vector<char> vec;

	if (current != nullptr)
		que.push(current);

	while (!que.empty()){
		current = que.front();
		que.pop();

		vec.push_back(current->data);
		if (current->leftChild) que.push(current->leftChild);
		if (current->rightChild) que.push(current->rightChild);
	}

	return vec;
}

实现区分不同层的节点

还有一个问题需要处理，那就是无法区分层与层之间的节点。下面介绍两种实现区分层与层之间节点的方法。

方法1：使用一个队列

在while循环之前，我们让根节点入队。
while循环开始后，队列中此时只有一个元素（size=1），它代表了树的第一层的节点；
第一次while循环结束，开始第二次while循环，队列中此时有两个元素（size=2），它代表了树的第二层的所有节点，for的作用是只将第二层的节点进行数据处理（vectmp.push_back(current->data)）；
第二次while循环结束，开始第三次while循环……
依次类推下去。
代码如下，其中黄底色是相对上面代码改动的部分。

vector<vector<char>> levelOrderRetVect(TreeNode* node)
{
	std::queue<TreeNode*> que;
	TreeNode* current = node;
	vector<vector<char>> vec;

	if (current != nullptr)
		que.push(current);

	while (!que.empty()){

		int size = que.size();//确定一层的节点个数
		vector<char> vectmp;
		for (int i = 0; i < size; i++){//遍历一层的节点，并将子节点入栈
			current = que.front();
			que.pop();

			if (current->leftChild) que.push(current->leftChild);
			if (current->rightChild) que.push(current->rightChild);

			vectmp.push_back(current->data);//将一层的节点放在一个vector中
		}
		vec.push_back(vectmp);//将包含一层中所有节点的vector放在一个vector中
	}
	return vec;
}

方法2：使用两个队列

利用两个队列，一个用于子节点入队，一个用于循环父节点层

vector<vector<char>> levelOrderRetVect(TreeNode* node)
{
	std::queue<TreeNode*> queFather, queSon;
	TreeNode* current = node;
	vector<vector<char>> vec;//定义一个vector

	if (current != nullptr)
		queSon.push(current);
	while (!queSon.empty()){

		//1.将儿子队列变为父队列
		queFather = queSon;//将儿子队列赋值给父亲队列
		while (!queSon.empty())
			queSon.pop();//清空儿子队列

		//2.循环一层的节点
		vector<char> vectmp;//定义一个vector，保存一层的数据
		while (!queFather.empty()){
			current = queFather.front();
			queFather.pop();

			if (current->leftChild) queSon.push(current->leftChild);//将当前层的所有子节点放入子队列中
			if (current->rightChild) queSon.push(current->rightChild);

			vectmp.push_back(current->data);
		}
		vec.push_back(vectmp);
	}
	return vec;
}

完整的测试代码及测试结果

注：生成的二叉树如文章开头的图

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

class TreeNode
{
public:
	char data;
	TreeNode *leftChild;
	TreeNode *rightChild;

	TreeNode();
	TreeNode(char _data) :data(_data), leftChild(nullptr), rightChild(nullptr){}
	TreeNode(char _data, TreeNode* _leftChild, TreeNode* _rightChild) 
		:data(_data), leftChild(_leftChild), rightChild(_rightChild){}
};

void PrintsVector(vector<vector<char>> _vect)
{
	vector<vector<char> > curVect = _vect;
	for (int i = 0; i < curVect.size(); i++){
		for (int j = 0; j < curVect[i].size(); j++){
			std::cout << "‘" << curVect[i][j] << "’";
		}
		std::cout << std::endl;
	}
	std::cout << std::endl;
}

/*层序遍历：*/
void levelOrder(TreeNode* node)
{
	std::queue<TreeNode*> que;
	TreeNode* current = node;

	if (current != nullptr)
		que.push(current);

	while (!que.empty()){
		current = que.front();
		que.pop();

		std::cout << current->data;
		if (current->leftChild) que.push(current->leftChild);
		if (current->rightChild) que.push(current->rightChild);
	}
	std::cout << std::endl;
}
/*返回vector向量的层序遍历：*/
vector<vector<char>> levelOrderRetVect(TreeNode* node)
{
	std::queue<TreeNode*> que;
	TreeNode* current = node;
	vector<vector<char>> vec;

	if (current != nullptr)
		que.push(current);

	while (!que.empty()){

		int size = que.size();//确定一层的节点个数
		vector<char> vectmp;
		for (int i = 0; i < size; i++){//遍历一层的节点，并将子节点入栈
			current = que.front();
			que.pop();

			if (current->leftChild) que.push(current->leftChild);
			if (current->rightChild) que.push(current->rightChild);

			vectmp.push_back(current->data);//将一层的节点放在一个vector中
		}
		vec.push_back(vectmp);//将包含一层中所有节点的vector放在vector中
	}
	return vec;
}
int main()
{
	TreeNode node1('*'), node2('-'), node3('+'), node4('B'), node5('C'), node6('F'), node7('E');
	node1.leftChild = &node2;
	node1.rightChild = &node5;

	node2.leftChild = &node3;
	node2.rightChild = &node4;

	node4.rightChild = &node6;

	node5.rightChild = &node7;

	std::cout << "层序遍历：";
	levelOrder(&node1);
	std::cout << "返回vector的层序遍历：" << endl;
	PrintsVector(levelOrderRetVect(&node1));

	system("pause");
	return 0;
}

打印的结果

以上就是层序遍历的介绍。如果有疑问，欢迎评论区下方留言；本人水平有限 ，如有错误，也欢迎在评论区下方批评指正。若是喜欢本文，就帮忙点赞吧！