1 #include<stdio.h>  2 #include<iostream>  3 #include<algorithm>  4 #include<math.h>  5 #include<string.h>  6 #include<string>  7 #include<map>  8 #include<set>  9 #include<vector> 10 #include<queue> 11 #define M(a,b) memset(a,b,sizeof(a)) 12 using namespace std; 13 typedef long long ll; 14 const int inf=0x3f3f3f3f; 15 queue<int>ans; 16 struct Binary_Tree //二叉树 17 { 18     int value; 19     Binary_Tree *lchild,*rchild; 20     Binary_Tree() 21     { 22         value=http://www.mamicode.com/0; 23         lchild=rchild=NULL; 24     } 25 }; 26 bool add(Binary_Tree *&Root,char *s,int value){ //向二叉树中加入点 27     if(Root==NULL) 28         Root=new Binary_Tree(); 29     if(*s==‘\0‘) 30     { 31         if(Root->value!=0) 32         { 33             return false; 34         } 35         Root->value=http://www.mamicode.com/value; 36         return true; 37     } 38     if(*s==‘L‘) //寻找路径 39     { 40         return add(Root->lchild,s+1,value);  41     } 42     else if(*s==‘R‘) 43     { 44         return add(Root->rchild,s+1,value); 45     } 46     return false; 47 } 48 void Delete(Binary_Tree *Root) //删除二叉树 49 { 50     if(Root==NULL) return ; 51     Delete(Root->lchild); 52     Delete(Root->rchild); 53     delete Root; 54 } 55 bool bfs(Binary_Tree *Root) //层次遍历 56 { 57     Binary_Tree *q[260]; //数组模拟队列 58     int front=0; 59     int rear=1; 60     q[0]=Root; 61     while (front<rear) 62     { 63         Binary_Tree *temp=q[front++]; 64         if(!temp->value) //没有值就返回false 65         { 66             return false; 67         } 68         ans.push(temp->value); //当前节点入ans队 69         if(temp->lchild) //左孩子入队 70         { 71             q[rear++]=temp->lchild; 72         } 73         if(temp->rchild) //右孩子入队 74         { 75             q[rear++]=temp->rchild; 76         } 77     } 78     return true; 79 } 80 int main(){ 81     Binary_Tree *Root=NULL; 82     char s[50]; 83     bool no=false; 84     while(true) 85     { 86         no=false; 87         Delete(Root); 88         Root=NULL; //二叉树初始化 89         while(true) 90         { 91             if(scanf("%s",s)==EOF) //读入 92             { 93                 return 0; 94             } 95             if(strcmp(s,"()")==0) 96             { 97                 break; 98             } 99             int val;100             char loc[10];101             strcpy(loc,"");102             sscanf(&s[1],"%d",&val);103             char *start=strchr(s,‘,‘)+1;104             sscanf(start,"%[A-Z]",&loc);105             if(!add(Root,loc,val))106             {107                 no=true;108             }109         }110         if(no)111         {112             puts("not complete");113         }114         else115         {116             if(!bfs(Root))117                 puts("not complete");118             else119             {120                 while(!ans.empty())121                 {122                     int ll=ans.front();123                     ans.pop();124                     printf("%d%c",ll,ans.empty()?‘\n‘:‘ ‘);125                 }126             }127         }128     }129     return 0;130 }131 /*132 133 (11,LL) (7,LLL) (8,R)134 (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()135 (3,L) (4,R) ()136 137 */