sponsored links

树得层次遍历@例题6-7

001 #include <cstdio>
002  #include <cstdlib>
003  #include <cstring>
004   
005  const int maxn = 300;
006   
007  struct Node
008  {
009      int value;
010      Node * left, * right;
011  };
012   
013  Node * root;
014   
015  Node * newnode()
016  {
017      Node * u = (Node *)malloc(sizeof(Node));
018      if(u != NULL)
019      {
020          u->value = 0;
021          u->left = u->right = NULL;
022      }
023      return u;
024  }
025   
026  int failed;
027  void addnode(int v, char * s)
028  {
029      int len = strlen(s);
030      Node * u = root;
031      for(int i = 0; i < len; i++)
032      {
033          if(s[i] == 'L')
034          {
035              if(u->left == NULL)   u->left = newnode();
036              u = u->left;
037          }
038          if(s[i] == 'R')
039          {
040              if(u->right == NULL)   u->right = newnode();
041              u = u->right;
042          }
043      }
044      if(u->value > 0)   failed = 1;
045      u->value = v;
046  }
047   
048  void remove_tree(Node * u)
049  {
050      if(u == NULL)    return;
051      remove_tree(u->left);
052      remove_tree(u->right);
053      free(u);
054  }
055   
056  char s[maxn];
057   
058  int read_input()
059  {
060      failed = 0;
061      remove_tree(root);
062      root = newnode();
063      while(1)
064      {
065          if(scanf("%s", s) == EOF)   return 0;
066          if(strcmp(s, "()") == 0)   break;
067          int v;
068          sscanf(&s[1], "%d", &v);
069          addnode(v, strchr(s, ',')+1);
070      }
071      return 1;
072  }
073   
074  int n, ans[maxn];
075  int bfs()
076  {
077      int front = 0, rear = 1;
078      n = 0;
079      Node * q[maxn];
080      q[0] = root;
081      while(front < rear)
082      {
083          Node * u = q[front++];
084          if(!u->value)   return 0;
085          ans[n++] = u->value;
086          if(u->left)   q[rear++] = u->left;
087          if(u->right)   q[rear++] = u->right;
088      }
089      return 1;
090  }
091   
092  int main()
093  {
094  #ifdef LOCAL
095      freopen("in", "r", stdin);
096  #endif
097      while(read_input())
098      {
099          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

 }

Tags: