Trees on the level 树的层次遍历 UVA 122(BFS)

约定不等于承诺〃 2024-02-17 18:50 21阅读 0赞

1.  \#include<cstdio>
2.  \#include<vector>
3.  \#include<queue>
4.  \#include<cstring>
5.  using namespace std;
6.  const int maxn=260;
7.  struct node\{ 
8.   bool have\_value; //判断是否被付了值
9.   int value; //结点值
10.  node\*left,\*right; //左右子结点
11.  node():have\_value(false),left(NULL),right(NULL)\{\} //构造函数
12. \};
13. char s\[maxn\]; //输入字符串 
14. int flag=0; //判断是否多次赋值，两次以上值为1
15. vector<int> vec1; //用于储存将输出的值
16. node\*root; //根结点
17. node\* newnode()\{ //此函数通过new 运算符申请内存生成新的node结构体并以指针形式返回
18.  return new node();
19. \}
20. void addnode(int value,char\* s)\{ //构建树，添加结点
21.  int len=strlen(s);
22.  node\*u= root;
23.  for(int i=0;i<len;i++)
24.  if(s\[i\]=='L')\{ 
25.  if(u->left == NULL )u->left=newnode(); //结点不存在，建立新结点
26.  u=u->left; //往左走
27.  \}
28.  else if(s\[i\]=='R')\{ 
29.  if(u->right == NULL)u->right=newnode();
30.  u=u->right;
31.  \}
32.  if(u->have\_value)flag=1; //已经被付过值，表明输入有误
33.  u->value=value; 
34.  u->have\_value=true; //标记此结点已经被负过值
35. \}
36. bool read()\{ 
37.  flag=0;
38.  root = newnode();
39.  while(true)\{ 
40.  if(scanf("%s",s)!=1)return false; //如果读到文件结束符，返回假
41.  if(!strcmp(s,"()"))break;
42.  int value;
43.  sscanf(&s\[1\],"%d",&value); //此函数从字符串中读取指定值，用于类似于scanf();
44.  addnode(value,strchr(s,',')+1); //strchr位于<cstring>头文件下，返回指定字符的地址
45.  \}
46.  return true;
47. \}
48. bool bfs(vector<int> & vec)\{ 
49.  queue<node \*>q;
50.  vec.clear(); 
51.  q.push(root); //初始时只有一个根结点
52.  while(!q.empty())\{ 
53.  node \*u= q.front();q.pop();
54.  if(!u->have\_value)return false; //如果为假，表明有结点未被赋值，输入有错
55.  vec.push\_back(u->value); //将结点值放入到vector容器中，等待输出
56.  if(u->left!=NULL)q.push(u->left); //如果左右子结点存在，则放入到队列中
57.  if(u->right !=NULL)q.push(u->right);
58.  \}
59.  return true;
60. \}
61. int main()\{ 
62.  while(read())\{ 
63.  bool flag1=bfs(vec1); //flag1用于判断根结点是否存在值，不存在为假
64.  if(flag || !flag1)printf("not complete");
65.  else \{ 
66.  printf("%d",vec1\[0\]);
67.  for(int i=1;i<vec1.size();i++)
68.  printf(" %d",vec1\[i\]);
69.  \}
70.  printf("\\n");
71.  \}
72.  return 0;
73. \}