二叉搜索树的两种实现(数组模拟,STL)

书上实现:

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

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

查询:如果当前数值等于根节点返回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 }

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。