比赛 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;
}