POJ 1577 Falling Leaves

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath>   
 5 #include<algorithm>  
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 const int maxn=105;
10 char str[maxn][maxn];
11 
12 typedef struct node{
13     char v;
14     node *l,*r;
15 } node;
16 
17 node* newnode(char ch){   // 创建一个新的节点 
18     node* u=(node*)malloc(sizeof(node));
19     if(u!=NULL){
20         u->v=ch;
21     u->l=u->r=NULL;
22     }
23     return u;
24 }
25 
26 node* addnode(char ch,node* nd){ // 增加节点 
27     if(nd==NULL) nd=newnode(ch);
28     else{
29         if(ch>=nd->v) nd->r=addnode(ch,nd->r);//如果更大， 放在当前这个头的右子树 
30         else nd->l=addnode(ch,nd->l);//如果更小，放在 当前这个头的左子树 
31     }
32     return nd;
33 }
34 
35 void dfs(node* nd){
36     if(nd!=NULL){
37         printf("%c",nd->v);
38         dfs(nd->l);
39         dfs(nd->r);
40     }
41 }
42 
43 int main()
44 {
45     int i,j,cnt=0;
46     node *root=NULL;
47     while(scanf("%s",str[cnt])){
48         char tmp=str[cnt][0];
49         if(tmp==‘*‘||tmp==‘$‘){
50             for(i=cnt-1;i>=0;i--)
51                 for(j=0;j<strlen(str[i]);j++)
52                 root=addnode(str[i][j],root);
53                 
54                 dfs(root);
55                 printf("\n");
56                 root=NULL;
57                 cnt=0;
58                 memset(str,0,sizeof(str));
59         }
60         else 
61         cnt++;
62         if(tmp==‘$‘) break;
63     }
64     return 0;
65 }