二叉搜索树的两种实现（数组模拟，STL）

浏览数：49 / 时间：2015年06月08日

书上实现：

二叉搜索数的特点：高效实现插入一个数值，查询是否包含某个数值，删除某一个数值。

所有的节点都满足左子树上的所有节点都比自己的小，而右子树上的所有节点都比自己大的特点。

查询：如果当前数值等于根节点返回true，比根节点小，就往左儿子走，否则往右儿子走。

插入：按照查找数值的方法去找其所在位置，从根节点出发，往左右儿子中找到合适位置。

删除：需要删除的节点没有左儿子，那么就把右儿子提上去。

需要删除的节点的左儿子没有右儿子，那么就把左儿子提上去

　　　以上两种情况都不符合的话，就把左儿子的子孙中最大的节点提到需要删除的节点上。

 1 #include <cstdio>
 2 
 3 struct node {   //树  
 4     int val;  //节点的值
 5     node *lch, *rch;  //左右儿子
 6 };
 7 
 8 node *insert(node *p,int x) {
 9     if(p == NULL) {  //如果节点为空  并赋值为x
10         node *q = new node; 
11         q->val = x;
12         q->lch = q->rch = NULL;
13         return q;
14     }
15     else {   //递归调用
16         if(x < p->val) p->lch = insert(p->lch,x);
17         else p->rch = insert(p->rch,x);
18         return p;
19     }
20 }
21 
22 bool find(node *p, int x) {
23     if(p==NULL) return false;
24     else if(x == p->val) return true;
25     else if(x < p->val) return find(p->lch,x);
26     else return find(p->rch,x);
27 }
28 
29 node *remove(node *p,int x) {
30     if(p==NULL) return NULL;  //如果树为空 返回NULL
31     else if(x < p->val) p->lch = remove(p->lch,x); //
32     else if(x > p->val) p->rch = remove(p->rch,x);
33     else if(p->lch==NULL) {
34         node *q=p->rch;
35         delete p;
36         return q;
37     }
38     else if(p->lch->rch == NULL) {
39         node *q = p->lch;
40         q->rch = p->rch;
41         delete p;
42         return q;
43     }
44     else {
45         node *q;
46         for(q = p->lch; q->rch->rch !=NULL; q = q->rch);
47         node *r = q->rch;
48         q->rch=r->lch;
49         r->lch=p->lch;
50         r->rch=p->rch;
51         delete p;
52         return r;
53     }
54     return p;
55 }
56 
57 int main()
58 {
59     node *root =NULL;
60     root=insert(root,1);
61     root=insert(root,2);
62     root=insert(root,3);
63     root=insert(root,5);
64     root=insert(root,7);
65 
66     root=remove(root,2);
67 
68     bool flag=find(root,2);
69     bool flag1=find(root,7);
70     printf("%d %d\n",flag,flag1);
71     return 0;
72 }

set正是使用二叉搜索树维护集合的容器。

 1 #include <cstdio>
 2 #include <set>
 3 using namespace std;
 4 
 5 int main() {
 6 
 7     set<int> s;
 8 
 9     s.insert(1);
10     s.insert(3);
11     s.insert(5);
12 
13     set<int>::iterator it;
14 
15     it=s.find(1);
16     if(it == s.end()) puts("not found");
17     else puts("found");
18 
19     it=s.find(2);
20     if(it == s.end()) puts("not found");
21     else puts("find");
22 
23     s.erase(3);
24     if(s.count(3)!=0) puts("found");
25     else puts("not found");
26 
27     for(it = s.begin(); it != s.end(); it++) {
28         printf("%d\n",*it);
29     }
30     return 0;
31 }

map 是维护则是维护键和键对应值的容器。

 1 #include <cstdio>
 2 #include <map>
 3 #include <string>
 4 #include <iostream>
 5 using namespace std;
 6 
 7 int main() {
 8 
 9     map<int, const char*>m;
10 
11     m.insert(make_pair(1,"ONE"));
12     m.insert(make_pair(10,"THE"));
13 
14     m.insert(make_pair(44,"HYNU"));
15     m[100]="hynuacm";
16 
17     map<int,const char*>::iterator it;
18 
19     it=m.find(1);
20     puts(it->second);
21     it=m.find(2);
22     if(it == m.end()) puts("not found");
23     else puts(it->second);
24 
25     puts(m[10]);
26 
27     m.erase(10);
28 
29     for(it = m.begin(); it != m.end(); it++) {
30         printf("%d: %s\n",it->first,it->second);
31     }
32     return 0;
33 }