建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
推薦在看算法導(dǎo)論的這一章之前先看看嚴(yán)蔚敏老師在《數(shù)據(jù)結(jié)構(gòu)》上的二叉查找樹。
整體來說二叉查找樹不難，就是插入和刪除節(jié)點時讓人糾結(jié)，我就是在刪除節(jié)點時各種糾結(jié)了。
二叉樹執(zhí)行基本操作的時間與樹的高度成正比。
首先說下二叉查找樹的性質(zhì)：
設(shè)x為二叉查找樹中的一個結(jié)點。如果y是x的左子樹中的一個結(jié)點，則key[y]<=key[x];如果y是x的右子樹的一個結(jié)點，則key[y]>=key[x]。
注意這個性質(zhì)，和堆對比下，還是有區(qū)別的，并且這個性質(zhì)表示二叉查找樹的根節(jié)點的左子樹中所有結(jié)點都小于根結(jié)點，所有右子樹的結(jié)點都大于根結(jié)點。所以根據(jù)這個性質(zhì)，可以用中序訪問二叉查找數(shù)來實現(xiàn)從小大到排列。
首先看看這個二叉查找樹(P151圖12-1(a))：
圖1
按中序遍歷結(jié)果為：
2->3->5->5->7->8
接下來說說二叉查找樹的幾個操作：
SEARCH:查找關(guān)鍵字等于key的結(jié)點
MINIMUM:找出關(guān)鍵字最小的結(jié)點
MAXIMUM:找出關(guān)鍵字最大的結(jié)點
SUCCESSOR:找出結(jié)點x的后繼y
INSERT:在二叉查找樹中插入結(jié)點z
DELETE:在二叉查找樹中刪除結(jié)點z
里面就INSERT和DELETE麻煩一些。
首先逐步分析代碼：
①.BST的數(shù)據(jù)結(jié)構(gòu)：
1
2
3
4
|
typedef struct Node{
int key;
Node *lchild, *rchild, *parent;
}Node, *BSTree;
|
②.BST的中序遍歷：
根據(jù)BST的性質(zhì)，對于一個根結(jié)點x，所以比x小的結(jié)點都在x的左子樹中，所有比x大的結(jié)點都在x的右子樹中，并且沒一個結(jié)點都滿足這個性質(zhì)，所以可以利用中序遍歷，按從小到大的順序輸出這個BST。
代碼如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
// 遞歸版本
Node * BSTreeSearch(BSTree T, int k)
{
if(T == NULL || k == T->key)
return T;
if(k < T->key)
return BSTreeSearch(T->lchild, k);
else
return BSTreeSearch(T->rchild, k);
}
// 非遞歸版本
BSNode * IterativeBSTreeSearch(BSTree T, int k)
{
while(T != NULL && k != T->key)
{
if(k < T->lchild->key);
x = T->lchild;
else
x = T->rchild;
}
return x;
}
|
③.BST的最大值與最小值：
依然是利用BST的左子樹結(jié)點，根結(jié)點，右子樹結(jié)點的大小關(guān)系，不解釋。。。
代碼如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
Node * BSTreeMinimum(BSTree T)
{
while(T->lchild != NULL)
T = T->lchild;
return T;
}
Node * BSTreeMaximum(BSTree T)
{
while(T->rchild != NULL)
T = T->rchild;
return T;
}
|
下面開始有些麻煩了。
④.BST的后繼：
這是其偽代碼：
1
2
3
4
5
6
7
8
|
TREE-SUCCESSOR(x)
1 if right[x] ≠ NIL
2 then return TREE-MINIMUM (right[x])
3 y ← p[x]
4 while y ≠ NIL and x = right[y]
5 do x ← y
6 y ← p[y]
7 return y
|
根據(jù)其后繼的特性，結(jié)點x的后繼是具有大于key[x]中的關(guān)鍵字最小者的那個結(jié)點。
第1~2行，x的右子樹的結(jié)點都是大于key[x]的結(jié)點，所以如果x有右子樹，則在右子樹中尋找最小值
第3~6行，如果沒有右子樹，則其后繼y,是x的父親結(jié)點的第一個右子樹(考慮為什么呢？根據(jù)特性：結(jié)點x的后繼是具有大于key[x]中的關(guān)鍵字最小者的那個結(jié)點。因為x沒有右子樹，所以這時，按中序遍歷的x下一個結(jié)點即后繼，應(yīng)該是這樣一個子樹的根結(jié)點y，x的祖先是其左孩子，這樣，y就大于其左子樹所有結(jié)點，并且因為x是y的左子樹中最大的結(jié)點了)。這個說著肯定是云里霧里，還是看圖分析最好了，依然利用上面的圖1：
葉子結(jié)點5的后繼是根結(jié)點5.
具體代碼如下：
1
2
3
4
5
6
7
8
9
10
11
12
|
Node *BSTreeSuccessor(Node *x)
{
if(x->rchild != NULL)
return BSTreeMinimum(x->rchild);
Node *y = x->parent;
while(y != NULL && x == y->rchild)
{
x = y;
y = y->parent;
}
return y;
}
|
⑤.BST的插入：
比如要把結(jié)點z插入二叉查找數(shù)T中，分以下幾步：
1.將key[z]從根結(jié)點x開始比較，并用y記錄x的父親結(jié)點，直到到達(dá)最后一層某一葉節(jié)點比較完,此時y指向某一葉節(jié)點,x是NULL。
2.如果此時y是NULL，則證明是空樹，于是根結(jié)點就是z
3.否則如果key[z]小于key[y]，則讓left[y] = z；當(dāng)key[z]大于或等于key[y]，則讓right[y] = z。
插入就是那么簡單。
看看偽代碼，就是按這個步驟來的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
TREE-INSERT(T, z)
1 y ← NIL
2 x ← root[T]
3 while x ≠ NIL
4 do y ← x
5 if key[z] < key[x]
6 then x ← left[x]
7 else x ← right[x]
8 p[z] ← y
9 if y = NIL
10 then root[T] ← z // Tree T was empty
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
|
具體的代碼如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
void BSTreeInsert(BSTree &T, int k)
{
Node *y = NULL;
Node *x = T;
Node *z = new Node;
z->key = k;
z->lchild = z->parent = z->rchild = NULL;//////////
while(x != NULL)
{
y = x;
if(k < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if(y == NULL)
{
T = z;
}
else
if(k < y->key)
y->lchild = z;
else
y->rchild = z;
}
|
⑥.BST的刪除：
比如要把二叉查找數(shù)T中的z結(jié)點刪除掉，這是要分三種情況：
1.z沒有左子樹和右子樹：
汗，這個就是直接刪除z，把z的父親結(jié)點parent[z]指向z的子樹設(shè)置為NULL。
如圖，直接刪除z，并讓結(jié)點12的右子樹為NULL。
2.z只有左子樹或者只有右子樹：
這個是讓z的子樹與其父親結(jié)點相連，刪除z即可。
如圖，此時直接刪除z，并讓z的子樹20的父親結(jié)點變成z的父親結(jié)點15。
3.z既有左子樹又有右子樹：
這是先用SUCCESSOR找到z的后繼y，因為y一定沒有左子樹(考慮為什么？下面解釋)，所以可以刪除y，并讓y的父親結(jié)點成為y的右子樹的父親結(jié)點(類似第2中情況)，并用y的key代替z的key。
如圖,y的右子樹7成為10的子樹，并且y取代了z的未知。
這是我們來考慮一個關(guān)鍵問題，y為何一定沒有左子樹？(習(xí)題12.2-5)
答：因為y是z的后繼，所以y是z的右子樹中最小的一個結(jié)點，如果y還有左子樹，則y的左子樹中的結(jié)點一定比y小！
具體代碼如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
Node* BSTreeDelete(BSTree T, Node *z)
{
Node *x, *y;
// z是要刪除的節(jié)點,而y是要替換z的節(jié)點
if(z->lchild == NULL || z->rchild == NULL)
y = z; // 當(dāng)要刪除的z至多有一個子樹，則y=z；
else
y = BSTreeSuccessor(z); // y是z的后繼
if(y->lchild != NULL)
x = y->lchild;
else
x = y->rchild;
if(x != NULL)
x->parent = y->parent; //如果y至多只有一個子樹，則使y的子樹成為y的父親節(jié)點的子樹
if(y->parent == NULL) // 如果y沒有父親節(jié)點，則表示y是根節(jié)點，詞典其子樹x為根節(jié)點
T = x;
else if(y == y->parent->lchild)
// 如果y是其父親節(jié)點的左子樹，則y的子樹x成為其父親節(jié)點的左子樹，
// 否則成為右子樹
y->parent->lchild = x;
else
y->parent->rchild = x;
if(y != z)
z->key = y->key;
return y;
}
|
下面是整個二叉查找樹的實現(xiàn)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
/*
* Author: Tanky Woo
* Blog: www.WuTianQi.com
* Description: 《算法導(dǎo)論》第12章 BST
*/
#include <iostream>
#define NULL 0
using namespace std;
// ①
typedef struct Node{
int key;
Node *lchild, *rchild, *parent;
}Node, *BSTree;
// ②
Node * BSTreeSearch(BSTree T, int k)
{
if(T == NULL || k == T->key)
return T;
if(k < T->key)
return BSTreeSearch(T->lchild, k);
else
return BSTreeSearch(T->rchild, k);
}
/*
BSNode * IterativeBSTreeSearch(BSTree T, int k)
{
while(T != NULL && k != T->key)
{
if(k < T->lchild->key);
x = T->lchild;
else
x = T->rchild;
}
return x;
}
*/
// ③
Node * BSTreeMinimum(BSTree T)
{
while(T->lchild != NULL)
T = T->lchild;
return T;
}
Node * BSTreeMaximum(BSTree T)
{
while(T->rchild != NULL)
T = T->rchild;
return T;
}
// ④
Node *BSTreeSuccessor(Node *x)
{
if(x->rchild != NULL)
return BSTreeMinimum(x->rchild);
Node *y = x->parent;
while(y != NULL && x == y->rchild)
{
x = y;
y = y->parent;
}
return y;
}
// ⑤
void BSTreeInsert(BSTree &T, int k)
{
Node *y = NULL;
Node *x = T;
Node *z = new Node;
z->key = k;
z->lchild = z->parent = z->rchild = NULL;
while(x != NULL)
{
y = x;
if(k < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if(y == NULL)
{
T = z;
}
else
if(k < y->key)
y->lchild = z;
else
y->rchild = z;
}
// ⑤
Node* BSTreeDelete(BSTree T, Node *z)
{
Node *x, *y;
// z是要刪除的節(jié)點,而y是要替換z的節(jié)點
if(z->lchild == NULL || z->rchild == NULL)
y = z; // 當(dāng)要刪除的z至多有一個子樹，則y=z；
else
y = BSTreeSuccessor(z); // y是z的后繼
if(y->lchild != NULL)
x = y->lchild;
else
x = y->rchild;
if(x != NULL)
x->parent = y->parent; //如果y至多只有一個子樹，則使y的子樹成為y的父親節(jié)點的子樹
if(y->parent == NULL) // 如果y沒有父親節(jié)點，則表示y是根節(jié)點，詞典其子樹x為根節(jié)點
T = x;
else if(y == y->parent->lchild)
// 如果y是其父親節(jié)點的左子樹，則y的子樹x成為其父親節(jié)點的左子樹，
// 否則成為右子樹
y->parent->lchild = x;
else
y->parent->rchild = x;
if(y != z)
z->key = y->key;
return y;
}
void InBSTree(BSTree T)
{
if(T != NULL)
{
InBSTree(T->lchild);
cout << T->key << " ";
InBSTree(T->rchild);
}
}
int main()
{
int m;
BSTree T = NULL;
for(int i=0; i<6; ++i)
{
cin >> m;
BSTreeInsert(T, m);
cout << "二叉查找樹中序查找：";
InBSTree(T);
cout << endl;
}
cout << "刪除根節(jié)點后：";
BSTreeDelete(T, T);
InBSTree(T);
}
|
結(jié)果如圖：
OK,BST分析完了，這一章一定要搞懂，否則下一章的Red-Black-Tree就會一抹黑了~~
在我獨立博客上的原文：http://www.wutianqi.com/?p=2430
歡迎大家互相學(xué)習(xí)，互相討論！