uva122Treea on the leval（二叉树遍历）

题目链接：
lrj--p150。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #include<queue>
 5 using namespace std;
 6 vector<int> ans;
 7 bool failed;
 8 struct node
 9 {
10     bool hav;
11     int v;
12     node *l,*r;
13     node():hav(false),l(NULL),r(NULL){}
14 };
15 node *root;  //二叉树的根节点
16 char s[258];
17 
18 node * newnode()
19 {
20     return new node();
21 }
22 
23 void addnode(int v,char*s)
24 {
25     int n=strlen(s);
26     node*u=root;
27     for(int i=0;i<n;i++)
28         if(s[i]=='L') {
29         if(u->l==NULL)  u->l=newnode(); //节点不存在，建立新节点
30         u=u->l;
31         }
32         else if(s[i]=='R'){
33             if(u->r==NULL) u->r=newnode();
34             u=u->r;
35         }
36     if(u->hav) failed=true;
37     u->v=v;
38     u->hav=true;
39 }
40 bool readinput()
41 {
42     root=newnode(); //创建根节点
43     failed=false;
44     for(;;){
45         if(scanf("%s",s)!=1) return failed;
46         if(strcmp(s,"()")==0) break;
47         int v;
48         sscanf(&s[1],"%d",&v); //读入节点值
49         addnode(v,strchr(s,',')+1); //找到逗号后面的位置，创建节点
50     }
51     return 1;
52 }
53 
54 
55 bool bfs(vector<int> &ans)
56 {
57     queue<node*> q;
58     ans.clear();
59     q.push(root);
60     while(!q.empty())
61     {
62         node*u=q.front();
63         q.pop();
64         if(!u->hav) return 0;
65         ans.push_back(u->v);
66         if(u->l!=NULL) q.push(u->l);
67         if(u->r!=NULL) q.push(u->r);
68     }
69     return 1;
70 }
71 int main()
72 {
73     while(readinput())
74     {
75         if(failed||!bfs(ans))  puts("not complete");
76         else
77             {
78             printf("%d",ans[0]);
79             for(int i=1;i<ans.size();i++)
80                 printf(" %d",ans[i]);
81             printf("
");
82             }
83     }
84 }