哈喽大家好，这里是蒟蒻hanyiyang的博文，今天，我来给大家，介绍一个关于图的算法，希望能帮助到大家！！！

层次遍历

大家来看一看上面这个图，为什么要说这是层次遍历呢，因为，这种遍历方式是一层一层进行的：
第一层：F
第二层：CE
第三层：ADHG
第四层：BM
这个就是层次遍历的大致顺序
那么算法是怎样的呢？？？

1. 先将根节点入队
2. 只要队列不为空，只要队首元素有左儿子且左儿子没有被访问过，就将左儿子入队，同理，只要队首元素有右儿子且右儿子没有被访问过，就将右儿子入队。
3. 将算法第2条执行完了以后，将队首元素弹出并输出。

这就是大致代码的实现

我们再来将上面的图根据算法再执行一遍
1.先将根节点F入队

2.将F的左右儿子CE入队

3.将F出队并输出

输出：F
4.将C的左右儿子AD入队，并将C出队输出

输出：F C
5.将E的左右儿子HG入队，并将E出队输出

输出：F C E
6.因A为叶子节点，则直接出队输出

输出：F C E A
7.将D的左儿子B入队，并将D出队输出

输出：F C E A D
8.因为H是叶子节点，所以直接将此出队输出

输出：F C E A D H
9.将G的左儿子入队，并将G出队输出

输出：F C E A D H G
10.因为B M都为叶子节点，所以直接出队输出，此时队列为空

输出：F C E A D H G B M

以上是层次遍历的大致过程，具体代码实现如下

struct node
{int data;int lson,rson;
}tree[MAXN];
void Leveltraversal(int root)
{queue<int>level;level.push(root);while(!level.empty()){cout<<tree[level.front()].data<<" ";if(tree[level.front()].lson!=0)level.push(tree[level.front()].lson);if(tree[level.front()].rson!=0)level.push(tree[level.front()].rson);level.pop();}return;
}

现在来道例题练练手
BST 遍历( bst.cpp )
【问题描述】
根据输入的n 个节点的值建立二叉搜索树，输出其层次遍历。
【输入说明】
第一行输入整数n
第二行输入n 个节点的值（保证每个节点的值为不同整数），两两之间用空格隔
开。
【输出说明】
输出一行，即二叉搜索树的层次遍历，两两之间用空格隔开。
【输入样例】
5
4 2 5 1 3
【输出样例】
4 2 5 1 3
【数据范围】
0<n≤1000
节点值在10^9 以内

参考代码

//hanyiyang c++ code#include <bits/stdc++.h>
#define MAXN 1001using namespace std;struct node
{long long data;long long lson,rson;
}tree[MAXN];void build_tree(int root,int now)
{if(tree[now].data<tree[root].data){if(tree[root].lson!=0)build_tree(tree[root].lson,now);else{tree[root].lson=now;return;}}else{if(tree[root].rson!=0)build_tree(tree[root].rson,now);else{tree[root].rson=now;return;}}return;
}void out_tree(int root)
{int now;queue<long long>out;out.push(root);while(!out.empty()){now=out.front();if(tree[now].lson!=0)out.push(tree[now].lson);if(tree[now].rson!=0)out.push(tree[now].rson);cout<<tree[now].data<<" ";out.pop();}return;
}int main()
{freopen("bst.in","r",stdin);freopen("bst.out","w",stdout);int n;int root;cin>>n;for(int i=0;i<=n;i++)tree[i].lson=tree[i].rson=0;for(int i=1;i<=n;i++){cin>>tree[i].data;if(i==1)root=i;elsebuild_tree(root,i);}out_tree(root);return 0;
}

这就是层次遍历的大致思想
记得关注点赞哦😄