UVa 122 Trees on the level

　　《算法竞赛入门经典》6.3.2的题，关于构建二叉树和层次遍历的问题。

　　书中的代码定义的节点结构用了一个have_value标记判断是否已有值，因为节点的值都是正整数，可以通过初始化为0来判断是否该节点已有值，另外，ans数组的n应在每次调用bfs函数时进行初始化。

　　第一次提交的时候PE了，原来是要去掉层次遍历结果的后缀空白符，可是我并没有在题目中找到相关的要求呀...

　　代码如下：

View Code

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 
  5 const int maxn = 300;
  6 
  7 struct Node 
  8 {
  9     int value;
 10     Node * left, * right;
 11 };
 12 
 13 Node * root;
 14 
 15 Node * newnode()
 16 {
 17     Node * u = (Node *)malloc(sizeof(Node));
 18     if(u != NULL)
 19     {
 20         u->value = 0;
 21         u->left = u->right = NULL;
 22     }
 23     return u;
 24 }
 25 
 26 int failed;
 27 void addnode(int v, char * s)
 28 {
 29     int len = strlen(s);
 30     Node * u = root;
 31     for(int i = 0; i < len; i++)
 32     {
 33         if(s[i] == 'L')
 34         {
 35             if(u->left == NULL)   u->left = newnode();
 36             u = u->left;
 37         }
 38         if(s[i] == 'R')
 39         {
 40             if(u->right == NULL)   u->right = newnode();
 41             u = u->right;
 42         }
 43     }
 44     if(u->value > 0)   failed = 1;
 45     u->value = v;
 46 }
 47 
 48 void remove_tree(Node * u)
 49 {
 50     if(u == NULL)    return;
 51     remove_tree(u->left);
 52     remove_tree(u->right);
 53     free(u);
 54 }
 55 
 56 char s[maxn];
 57 
 58 int read_input()
 59 {
 60     failed = 0;
 61     remove_tree(root);
 62     root = newnode();
 63     while(1)
 64     {
 65         if(scanf("%s", s) == EOF)   return 0;
 66         if(strcmp(s, "()") == 0)   break;
 67         int v;
 68         sscanf(&s[1], "%d", &v);
 69         addnode(v, strchr(s, ',')+1);
 70     }
 71     return 1;
 72 }
 73 
 74 int n, ans[maxn];
 75 int bfs()
 76 {
 77     int front = 0, rear = 1;
 78     n = 0;
 79     Node * q[maxn];
 80     q[0] = root;
 81     while(front < rear)
 82     {
 83         Node * u = q[front++];
 84         if(!u->value)   return 0;
 85         ans[n++] = u->value;
 86         if(u->left)   q[rear++] = u->left;
 87         if(u->right)   q[rear++] = u->right;
 88     }
 89     return 1;
 90 }
 91 
 92 int main()
 93 {
 94 #ifdef LOCAL
 95     freopen("in", "r", stdin);
 96 #endif
 97     while(read_input())
 98     {
 99         if(!bfs())   failed = 1;
100         if(failed)   printf("not complete\n");
101         else 
102         {
103             for(int i = 0; i < n; i++)
104             {
105                 printf("%s", i ? " " : "");
106                 printf("%d", ans[i]);
107             }
108             printf("\n");
109         }
110     }
111     return 0;
112 }