比赛 |
20160407树结构练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
树的层次遍历 |
最终得分 |
100 |
用户昵称 |
ミント |
运行时间 |
0.008 s |
代码语言 |
C++ |
内存使用 |
0.29 MiB |
提交时间 |
2016-04-07 18:56:18 |
显示代码纯文本
#include <fstream>
//#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <sstream>
using namespace std;
ifstream cin("vlevel.in");
ofstream cout("vlevel.out");
//FILE *fin = fopen("vlevel.in", "r");
//FILE *fout = fopen("vlevel.out", "w");
//#define Root 1
//#define Left 0
//#define Right 1
#ifdef Cogs
freopen("vlevel.in", "r", stdin);
freopen("vlevel.out", "w", stdout);
#endif
const int Maxn = 256 + 30;
const int Maxm = 2 + 1;
class poi
{
public:
int Child[Maxm];
int Father;
int Name;
bool Vis;
}Tree[Maxn];
int TreePos = 1, Ans[Maxn], AnsPos = 0, Root = 1;
bool Flag = false;
void Init()
{
memset(Tree, 0, sizeof(Tree));
for(int i=0;i<Maxn;i++)
for(int j=0;j<2;j++)
Tree[i].Child[j] = -1;
for(int i=0;i<Maxn;i++)
Tree[i].Vis = false;
for(int i=0;i<Maxn;i++)
Tree[i].Name = -1;
TreePos = 1;
AnsPos = 0;
return ;
}
void AddNode(int Name, string Str)
{
int lStr = Str.length();
int Now = 1;
for(int i=0;i<lStr;i++)
{
if(Str[i]=='L')
{
if(Tree[Now].Child[0]==-1)
{
TreePos++;
Tree[Now].Child[0] = TreePos;
}
Now = Tree[Now].Child[0];
}
if(Str[i]=='R')
{
if(Tree[Now].Child[1]==-1)
{
TreePos++;
Tree[Now].Child[1] = TreePos;
}
Now = Tree[Now].Child[1];
}
}
if(Tree[Now].Vis)
Flag = true;
Tree[Now].Name = Name;
Tree[Now].Vis = true;
return ;
}
int o = 0;
int p = 0;
void Read()
{
string Str;
int V;
while(cin>>Str)
{
if(Str.compare("()")==0)
break;
sscanf(&Str[1], "%d", &V);
int FindPos = Str.find(',');
//FindRoot
if(Str.length()-FindPos-2==0)
{
Tree[1].Name = V;
Tree[1].Vis = true;
//TreePos++;
Root = 1;
//cout<<Tree[1].Name<<endl;
continue;
}
AddNode(V, Str.substr(FindPos+1, Str.length()-FindPos-2));
}
return ;
}
bool BFS()
{
queue<int> Q;
if(Root==-1)
return false;
Q.push(Root);
AnsPos++;
Ans[AnsPos] = Tree[Root].Name;
while(!Q.empty())
{
int Now = Q.front();
Q.pop();
if(!Tree[Now].Vis)
return false;
AnsPos++;
Ans[AnsPos] = Tree[Now].Name;
for(int i=0;i<=1;i++)
if(Tree[Now].Child[i]!=-1)
Q.push(Tree[Now].Child[i]);
}
return true;
}
void Write()
{
for(int i=2;i<=TreePos+1;i++)
cout<<Ans[i]<<' ';
cout<<endl;
return ;
}
void Debug()
{
for(int i=1;i<=TreePos-1;i++)
cout<<Tree[i].Name<<": "<<Tree[Tree[i].Child[0]].Name<<' '<<Tree[Tree[i].Child[1]].Name<<endl;
return ;
}
void Work()
{
while(!cin.eof())
{
Init();
Flag = false;
Root = -1;
Read();
//Debug();
//cout<<o++<<endl;
if(cin.eof())
break;
if(Flag)
{
//cout<<"1"<<' ';
cout<<"not complete"<<endl;
continue;
}
if(!BFS())
{
//cout<<"2"<<' ';
cout<<"not complete"<<endl;
continue;
}
Write();
}
return ;
}
int main()
{
Init();
//Read();
Work();
//Write();
//fin.close();
//fout.close();
//fclose(fin);
//fclose(fout);
return 0;
}