今天實現了《算法導論》里提到的二叉搜索樹。
支持的操作有：插入、刪除、查詢、前驅、后繼、遍歷等。
首先定義樹節點的結構體：
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 }