[HDOJ5444]Elven Postman

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5444

GF长春网赛做过的题，裸的二叉查找树。将数据丢如树内查找值，走到一个左儿子输出一个E，走到一个右儿子输出一个W，走到头后不输出。

代码：

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 typedef struct Node {
23     Node* left;
24     Node* right;
25     int data;
26     Node() { left = NULL; right = NULL; }
27 }Node;
28 
29 Node* insert(Node* cur, int data) {
30     if(cur == NULL) {
31         cur = new Node();
32         cur->data = data;
33         return cur;
34     }
35     if(data > cur->data) {
36         cur->right = insert(cur->right, data);
37     }
38     else {
39         cur->left = insert(cur->left, data);
40     }
41     return cur;
42 }
43 
44 void solve(Node* cur, int x) {
45     if(cur == NULL ||cur->data == x) {
46         printf("
");
47         return ;
48     }
49 
50     if(x > cur->data) {
51         printf("W");
52         return solve(cur->right, x);
53     }
54     if(x < cur->data) {
55         printf("E");
56         return solve(cur->left, x);
57     }
58 }
59 
60 int n, q, x, tmp;
61 
62 int main() {
63     //freopen("input", "r", stdin);
64     int T;
65     scanf("%d", &T);
66     while(T--) {
67         scanf("%d", &n);
68         Node* root = NULL;
69         for(int i = 0; i < n; i++) {
70             scanf("%d", &tmp);
71             root = insert(root, tmp);
72         }
73         scanf("%d", &q);
74         while(q--) {
75             scanf("%d", &x);
76             solve(root, x);
77         }
78     }
79     return 0;
80 }

静态分配内存：

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 const int maxn = 1010;
23 
24 typedef struct Node {
25     Node* left;
26     Node* right;
27     int data;
28     Node() { left = NULL; right = NULL; }
29 }Node;
30 
31 Node memory[maxn<<1];
32 int CNT;
33 
34 Node* insert(Node* cur, int data) {
35     if(cur == NULL) {
36 //        cur = new Node()
37         cur = &memory[CNT++];
38         cur->left = NULL;
39         cur->right = NULL;
40         cur->data = data;
41         return cur;
42     }
43     if(data > cur->data) {
44         cur->right = insert(cur->right, data);
45     }
46     else {
47         cur->left = insert(cur->left, data);
48     }
49     return cur;
50 }
51 
52 void solve(Node* cur, int x) {
53     if(cur == NULL ||cur->data == x) {
54         printf("
");
55         return ;
56     }
57 
58     if(x > cur->data) {
59         printf("W");
60         return solve(cur->right, x);
61     }
62     if(x < cur->data) {
63         printf("E");
64         return solve(cur->left, x);
65     }
66 }
67 
68 int n, q, x, tmp;
69 
70 int main() {
71     // freopen("input", "r", stdin);
72     int T;
73     scanf("%d", &T);
74     while(T--) {
75         CNT = 0;
76         memset(memory, -1, sizeof(memory));
77         scanf("%d", &n);
78         Node* root = NULL;
79         for(int i = 0; i < n; i++) {
80             scanf("%d", &tmp);
81             root = insert(root, tmp);
82         }
83         scanf("%d", &q);
84         while(q--) {
85             scanf("%d", &x);
86             solve(root, x);
87         }
88     }
89     return 0;
90 }