二叉查找树递归定义：
二叉查找树是空树或不是空树
二叉查找树的左二叉查找树的值一定小于二叉查找树的值或左二叉查找树为空树
二叉查找树的右二叉查找树的值一定大于二叉查找树的值或右二叉查找树为空树
不维护父亲域的，坑爹啊。
放上代码：
|
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
#include <iostream>#include <string>using
namespace
std;
#define NEW(d) new BST(d)struct
BST {
BST *lc, *rc;
int
data;
BST() : lc(0), rc(0) {}
BST(int
d) : lc(0), rc(0), data(d) {}
}*root = NULL;typedef
BST* tree;
void
insert(int
d) {
if(root == NULL) { root = NEW(d); return;}
tree t, now = root;
//二分找到合适的位置，t是指向这个合适的位置的指针
while(now != NULL) {
t = now;
if(now-> data > d) now = now-> lc;
else
now = now-> rc;
}
//插入新值到左边（或右边）
if(t-> data > d) t-> lc = NEW(d);
else
t-> rc = NEW(d);
}//没有父亲域的这个就是巨坑void
del(int
d) {
tree t, q = root, rt = root;
while(rt != NULL && rt-> data != d) {
q = rt;
if(rt-> data > d) rt = rt-> lc;
else
rt = rt-> rc;
}
//如果删除的是root
if(q == root) {delete
root; root = NULL; return;}
//如果不存在
if(rt == NULL) return;
//如果有一边是空的，那么将另一棵子树拉上来即可，在这里，已经包含了当两边都是空树时
if(rt-> lc == NULL) {
if(q-> lc == rt) q-> lc = rt-> rc;
else
q-> rc = rt-> rc;
delete
rt;
return;
}
if(rt-> rc == NULL) {
if(q-> lc == rt) q-> lc = rt-> lc;
else
q-> rc = rt-> lc;
delete
rt;
return;
}
t = rt;
q = rt-> rc;
while(q-> lc) {
t = q;
q = q-> lc;
}
rt-> data = q-> data;
if(t != rt) t-> lc = q-> rc;
else
t-> rc = q-> rc;
delete
q;
}tree search(int
d) {
tree ret = root;
while(ret != NULL && ret-> data != d) {
if(ret-> data > d) ret = ret-> lc;
else
ret = ret-> rc;
}
return
ret;
}tree max(){ if(root == NULL) return
NULL;
tree ret = root;
while(ret-> rc) ret = ret-> rc;
return
ret;
}tree min(){ if(root == NULL) return
NULL;
tree ret = root;
while(ret-> lc) ret = ret-> lc;
return
ret;
}void
out(string str) {
cout << str;
}int
main() {
out("1: insert\n2: del\n3: search\n4: max\n5: min\n");
int
c, t;
tree a;
while(cin >> c) {
switch(c) {
case
1: cin >> t;
insert(t);
break;
case
2: cin >> t;
del(t);
break;
case
3: cin >> t;
if(search(t) == NULL) out("Not here\n");
else
out("Is here!\n");
break;
case
4: a = max();
if(a != NULL) cout << a-> data << endl;
else
out("Warn!\n");
break;
case
5: a = min();
if(a != NULL) cout << a-> data << endl;
else
out("Warn!\n");
break;
default:
break;
}
}
return
0;
} |
因为有些坑爹，所以还是写递归版的del
|
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
|
void
del(tree& rt, int
d) {
if(rt == NULL) return;
if(rt-> data > d) del(rt-> lc, d);
else
if(rt-> data < d) del(rt-> rc, d);
else
{
tree q, t;
if(rt-> lc == NULL) {
q = rt;
rt = rt-> rc;
delete
q;
return;
}
if(rt-> rc == NULL) {
q = rt;
rt = rt-> lc;
delete
q;
return;
}
q = rt-> rc, t = rt;
//找后继
while(q-> lc != NULL) {
t = q;
q = q-> lc;
}
rt-> data = q-> data;
//当后继就是右子女，那么要将后继的右子女接到节点右边
if(rt == t) t-> rc = q-> rc;
//否则就要给后继的父亲的左子女赋值为后继的右子女
else
t-> lc = q-> rc;
delete
q;
}
} |
写个简洁的把，，，维护个父亲域。。旋转也好写了= =。
|
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
#include <iostream>#include <string>using
namespace
std;
#define NEW(d) new BST(d)struct
BST {
BST *lc, *rc, *pa;
int
data;
BST() : lc(0), rc(0), pa(0) {}
BST(int
d) : lc(0), rc(0), pa(0), data(d) {}
//BST operator= (BST& a) { lc = a.lc; rc = a.rc; pa = a.pa; data = a.data; return *this; }
}*root = NULL;typedef
BST* tree;
void
insert(int
d) {
if(root == NULL) { root = NEW(d); return;}
tree t, now = root;
//二分找到合适的位置，t是指向这个合适的位置的指针
while(now != NULL) {
t = now;
if(now-> data > d) now = now-> lc;
else
now = now-> rc;
}
//插入新值到左边（或右边）
if(t-> data > d) t-> lc = NEW(d), t-> lc-> pa = t;
else
t-> rc = NEW(d), t-> rc-> pa = t;
}tree search(int
d) {
tree ret = root;
while(ret != NULL && ret-> data != d) {
if(ret-> data > d) ret = ret-> lc;
else
ret = ret-> rc;
}
return
ret;
}void
del(int
d) {
tree rt = search(d), t, q;
if(rt == root) { delete
root; root = NULL; return; }
if(rt == NULL) return;
if(rt-> lc == NULL) {
if(rt-> pa-> lc == rt) rt-> pa-> lc = rt-> rc;
else
rt-> pa-> rc = rt-> rc;
delete
rt;
return;
}
if(rt-> rc == NULL) {
if(rt-> pa-> lc == rt) rt-> pa-> lc = rt-> lc;
else
rt-> pa-> rc = rt-> lc;
delete
rt;
return;
}
q = rt-> rc, t = rt;
while(q-> lc) {
t = q;
q = q-> lc;
}
rt-> data = q-> data;
if(t != rt) t-> rc = q-> rc;
else
t-> lc = q-> rc;
delete
q;
}tree max(){ if(root == NULL) return
NULL;
tree ret = root;
while(ret-> rc) ret = ret-> rc;
return
ret;
}tree min(){ if(root == NULL) return
NULL;
tree ret = root;
while(ret-> lc) ret = ret-> lc;
return
ret;
}void
out(string str) {
cout << str;
}int
main() {
out("1: insert\n2: del\n3: search\n4: max\n5: min\n");
int
c, t;
tree a;
while(cin >> c) {
switch(c) {
case
1: cin >> t;
insert(t);
break;
case
2: cin >> t;
del(t);
break;
case
3: cin >> t;
if(search(t) == NULL) out("Not here\n");
else
out("Is here!\n");
break;
case
4: a = max();
if(a != NULL) cout << a-> data << endl;
else
out("Warn!\n");
break;
case
5: a = min();
if(a != NULL) cout << a-> data << endl;
else
out("Warn!\n");
break;
default:
break;
}
}
return
0;
} |