建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
推薦在看算法導論的這一章之前先看看嚴蔚敏老師在《數據結構》上的二叉查找樹。
整體來說二叉查找樹不難，就是插入和刪除節點時讓人糾結，我就是在刪除節點時各種糾結了。
二叉樹執行基本操作的時間與樹的高度成正比。
首先說下二叉查找樹的性質：
設x為二叉查找樹中的一個結點。如果y是x的左子樹中的一個結點，則key[y]<=key[x];如果y是x的右子樹的一個結點，則key[y]>=key[x]。
注意這個性質，和堆對比下，還是有區別的，并且這個性質表示二叉查找樹的根節點的左子樹中所有結點都小于根結點，所有右子樹的結點都大于根結點。所以根據這個性質，可以用中序訪問二叉查找數來實現從小大到排列。
首先看看這個二叉查找樹(P151圖12-1(a))：
圖1
按中序遍歷結果為：
2->3->5->5->7->8
接下來說說二叉查找樹的幾個操作：
SEARCH:查找關鍵字等于key的結點
MINIMUM:找出關鍵字最小的結點
MAXIMUM:找出關鍵字最大的結點
SUCCESSOR:找出結點x的后繼y
INSERT:在二叉查找樹中插入結點z
DELETE:在二叉查找樹中刪除結點z
里面就INSERT和DELETE麻煩一些。
首先逐步分析代碼：
①.BST的數據結構：
1
2
3
4
|
typedef struct Node{
int key;
Node *lchild, *rchild, *parent;
}Node, *BSTree;
|
②.BST的中序遍歷：
根據BST的性質，對于一個根結點x，所以比x小的結點都在x的左子樹中，所有比x大的結點都在x的右子樹中，并且沒一個結點都滿足這個性質，所以可以利用中序遍歷，按從小到大的順序輸出這個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的左子樹結點，根結點，右子樹結點的大小關系，不解釋。。。
代碼如下：
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
|
根據其后繼的特性，結點x的后繼是具有大于key[x]中的關鍵字最小者的那個結點。
第1~2行，x的右子樹的結點都是大于key[x]的結點，所以如果x有右子樹，則在右子樹中尋找最小值
第3~6行，如果沒有右子樹，則其后繼y,是x的父親結點的第一個右子樹(考慮為什么呢？根據特性：結點x的后繼是具有大于key[x]中的關鍵字最小者的那個結點。因為x沒有右子樹，所以這時，按中序遍歷的x下一個結點即后繼，應該是這樣一個子樹的根結點y，x的祖先是其左孩子，這樣，y就大于其左子樹所有結點，并且因為x是y的左子樹中最大的結點了)。這個說著肯定是云里霧里，還是看圖分析最好了，依然利用上面的圖1：
葉子結點5的后繼是根結點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的插入：
比如要把結點z插入二叉查找數T中，分以下幾步：
1.將key[z]從根結點x開始比較，并用y記錄x的父親結點，直到到達最后一層某一葉節點比較完,此時y指向某一葉節點,x是NULL。
2.如果此時y是NULL，則證明是空樹，于是根結點就是z
3.否則如果key[z]小于key[y]，則讓left[y] = z；當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的刪除：
比如要把二叉查找數T中的z結點刪除掉，這是要分三種情況：
1.z沒有左子樹和右子樹：
汗，這個就是直接刪除z，把z的父親結點parent[z]指向z的子樹設置為NULL。
如圖，直接刪除z，并讓結點12的右子樹為NULL。
2.z只有左子樹或者只有右子樹：
這個是讓z的子樹與其父親結點相連，刪除z即可。
如圖，此時直接刪除z，并讓z的子樹20的父親結點變成z的父親結點15。
3.z既有左子樹又有右子樹：
這是先用SUCCESSOR找到z的后繼y，因為y一定沒有左子樹(考慮為什么？下面解釋)，所以可以刪除y，并讓y的父親結點成為y的右子樹的父親結點(類似第2中情況)，并用y的key代替z的key。
如圖,y的右子樹7成為10的子樹，并且y取代了z的未知。
這是我們來考慮一個關鍵問題，y為何一定沒有左子樹？(習題12.2-5)
答：因為y是z的后繼，所以y是z的右子樹中最小的一個結點，如果y還有左子樹，則y的左子樹中的結點一定比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是要刪除的節點,而y是要替換z的節點
if(z->lchild == NULL || z->rchild == NULL)
y = z; // 當要刪除的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的父親節點的子樹
if(y->parent == NULL) // 如果y沒有父親節點，則表示y是根節點，詞典其子樹x為根節點
T = x;
else if(y == y->parent->lchild)
// 如果y是其父親節點的左子樹，則y的子樹x成為其父親節點的左子樹，
// 否則成為右子樹
y->parent->lchild = x;
else
y->parent->rchild = x;
if(y != z)
z->key = y->key;
return 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
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: 《算法導論》第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是要刪除的節點,而y是要替換z的節點
if(z->lchild == NULL || z->rchild == NULL)
y = z; // 當要刪除的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的父親節點的子樹
if(y->parent == NULL) // 如果y沒有父親節點，則表示y是根節點，詞典其子樹x為根節點
T = x;
else if(y == y->parent->lchild)
// 如果y是其父親節點的左子樹，則y的子樹x成為其父親節點的左子樹，
// 否則成為右子樹
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 << "刪除根節點后：";
BSTreeDelete(T, T);
InBSTree(T);
}
|
結果如圖：
OK,BST分析完了，這一章一定要搞懂，否則下一章的Red-Black-Tree就會一抹黑了~~
在我獨立博客上的原文：http://www.wutianqi.com/?p=2430
歡迎大家互相學習，互相討論！