二叉搜索树的实现

复杂度 O(logn)
 1 #include <queue>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 //表示节点的结构体
 6 struct node{
 7     int val;
 8     node *lch,*rch;  
 9 };
10 
11 //插入数值x
12 node *intsert(node *p, int x)
13 {
14     if(p==NULL){
15         node *q=new node;
16         q->val=x;
17         q->lch=q->rch=NULL;
18         return q;
19     }
20     else{
21         if(x < p->val)  
22             p->lch=intsert(p->lch,x);
23         else
24             p->rch=intsert(p->rch,x);
25         return p;
26     }
27 }
28 
29 //查找数值x
30 bool find(node *p,int x)
31 {
32     if(p==NULL) return false;
33     else if(x == p->val)  return true;
34     else if(x < p->val)   return find(p->lch,x);
35     else return find(p->rch,x);
36 }
37 
38 //删除数值x
39 node *remove(node *p,int x){
40     if(p==NULL)  return NULL;
41     else if(x < p->val)   p->lch=remove(p->lch,x);
42     else if(x > p->val)   p->rch=remove(p->rch,x);
43     else if(p->lch==NULL){
44         node *q=p->ch;
45         delete p;
46         return q;
47     }
48     else if(p->lch->rch==NULL){
49         node *q=p->lch;
50         q->rch=p->rch;
51         delete p;
52         return q;
53     }
54     else{
55         node *q;
56         for(q=p->lch;q->rch->rch!=NULL;q=q->rch);
57         node *r=q->rch;
58         q->rch=r->lch;
59         r->lch=p->lch;
60         r->rch=p->rch;
61         delete p;
62         return r;
63     }
64     return p;
65 }