Trees on the level UVA – 122
解题思路：
首先要解决读数据问题，根据题意，当输入为“()”时，结束该组数据读入，当没有字符串时，整个输入结束。因此可以专门编写一个readin()函数，类型设置为bool型，遇到第一种情况时返回true，遇到第二种情况返回false，主程序中只要发现readin返回false时就break，结束整个大循环。
接下来要建立二叉树，首先为二叉树编写一个结构体，然后根据字符串的输入情况来建树，如果是‘L’就往左走，走不动时建一颗新树，同样的方法处理右子树，最后读入结点值。由于输入可能有误，因此用一个全局变量failed来记录是否有输入错误的情况出现，如果在建树过程中发现该结点已经被赋过值，那么全局变量failed变为true。
最后开始BFS找结点值，此时可能出现有结点没有结点值的情况，因此要把bfs定义为bool型，只要出现这种非法情况，返回false。最后便不难根据情况进行输出了。
sscanf() – 从一个字符串中读进与指定格式相符的数据.
函数原型:
Int sscanf( string str, string fmt, mixed var1, mixed var2 … );
int scanf( const char *format [,argument]… );
说明：
sscanf与scanf类似，都是用于输入的，只是后者以屏幕(stdin)为输入源，前者以固定字符串为输入源。
其中的format可以是一个或多个 {%[*] [width] [{h | l | I64 | L}]type | ‘ ‘ | ‘/t’ | ‘/n’ | 非%符号}
注：
1、 * 亦可用于格式中, (即 %*d 和 %*s) 加了星号 (*) 表示跳过此数据不读入. (也就是不把此数据读入参数中)
2、{a|b|c}表示a,b,c中选一，[d],表示可以有d也可以没有d。
3、width表示读取宽度。
4、{h | l | I64 | L}:参数的size,通常h表示单字节size，I表示2字节 size,L表示4字节size(double例外),l64表示8字节size。
5、type :这就很多了，就是%s,%d之类。
6、特别的：%*[width] [{h | l | I64 | L}]type 表示满足该条件的被过滤掉，不会向目标参数中写入值
支持集合操作：
%[a-z] 表示匹配a到z中任意字符，贪婪性(尽可能多的匹配)
%[aB’] 匹配a、B、’中一员，贪婪性
%[^a] 匹配非a的任意字符，贪婪性
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std; const int maxn = ;
vector<int> ans;
bool failed;
class Node{
public:
bool create;//表示该结点是否已经建立
int v;//结点值
Node *left,*right;
Node():create(false),left(NULL),right(NULL){}//初始化
}*root;//根节点
char a[maxn];//保存读入的节点 void create_tree(int v,char *tr)
{
int len = strlen(tr);
Node *temp = root;
if(len == )
{
temp->v = v;
temp->create = true;
return;
}
for(int i=;i<len-;i++)///注意最后一个是')'
{
if(tr[i] == 'L')///向左子树
{
if(temp->left == NULL)
{
temp->left = new Node;
}
temp = temp->left;
}
else{
if(temp->right == NULL)
temp->right = new Node;
temp = temp->right;
}
}
if(temp->create == true) failed = true;///已经赋值，说明输入有误
temp->v = v;
temp->create = true;
} bool read_input()
{
failed = false;
root = new Node;///创建根节点
for(;;)
{
if(scanf("%s",a) != ) return false;///整个输入结束
if(!strcmp(a,"()")) break;///读到结束标志，退出循环
int v;
sscanf(&a[],"%d",&v);
create_tree(v,strchr(a,',')+);
}
return true;
}
int print_tree()
{
queue<Node*> q;
ans.clear();///清空 vector<int> ans;
q.push(root);///初始时只有一个根节点
while(!q.empty())
{
Node *temp = q.front();q.pop();
if(temp->create == false)///没有被建立的结点
return ;
ans.push_back(temp->v);
if(temp->left != NULL) q.push(temp->left);
if(temp->right != NULL) q.push(temp->right);
}
return ;
} int main()
{
while(read_input())//有输入则建树
{
///开始遍历树，层次输出
int temp = print_tree();
if(temp == || failed)
cout<<"not complete"<<endl;
else{
int len = ans.size();
for(int i=;i<len;i++)
{
cout<<ans[i];
if(i == len-) cout<<endl;
else cout<<" ";
}
}
}
return ;
}
