算法导论第十二章 二叉搜索树
一、二叉搜索树概览
二叉搜索树（又名二叉查找树、二叉排序树）是一种可提供良好搜寻效率的树形结构，支持动态集合操作，所谓动态集合操作，就是Search、Maximum、Minimum、Insert、Delete等操作，二叉搜索树可以保证这些操作在对数时间内完成。当然，在最坏情况下，即所有节点形成一种链式树结构，则需要O(n)时间。这就说明，针对这些动态集合操作，二叉搜索树还有改进的空间，即确保最坏情况下所有操作在对数时间内完成。这样的改进结构有AVL(Adelson-Velskii-Landis) tree、RB（红黑）tree和AA-tree。AVL树和红黑树相对应用较多，我们在后面的章节中在做整理。 在二叉搜索树中，任何一个节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中每一个节点的键值。我们结合书本的理论对二叉搜索树的动态集合操作做编程实现。其中除了Delete操作稍稍复杂之外，其余的操作都是非常简单的。
二、二叉搜索树动态集合操作
1、查询二叉搜索树 查询包括查找某一个元素，查找最大、最小关键字元素，查找前驱和后继，根据二叉搜索树的性质：左子树 < 根 < 右子树，这样的操作很容易实现。如下： 查找某元素：
1//@brief 查找元素
2//@return 是否查找成功
3bool BinarySearchTree::Search(const int search_value) const
4{
5 return _Search(m_pRoot, search_value) != NULL;
6}
7
8//@brief 真正的查找操作
9//非递归查找
10BinarySearchTree::_Node * BinarySearchTree::_Search(_Node *node, const int search_value) const
11{
12 //递归
13 // if (node == NULL || search_value = node->m_nValue)
14 // return node;
15 // if (search_value < node->m_nValue)
16 // return _Search(node->m_pLeft);
17 // else
18 // return _Search(node->m_pRight);
19 //非递归
20 while (node && search_value != node->m_nValue) {
21 if (search_value < node->m_nValue)
22 node = node->m_pLeft;
23 else
24 node = node->m_pRight;
25 }
26 return node;
27}查找最大、最小关键字元素：
1//@brief 得到以node为根节点的子树中的最大关键字节点
2BinarySearchTree::_Node * BinarySearchTree::_GetMaximum(_Node *node) const
3{
4 while (node->m_pRight) {
5 node = node->m_pRight;
6 }
7 return node;
8}
9
10//@brief 得到以node为根节点的子树中的最小关键字节点
11BinarySearchTree::_Node * BinarySearchTree::_GetMinimum(_Node *node) const
12{
13 while (node->m_pLeft) {
14 node = node->m_pLeft;
15 }
16 return node;
17}查找前驱和后继：
1//@brief 得到一个同时存在左右子树的节点node的前驱
2BinarySearchTree::_Node * BinarySearchTree::_GetPredecessor(_Node *node) const
3{
4 if (node->m_pLeft)
5 return _GetMinimum(node);
6 _Node *pTemp = node->m_pParent;
7 while (pTemp && node == pTemp->m_pLeft) {
8 node = pTemp;
9 pTemp = pTemp->m_pParent;
10 }
11 return pTemp;
12}
13
14//@brief 得到一个同时存在左右子树的节点node的后继
15BinarySearchTree::_Node * BinarySearchTree::_GetSuccessor(_Node *node) const
16{
17 if (node->m_pRight)
18 return _GetMaximum(node);
19
20 _Node *pTemp = node->m_pParent;
21 while (pTemp && node == pTemp->m_pRight) {
22 node = pTemp;
23 pTemp = pTemp->m_pParent;
24 }
25 return pTemp;
26}2、插入和删除 插入操作：通过不断的遍历，找到待插入元素应该处的位置，即可进行插入，代码如下：（包括递归和非递归的版本）
1//@brief 插入元素
2//@return 是否插入成功
3bool BinarySearchTree::Insert(const int new_value)
4{
5 //非递归
6 if (Search(new_value))
7 return false;
8 _Node *pTemp = NULL;
9 _Node *pCurrent = m_pRoot;
10 while (pCurrent) {
11 pTemp = pCurrent;
12 if (new_value < pCurrent->m_nValue)
13 pCurrent = pCurrent->m_pLeft;
14 else
15 pCurrent = pCurrent->m_pRight;
16 }
17 _Node *pInsert = new _Node();
18 pInsert->m_nValue = new_value;
19 pInsert->m_pParent = pTemp;
20 if (!pTemp) //空树
21 m_pRoot = pInsert;
22 else if (new_value < pTemp->m_nValue)
23 pTemp->m_pLeft = pInsert;
24 else
25 pTemp->m_pRight = pInsert;
26 return true;
27}
28
29//递归
30BinarySearchTree::_Node * BinarySearchTree::Insert_Recur(_Node *&node, const int new_value)
31{
32 if (node == NULL) {
33 _Node *pInsert = new _Node();
34 pInsert->m_nValue = new_value;
35 node = pInsert;
36 }
37 else if (new_value < node->m_nValue)
38 node->m_pLeft = Insert_Recur(node->m_pLeft, new_value);
39 else
40 node->m_pRight = Insert_Recur(node->m_pRight, new_value);
41 return node;
42}删除操作：有点小复杂，总共分为四种情况： 1）如果待删除节点没有子节点，则直接删除即可，并更改其父节点的指向； 2）如果待删除的节点只有一个子节点，其中，如果为左子树节点，则用左子树节点替换之；反之用右子树节点替换之； 3）如果待删除节点 z 有两个子节点，这个时候分两种情况考虑，第一种情况：z 的后继即为 z 的右孩子节点，则将 z 的有孩子节点替换之； 4）第二种情况： z 的后继不是 z 的有孩子节点，则首先用 z 的后继的有孩子节点替换 z 的后继，再用 z 的后继替换 z 。 没有图形作为辅助，实属难以表述和透彻理解，详细的过程和分析见书本上。 注意：在《算法导论》前几版的实现中，该过程的实现略有不同，相较上面这个过程，要简单一些，做法是：不是用 z 的后继 y 替换节点 z，而是删除节点 y，但复制 y 的关键字到节点 z 中来实现。但是这种做法，作者在最新这一版中明确提出，那种方法的缺陷是：会造成实际被删除的节点并不是被传递到删除过程中的那个节点，会有一些已删除节点的“过时”指针带来不必要的影响，总之复制删除的方法不是好的。 另外，还有一点是：这里 y 可以选择作为 z 的后继，也可以作为 z 的前驱。有意思的是，习题12.3-6提出一种为两者分配公平策略的机制，来实现较好的性能。何为公平策略，譬如下面图示所示：
左图右子树高度大于左子树，应选择后继替换待删除节点；右图则相反，应选择前驱；这里的公平策略的宗旨就是为了在实现动态集合操作的时候尽可能使树的高度维持在一个较低的高度。 代码实现如下：
1//@brief 删除元素
2//@return 是否删除成功
3bool BinarySearchTree::Delete(const int delete_value)
4{
5 _Node *delete_node = _Search(m_pRoot, delete_value);
6 //未找到该节点
7 if (!delete_node)
8 return false;
9 else {
10 _DeleteNode(delete_node);
11 return true;
12 }
13}
14
15//@brief 真正的删除操作
16void BinarySearchTree::_DeleteNode(_Node *delete_node)
17{
18 if (delete_node->m_pLeft == NULL)
19 _Delete_Transplant(delete_node, delete_node->m_pRight);
20 else if (delete_node->m_pRight == NULL)
21 _Delete_Transplant(delete_node, delete_node->m_pLeft);
22 else {
23 _Node *min_node = _GetMinimum(delete_node->m_pRight);
24 if (min_node->m_pParent != delete_node) {
25 _Delete_Transplant(min_node, min_node->m_pRight);
26 min_node->m_pRight = delete_node->m_pRight;
27 min_node->m_pRight->m_pParent = min_node;
28 }
29 _Delete_Transplant(delete_node, min_node);
30 min_node->m_pLeft = delete_node->m_pLeft;
31 min_node->m_pLeft->m_pParent = min_node;
32 }
33}
34
35void BinarySearchTree::_Delete_Transplant(_Node *unode, _Node *vnode)
36{
37 if (unode->m_pParent == NULL)
38 m_pRoot = vnode;
39 else if (unode == unode->m_pParent->m_pLeft)
40 unode->m_pParent->m_pLeft = vnode;
41 else
42 unode->m_pParent->m_pRight = vnode;
43
44 if (vnode)
45 vnode->m_pParent = unode->m_pParent;
46}这里增加了一个函数Transplant()来实现替换操作，使代码较简洁。 完整的代码如下：
1//BinarySearchTree.h
2#ifndef _BINARY_SEARCH_TREE_
3#define _BINARY_SEARCH_TREE_
4class BinarySearchTree
5{
6private:
7 struct _Node {
8 int m_nValue;
9 _Node *m_pParent;
10 _Node *m_pLeft;
11 _Node *m_pRight;
12 };
13public:
14 BinarySearchTree(_Node *pRoot = NULL) :m_pRoot(pRoot) {}
15 ~BinarySearchTree();
16 //@brief 插入元素
17 //@return 是否插入成功
18 bool Insert(const int new_value);
19 //递归
20 _Node * Insert_Recur(_Node *&node, const int new_value);
21 //@brief 删除元素
22 //@return 是否删除成功
23 bool Delete(const int delete_value);
24 //@brief 查找元素
25 //@return 是否查找成功
26 bool Search(const int search_value) const;
27 //@brief 使用dot描述当前二叉查找树
28 void Display() const;
29 //@brief 树的遍历
30 void Inorder() const { Inorder_Tree_Walk(m_pRoot); }
31 void Preorder() const { Preorder_Tree_Walk(m_pRoot); }
32 void Postorder() const { Postorder_Tree_Walk(m_pRoot); }
33private:
34 //@brief 真正的删除操作
35 void _DeleteNode(_Node *delete_node);
36 void _Delete_Transplant(_Node *unode, _Node *vnode);
37 //@brief 得到以node为根节点的子树中的最大关键字节点
38 _Node * _GetMaximum(_Node *node) const;
39 //@brief 得到以node为根节点的子树中的最小关键字节点
40 _Node * _GetMinimum(_Node *node) const;
41 //@brief 得到一个同时存在左右子树的节点node的前驱
42 _Node * _GetPredecessor(_Node *node) const;
43 //@brief 得到一个同时存在左右子树的节点node的后继
44 _Node * _GetSuccessor(_Node *node) const;
45 //@brief 真正的查找操作
46 //非递归查找
47 _Node * _Search(_Node *node, const int search_value) const;
48 //@brief 显示一棵二叉搜索树
49 void _Display(/*iostream &ss, */_Node *node) const;
50 //@brief 递归释放节点
51 void _RecursiveReleaseNode(_Node *node);
52 void ShowGraphvizViaDot(const string &dot) const;
53 //@brief 树的遍历
54 void Inorder_Tree_Walk(_Node *node) const;
55 void Preorder_Tree_Walk(_Node *node) const;
56 void Postorder_Tree_Walk(_Node *node) const;
57private:
58 _Node * m_pRoot;
59};
60#endif//_BINARY_SEARCH_TREE_ 1//BinarySearchTree.cpp
2#include <iostream>
3#include <string>
4#include <iomanip>
5#include <ctime>
6using namespace std;
7#include "BinarySearchTree.h"
8BinarySearchTree::~BinarySearchTree()
9{
10 _RecursiveReleaseNode(m_pRoot);
11}
12
13//@brief 插入元素
14//@return 是否插入成功
15bool BinarySearchTree::Insert(const int new_value)
16{
17 //非递归
18 if (Search(new_value))
19 return false;
20 _Node *pTemp = NULL;
21 _Node *pCurrent = m_pRoot;
22 while (pCurrent) {
23 pTemp = pCurrent;
24 if (new_value < pCurrent->m_nValue)
25 pCurrent = pCurrent->m_pLeft;
26 else
27 pCurrent = pCurrent->m_pRight;
28 }
29 _Node *pInsert = new _Node();
30 pInsert->m_nValue = new_value;
31 pInsert->m_pParent = pTemp;
32 if (!pTemp) //空树
33 m_pRoot = pInsert;
34 else if (new_value < pTemp->m_nValue)
35 pTemp->m_pLeft = pInsert;
36 else
37 pTemp->m_pRight = pInsert;
38 return true;
39 // //该元素已经存在
40 // if (Search(new_value))
41 // return false;
42 //
43 // //空树，插入第1个节点
44 // if (!m_pRoot) {
45 // m_pRoot = new _Node();
46 // m_pRoot->m_nValue = new_value;
47 // return true;
48 // }
49 //
50 // //非第一个节点
51 // _Node *current_node = m_pRoot;
52 // while( current_node ) {
53 // _Node *&next_node_pointer = (new_value < current_node->m_nValue ? current_node->m_pLeft:current_node->m_pRight);
54 // if ( next_node_pointer )
55 // current_node = next_node_pointer;
56 // else {
57 // next_node_pointer = new _Node();
58 // next_node_pointer->m_nValue = new_value;
59 // next_node_pointer->m_pParent = current_node;
60 // break;
61 // }
62 // }
63 // return true;
64}
65
66//递归
67BinarySearchTree::_Node * BinarySearchTree::Insert_Recur(_Node *&node, const int new_value)
68{
69 if (node == NULL) {
70 _Node *pInsert = new _Node();
71 pInsert->m_nValue = new_value;
72 node = pInsert;
73 }
74 else if (new_value < node->m_nValue)
75 node->m_pLeft = Insert_Recur(node->m_pLeft, new_value);
76 else
77 node->m_pRight = Insert_Recur(node->m_pRight, new_value);
78 return node;
79}
80
81//@brief 删除元素
82//@return 是否删除成功
83bool BinarySearchTree::Delete(const int delete_value)
84{
85 _Node *delete_node = _Search(m_pRoot, delete_value);
86 //未找到该节点
87 if (!delete_node)
88 return false;
89 else {
90 _DeleteNode(delete_node);
91 return true;
92 }
93}
94
95//@brief 查找元素
96//@return 是否查找成功
97bool BinarySearchTree::Search(const int search_value) const
98{
99 return _Search(m_pRoot, search_value) != NULL;
100}
101//@brief 使用dot描述当前二叉查找树
102void BinarySearchTree::Display() const
103{
104 _Display(m_pRoot);
105}
106
107//@brief 树的遍历
108//中序
109void BinarySearchTree::Inorder_Tree_Walk(_Node *node) const
110{
111 if (node) {
112 Inorder_Tree_Walk(node->m_pLeft);
113 cout << node->m_nValue << " ";
114 Inorder_Tree_Walk(node->m_pRight);
115 }
116}
117
118//前序
119void BinarySearchTree::Preorder_Tree_Walk(_Node *node) const
120{
121 if (node) {
122 cout << node->m_nValue << " ";
123 Preorder_Tree_Walk(node->m_pLeft);
124 Preorder_Tree_Walk(node->m_pRight);
125 }
126}
127
128//后序
129void BinarySearchTree::Postorder_Tree_Walk(_Node *node) const
130{
131 if (node) {
132 Postorder_Tree_Walk(node->m_pLeft);
133 Postorder_Tree_Walk(node->m_pRight);
134 cout << node->m_nValue << " ";
135 }
136}
137
138//@brief 真正的删除操作
139void BinarySearchTree::_DeleteNode(_Node *delete_node)
140{
141 if (delete_node->m_pLeft == NULL)
142 _Delete_Transplant(delete_node, delete_node->m_pRight);
143 else if (delete_node->m_pRight == NULL)
144 _Delete_Transplant(delete_node, delete_node->m_pLeft);
145 else {
146 _Node *min_node = _GetMinimum(delete_node->m_pRight);
147 if (min_node->m_pParent != delete_node) {
148 _Delete_Transplant(min_node, min_node->m_pRight);
149 min_node->m_pRight = delete_node->m_pRight;
150 min_node->m_pRight->m_pParent = min_node;
151 }
152 _Delete_Transplant(delete_node, min_node);
153 min_node->m_pLeft = delete_node->m_pLeft;
154 min_node->m_pLeft->m_pParent = min_node;
155 }
156}
157
158void BinarySearchTree::_Delete_Transplant(_Node *unode, _Node *vnode)
159{
160 if (unode->m_pParent == NULL)
161 m_pRoot = vnode;
162 else if (unode == unode->m_pParent->m_pLeft)
163 unode->m_pParent->m_pLeft = vnode;
164 else
165 unode->m_pParent->m_pRight = vnode;
166 if (vnode)
167 vnode->m_pParent = unode->m_pParent;
168}
169
170//@brief 得到以node为根节点的子树中的最大关键字节点
171BinarySearchTree::_Node * BinarySearchTree::_GetMaximum(_Node *node) const
172{
173 while (node->m_pRight) {
174 node = node->m_pRight;
175 }
176 return node;
177}
178
179//@brief 得到以node为根节点的子树中的最小关键字节点
180BinarySearchTree::_Node * BinarySearchTree::_GetMinimum(_Node *node) const
181{
182 while (node->m_pLeft) {
183 node = node->m_pLeft;
184 }
185 return node;
186}
187
188//@brief 得到一个同时存在左右子树的节点node的前驱
189BinarySearchTree::_Node * BinarySearchTree::_GetPredecessor(_Node *node) const
190{
191 if (node->m_pLeft)
192 return _GetMinimum(node);
193
194 _Node *pTemp = node->m_pParent;
195 while (pTemp && node == pTemp->m_pLeft) {
196 node = pTemp;
197 pTemp = pTemp->m_pParent;
198 }
199 return pTemp;
200}
201
202//@brief 得到一个同时存在左右子树的节点node的后继
203BinarySearchTree::_Node * BinarySearchTree::_GetSuccessor(_Node *node) const
204{
205 if (node->m_pRight)
206 return _GetMaximum(node);
207
208 _Node *pTemp = node->m_pParent;
209 while (pTemp && node == pTemp->m_pRight) {
210 node = pTemp;
211 pTemp = pTemp->m_pParent;
212 }
213 return pTemp;
214}
215
216//@brief 真正的查找操作
217//非递归查找
218BinarySearchTree::_Node * BinarySearchTree::_Search(_Node *node, const int search_value) const
219{
220 //递归
221 // if (node == NULL || search_value = node->m_nValue)
222 // return node;
223 // if (search_value < node->m_nValue)
224 // return _Search(node->m_pLeft);
225 // else
226 // return _Search(node->m_pRight);
227 //非递归
228 while (node && search_value != node->m_nValue) {
229 if (search_value < node->m_nValue)
230 node = node->m_pLeft;
231 else
232 node = node->m_pRight;
233 }
234 return node;
235}
236
237//@brief 显示一棵二叉搜索树
238void BinarySearchTree::_Display(/*iostream &ss, */_Node *node) const
239{
240 if (node)
241 {
242 cout << node->m_nValue << " ";
243 if (node->m_pLeft)
244 {
245 _Display(node->m_pLeft);
246 }
247 if (node->m_pRight)
248 {
249 _Display(node->m_pRight);
250 }
251 }
252}
253
254//@brief 递归释放节点
255void BinarySearchTree::_RecursiveReleaseNode(_Node *node)
256{
257 if (node) {
258 _RecursiveReleaseNode(node->m_pLeft);
259 _RecursiveReleaseNode(node->m_pRight);
260 delete node;
261 }
262}
263
264int main()
265{
266 srand((unsigned)time(NULL));
267 BinarySearchTree bst;
268 //用随机值生成一棵二叉查找树
269 for (int i = 0; i < 10; i++) {
270 bst.Insert(rand() % 100);
271 }
272 bst.Display();
273 cout << endl;
274 //中序遍历
275 // bst.Inorder();
276 // cout << endl;
277 //删除所有的奇数值结点
278 for (int i = 1; i < 100; i += 2)
279 {
280 if (bst.Delete(i))
281 {
282 cout << "### Deleted [" << i << "] ###" << endl;
283 }
284 }
285 //验证删除的交换性
286 // bst.Delete(2);
287 // bst.Delete(1);
288 // bst.Display();
289 // cout << endl;
290 //查找100以内的数，如果在二叉查找树中，则显示
291 cout << endl;
292 for (int i = 0; i < 10; i += 1)
293 {
294 if (bst.Search(i))
295 {
296 cout << "搜索[" << i << "]元素：\t成功" << endl;
297 }
298 }
299 cout << endl;
300 //中序遍历
301 bst.Inorder();
302 return 0;
303}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-06-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录