1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
struct Node {
int val, parent, lchild, rchild;
Node() : val(-1), parent(-1), lchild(-1), rchild(-1) {}
} treenodes[3965];
int root = -1, num_nodes = 0;
inline int new_node(int _value) {
treenodes[num_nodes].val = _value;
return (num_nodes++);
}
void __preorder(int rt) {
if (~rt) {
printf(" %d,", treenodes[rt].val);
__preorder(treenodes[rt].lchild);
__preorder(treenodes[rt].rchild);
}
}
void __inorder(int rt) {
if (~rt) {
__inorder(treenodes[rt].lchild);
printf(" %d,", treenodes[rt].val);
__inorder(treenodes[rt].rchild);
}
}
inline void printall() {
__preorder(root); putchar('\n');
__inorder(root); putchar('\n');
}
int __search(int rt, int _target) {
if (!~rt)
return -1;
else if (_target == treenodes[rt].val)
return rt;
else {
if (_target < treenodes[rt].val)
return __search(treenodes[rt].lchild, _target);
else
return __search(treenodes[rt].rchild, _target);
}
} inline bool search(int _target) {
return ~__search(root, _target);
}
int __insert(int rt, int _value) {
if (!~rt)
return new_node(_value);
else {
if (treenodes[rt].val != _value) {
if (_value < treenodes[rt].val) {
treenodes[rt].lchild = __insert(treenodes[rt].lchild, _value);
treenodes[treenodes[rt].lchild].parent = rt;
} else {
treenodes[rt].rchild = __insert(treenodes[rt].rchild, _value);
treenodes[treenodes[rt].rchild].parent = rt;
}
}
return rt;
}
} inline void insert(int _value) {
root = __insert(root, _value);
}
int cur;
int main(int argc, char *argv[]) {
root = new_node(39);
printf("index_root=%d\nnum_nodes=%d\n", root, num_nodes);
printf("%d\n", treenodes[root].val);
printf("%d %d\n", search(39), search(128));
while (~scanf("%d", &cur))
insert(cur);
printall();
for (int k = 0; k != 10; ++k)
printf("%d\n", search(k));
return 0;
}
|