目录
- 具体实现的代码
- 1.树节点定义:
- 2.层序遍历代码:
- 实现区分不同层的节点
- 方法1:使用一个队列
- 方法2:使用两个队列
- 完整的测试代码及测试结果
二叉树的层序遍历就是从根节点开始,一层一层的显示节点数据,每一层都是从左往右。如下图所示,层序遍历的结构就为:‘*’->‘-’->‘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;
}
打印的结果
以上就是层序遍历的介绍。如果有疑问,欢迎评论区下方留言;本人水平有限 ,如有错误,也欢迎在评论区下方批评指正。若是喜欢本文,就帮忙点赞吧!