今天實(shí)現(xiàn)了《算法導(dǎo)論》里提到的二叉搜索樹(shù)。
支持的操作有：插入、刪除、查詢、前驅(qū)、后繼、遍歷等。
首先定義樹(shù)節(jié)點(diǎn)的結(jié)構(gòu)體：
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;
// 空樹(shù)
if(yy==NULL) root=z;
else{
if(yy->key<z->key) yy->r=z;
else yy->l=z;
}
}
插入就是將新的鍵值放到合適的位置，使得二叉搜索樹(shù)的性質(zhì)得以保存。
用兩個(gè)指針yy,xx，yy指向xx的父節(jié)點(diǎn)。xx跟yy同時(shí)向下搜索：當(dāng)待插入鍵值小于xx指向的節(jié)點(diǎn)鍵值時(shí)，xx指向xx的左兒子，否則指向右兒子。yy跟進(jìn)。直到xx為空，說(shuō)明到達(dá)合適的位置了，此時(shí)建立新的節(jié)點(diǎn)并把信息存進(jìn)去。修改yy所指的節(jié)點(diǎn)（此時(shí)為新節(jié)點(diǎn)的父節(jié)點(diǎn)）的兒子指針。
2. 刪除操作
刪除操作比較復(fù)雜一些，先看下面的代碼：
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的非空兒子，此時(shí)y最多只有一個(gè)兒子。若y無(wú)兒子，x為空
11 node *x;
12 if(y->l!=NULL) x=y->l;
13 else x=y->r;
14
15 // y有一個(gè)兒子，則將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 // 當(dāng)y!=z時(shí)，則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的節(jié)點(diǎn)時(shí)，首先要找到這個(gè)節(jié)點(diǎn)，用函數(shù)node *search(long k)，返回一個(gè)指針指向包含該鍵值的節(jié)點(diǎn)(如第3行所示)。
接下來(lái)分三種情況：
被刪節(jié)點(diǎn)無(wú)孩子、只有一個(gè)孩子、有兩個(gè)孩子。
若是情況1或2，y指向被刪節(jié)點(diǎn)，否則指向被刪節(jié)點(diǎn)的后繼，如6~8行所示。這個(gè)操作后，y所指向的節(jié)點(diǎn)至多只有1個(gè)孩子（想想為什么）
接著指針x指向y唯一的孩子（若有的話）并改變x的父親指針，指向y的父節(jié)點(diǎn)（注意此時(shí)y的父親指針仍指向y的父親）
19~23行處理y是根的情況；26行處理case3的情況。
最后刪除y，并以引用變量res返回被刪的節(jié)點(diǎn)的信息。
3. 搜索
包括找一個(gè)鍵值k，找鍵值k的前驅(qū)、后繼，最大最小值。
原理比較簡(jiǎn)單，代碼如下：
1 // 返回以x為根的子樹(shù)的最小值
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大的數(shù)中最小的一個(gè)
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為根節(jié)點(diǎn)且無(wú)后繼
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. 中序遍歷
相當(dāng)于是從小到大輸出樹(shù)中節(jié)點(diǎn)的鍵值。
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 }