hdu 5444 Elven Postman（二叉树）——2015 ACM/ICPC Asia Regional Changchun Online

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<string>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<queue>
  7 
  8 using namespace std;
  9 
 10 char ans[1100][1100];
 11 
 12 struct Node
 13 {
 14     int num,we[2];    //分别代表当前节点的值，左孩子，右孩子的序号 
 15     Node(int num=0):num(num){
 16         we[0]=we[1]=0;
 17     }    
 18 };
 19 
 20 struct Tree
 21 {
 22     int n;
 23     
 24     Node node[11000];
 25     
 26     void init()
 27     {
 28         n=0;
 29     }
 30     
 31     int newNode(int val)
 32     {
 33         node[++n]=Node(val);
 34         return n;
 35     }
 36     
 37     void insert(int &u,int val)
 38     {
 39         if(u==0)
 40         {
 41             u=newNode(val);
 42             return;
 43         }
 44         
 45         if(val<node[u].num)
 46         {
 47             insert(node[u].we[0],val);
 48         }
 49         else
 50         {
 51             insert(node[u].we[1],val);
 52         }
 53     }
 54     
 55     void solve(int u,int d,char* s)
 56     {
 57         if(u==0) return;
 58         s[d]=‘\0‘;
 59         strcpy(ans[node[u].num],s);
 60         
 61         if(node[u].we[0])
 62         {
 63             s[d]=‘E‘;
 64             solve(node[u].we[0],d+1,s);
 65         }
 66         if(node[u].we[1])
 67         {
 68             s[d]=‘W‘;
 69             solve(node[u].we[1],d+1,s);
 70         }
 71     }
 72     
 73 }solver;
 74 
 75 int main()
 76 {
 77     int k,m,q,t,p;
 78     int T;
 79     
 80     cin>>T;
 81     
 82     while(T--)
 83     {
 84         int n;
 85         
 86         cin>>n;
 87         
 88         if(n==0) continue;
 89         
 90         cin>>k;
 91         int root = solver.newNode(k);
 92         
 93         for(int i=2;i<=n;++i)
 94         {
 95             cin>>k;
 96             solver.insert(root,k);
 97         }
 98         
 99         char s[1100];
100         solver.solve(root,0,s);
101         
102         cin>>m;
103         while(m--)
104         {
105             cin>>t;
106             cout<<ans[t]<<endl;
107         }
108          
109     }
110     return 0;
111 }