ZOJ 1700 Falling Leaves

  1 #include <iostream>
  2 #include <stdlib.h>
  3  using namespace std;
  4 
  5  struct node
  6 {
  7     char a;
  8     node* left;
  9     node* right;
 10 };
 11 
 12 void insert(char, node**);
 13 void output(node* );
 14 node* modified_search(node*, char);
 15 void cleartree(node* head);
 16 
 17 int main()
 18 {
 19     char hold[200][200];
 20     char b[200];
 21     int i = 0;
 22     int count = 0;
 23     node* head = NULL;
 24 
 25     //freopen("test.txt", "r", stdin) ;
 26     
 27     while (cin >> b)
 28     {
 29         if (b[0] != '*' && b[0] != '$')
 30         {
 31             strcpy(hold[i++], b);
 32             count++;
 33         }
 34         if (b[0] == '*' || b[0] == '$')
 35         {
 36             for (int i = count - 1; i >=0; i--)
 37             {
 38                 for (int j = 0; j < strlen(hold[i]); j++)
 39                 {                    
 40                     insert(hold[i][j], &head);
 41                 }
 42             }//构建二叉树
 43 
 44             output(head);
 45             cleartree(head);
 46             cout << "\n";
 47             if (b[0] == '$')
 48                 break;
 49             
 50             count = 0;
 51             i = 0;
 52             head = NULL;
 53         }
 54         
 55     }
 56 }
 57 //前序输出
 58 void output(node* head)
 59 {
 60     if (head != NULL)
 61     {
 62         cout << head->a;
 63         output(head->left);
 64         output(head->right);
 65     }
 66 }
 67 
 68 //释放内存
 69 void cleartree(node* head)
 70 {
 71     if(head)
 72     {
 73         if (head->left == NULL && head->right == NULL)
 74         {
 75             delete head;
 76         }
 77         else
 78         {
 79             cleartree(head->left);
 80             cleartree(head->right);
 81             delete head;
 82         }
 83     }
 84     
 85 }
 86 
 87 //建立二叉查找树
 88 void insert(char a, node** head)
 89 {
 90      node* b;
 91      //查找需要插入的节点
 92      node* tmp = modified_search(*head, a);
 93      
 94      if (tmp)
 95      {
 96          b = new node;
 97          if (b == NULL)
 98          {
 99             // cout << "FULL";
100              exit(0);
101          }
102          b->a = a;
103          b->left = NULL;
104          b->right = NULL;
105 
106          if (tmp->a < b->a)
107              tmp->right = b;
108          if (tmp->a > b->a)
109              tmp->left = b;
110 
111      }
112      else
113      {
114         //创建头节点
115         if (*head == NULL)
116         {
117             *head = new node;
118             (*head)->a = a;
119             (*head)->left = NULL;
120             (*head)->right = NULL;
121         }
122      }
123      
124     
125 
126 }
127 //查找需要插入结点的函数
128 //写得比较复杂
129 node* modified_search(node* head, char a)
130 {
131     
132     if (head == NULL|| head->left == NULL &&  head->right == NULL)
133     {
134         return head;
135     }
136     else
137     {
138         if (head->a > a && head->left == NULL)//已经到底
139             return head;
140 
141         if (head->a > a && head->left != NULL)//还没到底，继续搜索
142             return modified_search(head->left, a);    
143 
144         if (head->a < a && head->right != NULL)//已经到底
145             return modified_search(head->right, a);
146 
147         if (head->a < a && head->right == NULL)//还没到底，继续搜索
148             return head;
149 
150         if (head->a == a)//当发现插入的数重复时，忽略
151             return NULL;
152     }
153 }