SDUT 2129 树结构练习——判断给定森林中有多少棵树

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 #include <iostream>
  6 
  7 using namespace std;
  8 
  9 struct N
 10 {
 11     char data;
 12     N *l,*r;
 13 };
 14 
 15 N *creat()
 16 {
 17     N *p = (N *)malloc(sizeof(N));
 18     p->l = p->r = NULL;
 19     return p;
 20 }
 21 
 22 void insert(N *root,char s)
 23 {
 24     if(s > root->data)
 25     {
 26         if(root->r == NULL)
 27         {
 28             N *p = creat();
 29             root->r = p;
 30             p->data = s;
 31         }
 32         else
 33             insert(root->r,s);
 34     }
 35     else if(s < root->data)
 36     {
 37         if(root->l == NULL)
 38         {
 39             N *p = creat();
 40             root->l = p;
 41             p->data = s;
 42         }
 43         else
 44             insert(root->l,s);
 45     }
 46 }
 47 
 48 int top;
 49 
 50 void output1(N *root,char *s)
 51 {
 52     if(root == NULL)
 53         return ;
 54     output1(root->l,s);
 55     s[top++] = root->data;
 56     output1(root->r,s);
 57 }
 58 
 59 void output2(N *root,char *s)
 60 {
 61     if(root == NULL)
 62     {
 63         return ;
 64     }
 65     if(root->l == NULL && root->r == NULL)
 66     {
 67         s[top++] = root->data;
 68         return ;
 69     }
 70 
 71     output2(root->l,s);
 72     output2(root->r,s);
 73     s[top++] = root->data;
 74 }
 75 
 76 bool judge(N *r1,N *r2)
 77 {
 78     char s1[11];
 79     char s2[11];
 80 
 81     top = 0;
 82     output1(r1,s1);
 83     s1[top] = '';
 84 
 85     top = 0;
 86     output1(r2,s2);
 87     s2[top] = '';
 88 
 89     if(strcmp(s1,s2))
 90         return false;
 91 
 92     top = 0;
 93     output2(r1,s1);
 94     s1[top] = '';
 95 
 96     top = 0;
 97     output2(r2,s2);
 98     s2[top] = '';
 99 
100     if(strcmp(s1,s2))
101         return false;
102 
103     return true;
104 
105 }
106 
107 int main()
108 {
109     int n;
110     char t[11];
111 
112     while(cin>>n && n)
113     {
114         cin>>t;
115 
116         N *r1 = creat();
117         if(t[0] != '')
118         {
119             r1->data = t[0];
120             for(int i = 1;t[i] != ''; i++)
121                 insert(r1,t[i]);
122         }
123         while(n--)
124         {
125             cin>>t;
126 
127             N *r2 = creat();
128             if(t[0] != '')
129             {
130                 r2->data = t[0];
131                 for(int i = 1;t[i] != ''; i++)
132                     insert(r2,t[i]);
133             }
134             if(judge(r1,r2))
135                 cout<<"YES
";
136             else cout<<"NO
";
137         }
138     }
139     return 0;
140 }