这篇文章是为了帮助一些
像我这样的菜鸟
找到简单的题解
问题描述: 题目描述输入一串二叉树，对其从根结点开始进行 BFS，输出 BFS 序。
输入格式第一行为二叉树的节点数n (1≤n≤26)。
后面 n 行，每一个字母为节点，后两个字母分别为其左右儿子。
空节点用 * 表示。
说明：
- 不保证第一个节点是根结点
- 不保证 n 个结点的编号就是前 n 个小写字母
输出共 n 行，每行一个字母，为二叉树的 BFS 序。
样例输入6 abc bdi cj* d** i** j**样例输出
a b c d i j问题解析:
这道题需要用到BFS(广度优先搜索)和二叉树
广度优先搜索介绍:
广度优先搜索（也称宽度优先搜索，缩写BFS）
是连通图的一种遍历策略。因为它的思想是从一个顶点开始，辐射状地优先遍历其周围较广的区域，因此得名。
一般可以用它做走迷宫，从起点开始，找出到终点的最短路程，很多最短路径算法就是基于广度优先的思想成立的。
当然这是迷宫问题
二叉树也可以BFS
BFS:相关资料
重点：BFS需要使用队列
二叉树介绍:关于二叉树需要讲的太多了
我找到了相关资料
二叉树:相关资料
本题直接创建二叉树
再BFS(同时输出BFS的入队信息)
题目代码:第一部写变量
本题变量非常多有二叉树、队列、一些输入输出的变量
struct node
{
char z,data,left,right;//分别表示父节点 自身 左孩子 右孩子
}a[10000001];//也可以开小点
queue q;//BFS队列
int sum;//输入次数
char f,x,b,c,root;//各种变量
然后写BFS部分
void bfs(char r)//树的根节点题目说不保证第一个输入的为根
{
q.push(r);//入队
while(!q.empty())//判断是否为空
{
char n=q.front();//定义临时变量
cout<
接下来是主函数和寻找树的根部分
int main()
{
cin>>sum;//输入个数
for(int i=1;i<=sum;i++)
{
cin>>x;//输入当前节点
a[x].data=x;//当前节点存储
cin>>a[x].left;//读入左孩子
cin>>a[x].right;//读入右孩子
if(a[x].left!='*') a[a[x].left].z=x;//把左孩子的父亲设为当前节点X
if(a[x].right!='*') a[a[x].right].z=x;//把右孩子的父亲设为当前节点X
}
root=x;//树的根存储为最后一个孩子
while(a[root].z!=' ')//判断是否有父亲
{
root=a[root].z;//查找父亲的父亲
}
bfs(root);//bfs根
return 0;
}
完整代码:
#include
using namespace std;
struct node
{
char z,data,left,right;//分别表示父节点 自身 左孩子 右孩子
}a[10000001];//也可以开小点
queue q;//BFS队列
int sum;//输入次数
char f,x,b,c,root;//各种变量
void bfs(char r)//树的根节点题目说不保证第一个输入的为根
{
q.push(r);//入队
while(!q.empty())//判断是否为空
{
char n=q.front();//定义临时变量
cout<>sum;//输入个数
for(int i=1;i<=sum;i++)
{
cin>>x;//输入当前节点
a[x].data=x;//当前节点存储
cin>>a[x].left;//读入左孩子
cin>>a[x].right;//读入右孩子
if(a[x].left!='*') a[a[x].left].z=x;//把左孩子的父亲设为当前节点X
if(a[x].right!='*') a[a[x].right].z=x;//把右孩子的父亲设为当前节点X
}
root=x;//树的根存储为最后一个孩子
while(a[root].z!=' ')//判断是否有父亲
{
root=a[root].z;//查找父亲的父亲
}
bfs(root);//bfs根
return 0;
}
题目测评:
样例通过
成功AC 
