今天实现了《算法导论》里提到的二叉搜索树。
支持的操作有：插入、删除、查询、前驱、后继、遍历等。
首先定义树节点的结构体：
struct node{
node(long k,int position){
l=r=p=NULL;
key=k,pos=position;
}
node(){
l=r=p=NULL;
}
node *l,*r,*p;
int pos;
long key;
};
1. 插入操作
void insert(long k,int position)
{
node *yy=NULL;
node *xx = root;
while(xx!=NULL){
yy=xx;
if(k>xx->key) xx=xx->r;
else xx=xx->l;
}
node *z=new node(k,position);
z->p=yy;
// 空树
if(yy==NULL) root=z;
else{
if(yy->key<z->key) yy->r=z;
else yy->l=z;
}
}
插入就是将新的键值放到合适的位置，使得二叉搜索树的性质得以保存。
用两个指针yy,xx，yy指向xx的父节点。xx跟yy同时向下搜索：当待插入键值小于xx指向的节点键值时，xx指向xx的左儿子，否则指向右儿子。yy跟进。直到xx为空，说明到达合适的位置了，此时建立新的节点并把信息存进去。修改yy所指的节点（此时为新节点的父节点）的儿子指针。
2. 删除操作
删除操作比较复杂一些，先看下面的代码：
1 bool del(long key,node &res)
2 {
3 node *z=search(key);
4 if(z==NULL) return false;
5
6 node *y;
7 if(z->l ==NULL || z->r==NULL) y=z;
8 else y=successor(z->key);
9
10 // x指向y的非空儿子，此时y最多只有一个儿子。若y无儿子，x为空
11 node *x;
12 if(y->l!=NULL) x=y->l;
13 else x=y->r;
14
15 // y有一个儿子，则将y删去
16 if(x!=NULL) x->p=y->p;
17
18 // y is the root
19 if(y->p==NULL) root=x;
20 else{
21 if(y==y->p->l) (y->p)->l=x;
22 else y->p->r=x;
23 }
24
25 // 当y!=z时，则y是z的后继，删去z后，y取代z
26 if(y!=z) z->key=y->key,z->pos=y->pos;
27 res.key=z->key,res.pos=z->pos;
28 delete y;
29 return true;
30 }
删除键值为k的节点时，首先要找到这个节点，用函数node *search(long k)，返回一个指针指向包含该键值的节点(如第3行所示)。
接下来分三种情况：
被删节点无孩子、只有一个孩子、有两个孩子。
若是情况1或2，y指向被删节点，否则指向被删节点的后继，如6~8行所示。这个操作后，y所指向的节点至多只有1个孩子（想想为什么）
接着指针x指向y唯一的孩子（若有的话）并改变x的父亲指针，指向y的父节点（注意此时y的父亲指针仍指向y的父亲）
19~23行处理y是根的情况；26行处理case3的情况。
最后删除y，并以引用变量res返回被删的节点的信息。
3. 搜索
包括找一个键值k，找键值k的前驱、后继，最大最小值。
原理比较简单，代码如下：
1 // 返回以x为根的子树的最小值
2 node *minimum(node *x)
3 {
4 while(x->l!=NULL) x=x->l;
5 return x;
6 }
7
8 node *maximum(node *x)
9 {
10 while(x->r!=NULL) x=x->r;
11 return x;
12 }
13
14 // 返回x的后继，即比x大的数中最小的一个
15 node *successor(long k)
16 {
17 node *x=search(k);
18 node *y=NULL;
19 if(x->r!=NULL) return minimum(x->r);
20 else{
21 y=x->p;
22 while(y!=NULL && x==y->r){
23 x=y;
24 y=x->p;
25 }
26 }
27 // 若y==NULL 则x为根节点且无后继
28 return y;
29 }
30
31 node *predecessor(long k)
32 {
33 node *x=search(k);
34 node *y=NULL;
35 if(x->l!=NULL) return maximum(x->l);
36 else{
37 y=x->p;
38 while(y!=NULL && x==y->l){
39 x=y;
40 y=x->p;
41 }
42 }
43 return y;
44 }
4. 中序遍历
相当于是从小到大输出树中节点的键值。
1 void inorderWalk(node *x)
2 {
3 if(x!=NULL){
4 inorderWalk(x->l);
5 printf("%d ",x->key);
6 inorderWalk(x->r);
7 }
8 }