二叉树层次遍历。

题目：
http://acm.zju.edu.cn/onlinejudge/showRuns.do?contestId=1
  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<vector>
  5 #include<queue>
  6 using namespace std;
  7 
  8 const int maxn = 256 + 110;
  9 
 10 struct Node{
 11     bool have_value;
 12     int v;
 13     Node* left, *right;
 14     Node():have_value(false), left(NULL), right(NULL){}
 15 };
 16 
 17 Node* root;
 18 
 19 Node* newnode() 
 20 {
 21     return new Node();
 22 }
 23 
 24 bool failed;
 25 void addnode(int v, char* s)
 26 {
 27     int n = strlen(s);
 28     Node* u = root;
 29     for(int i=0; i<n; i++)
 30     if(s[i]=='L')
 31     {
 32         if(u->left==NULL) u->left = newnode();
 33         u=u->left;
 34     }
 35     else if (s[i]=='R')
 36     {
 37         if(u->right==NULL) u->right = newnode();
 38         u= u->right;
 39     }
 40     if(u->have_value) failed = true;
 41     u->v=v;
 42     u->have_value = true;
 43 }
 44 
 45 void remove_tree(Node* u)
 46 {
 47     if(u==NULL) return;
 48     remove_tree(u->left);
 49     remove_tree(u->right);
 50     delete u;
 51 }
 52 
 53 char s[maxn];
 54 bool read_input(){
 55     failed = false;
 56     remove_tree(root);
 57     root = newnode();
 58     for(;;)
 59     {
 60         if(scanf("%s", s)!=1) return false;
 61         if(!strcmp(s, "()")) break;
 62         int v;
 63         sscanf(&s[1], "%d", &v);
 64         addnode(v, strchr(s, ',')+1);
 65     }
 66     return true;
 67 }
 68 
 69 bool bfs(vector<int>& ans)
 70 {
 71     queue<Node*> q;
 72     ans.clear();
 73     q.push(root);
 74     while(!q.empty())
 75     {
 76         Node* u = q.front(); q.pop();
 77         if(!u->have_value) return false;
 78         ans.push_back(u->v);
 79         if(u->left!=NULL) q.push(u->left);
 80         if(u->right!=NULL) q.push(u->right);
 81     }
 82     return true;
 83 }
 84 
 85 int main()
 86 {
 87     vector<int> ans;
 88     while(read_input())
 89     {
 90         if(!bfs(ans)) failed = 1;
 91         if(failed) printf("not complete
");
 92         else
 93         {
 94             for(int i=0; i<ans.size(); i++)
 95             {
 96                 if(i!=0) printf(" ");
 97                 printf("%d", ans[i]);
 98             }
 99             printf("
");
100         }
101     }
102     return 0;
103 }
View Code