BinarySearchTree示例——C++模板实现
浏览数：24 /
时间：2015年06月08日
数据结构和算法理解很简单，深感算法导论的介绍更是精辟而无累赘。
例如：1. 直接切入二叉搜索树，而不是从树开始介绍各种繁琐的表示方式，最后的重点结果还是二叉搜索和几种平衡树，算法导论介绍知识的时候数学性虽强，但应用性也十足，它的 应用性不在于给你代码，而在于给你应用的场景，告诉你各种结构的优劣和代价，这才是学习数据结构和算法应该掌握的精华，而不在一些教材上展示的可以称之为垃圾的代 码上，实际上，关于数据结构的实现代码，工业级的STL源码可以给你最高屋建瓴的精华。
2. 遍历方法仅重点分析中序遍历，为何？因为按照二叉搜索树的性质其中序即使orderd，其它序也有作用，比如某一道习题提到的位二叉树，其pre-order才是orderd，但 比上来让你实现几个遍历，滚瓜烂熟之后也不知在何处用（只会用来display数据除外）；
3. 不止一次在网上看到人们评价算导的数据结构部分过于简单，又跑回去啃严版教材，实乃买椟还珠，为何他们觉得简单，我简单分析一下，认为他们一不做或者不思考习题， 对于二叉搜索树而言，最难的（其实也不难）地方在于迭代遍历（pre，in，post），算法导论的习题中不仅有，而且还提出一种使用stack模拟，另一种不借助stack，要求 读者独立完成。倘使不做，自然无法得其中奥义，只能回去啃别人代码，一读便懂，回头即忘。
所以就我个人阅读感受而言，算法导论一书造诣颇高，比大多数相关书籍不知道高明多少，十分推荐。
我在以前只学习数据结构的时候就已经用模板实现了二叉搜索树，但是看完算法导论再加之一些STL源码的阅读体验，感觉之前的代码臭不可闻，接口错乱，实现冗杂，实乃错误之典范，究其根本还在于理解了但是不明白用来干嘛。当然，我偶然搜索了一下，发现大多数学习者在互相抄袭，完全相同的代码和用词出现在了好多的博文上，而其抄袭的代码本身也不是什么优秀之作。既然是学习，不管好与坏，自己做得才有进步，复制粘贴就。。。
所以最近得空重新实现一下，虽然还是有诸多不满之处，但比之前要好很多了。
下面在代码中分析一下：（设置为虚函数的函数是要做red-black tree中重新给出实现的操作）
算法的部分不难，理解之后还有很多设计上的问题，即接口和实现的分离、node类和tree类之间的耦合和内聚等等。
自己从头撸一个，还是有一些好处的。
1 #include<iostream> 2 using namespace std; 3 4 //结点类 5 template<typename T> 6 class TreeNode 7 { 8 //声明为二叉搜索树的友元类 9 template<class T> friend class BinarySearchTree; 10 //方便<<操作符访问结点成员 11 template<typename T> friend ostream& operator<<(ostream &os, BinarySearchTree<T>&BST); 12 13 private: 14 T value; 15 TreeNode<T>* lchild; 16 TreeNode<T>* rchild; 17 TreeNode<T>* parent;//带parent结点要方便的多 18 19 TreeNode<T>* _increase();//自增，即中序下的后继 20 TreeNode<T>* _decrease();//自减，即中序下的前驱 21 public: 22 //三个构造函数 23 TreeNode() :value(0), lchild(NULL), rchild(NULL),parent(NULL){} 24 TreeNode(T v) :value(v), lchild(NULL), rchild(NULL),parent(NULL){} 25 TreeNode(TreeNode<T> &node) :value(node.value), lchild(node.lchild), rchild(node.rchild),parent(node.parent){} 26 virtual ~TreeNode(){} //析构函数设置为虚函数 27 void _test_display() //此函数只是测试使用，应该删去 28 { 29 cout << "value: " << this->value<<" "; 30 if (this->lchild!=NULL) 31 cout <<"lchild: "<< this->lchild->value<<" "; 32 else cout << "lchild: NULL"<<" "; 33 if (this->rchild != NULL) 34 cout << "rchild: " << this->rchild->value << " "; 35 else cout << "rchild: NULL" << " "; 36 if (this->parent != NULL) 37 cout << "parent: " << this->parent->value << " "; 38 else cout << "parent: NULL" << " "; 39 cout << endl; 40 } 41 42 }; 43 44 //二叉搜索树类 45 template<typename T> 46 class BinarySearchTree 47 { 48 49 private: 50 TreeNode<T> *root; //根节点 51 int size; //结点数量 52 53 TreeNode<T>* _copy(TreeNode<T> *node,TreeNode<T>* q); //私有函数，node表示复制以node为根节点的树，参数q实际上指向node的父节点，是实现的小技巧 54 TreeNode<T>* _mininum(TreeNode<T>* node); //私有函数，找到以node为根节点的树中的最小结点 55 TreeNode<T>* _maxinum(TreeNode<T>* node); 56 57 virtual TreeNode<T>* _insert(T& value,TreeNode<T>* node);//私有函数，用于实现Insert操作 58 virtual void _delete(TreeNode<T>* _delete_node,TreeNode<T>* node);//私有函数，用于实现Delete操作 59 TreeNode<T>* _search(T& value, TreeNode<T>* node); //私有函数，用于实现Search操作 60 virtual void _init(T* array,int length); //通过数组初始化二叉搜索树 61 virtual void _clear(TreeNode<T>* node); //清空node为根节点的树 62 63 64 65 public: 66 //构造和析构函数 67 BinarySearchTree() :root(NULL), size(0){} 68 BinarySearchTree(T* array, int length) { _init(array, length); } 69 BinarySearchTree(BinarySearchTree<T> &tree){ root = _copy(tree.root, NULL); size = tree.size; } 70 virtual ~BinarySearchTree() { _clear(root); size = 0; } 71 //赋值操作符的重载 72 virtual BinarySearchTree<T>& operator=(BinarySearchTree<T> &tree){ _clear(root); root = _copy(tree.root, NULL); size = tree.size; return *this; } 73 //判断树是否为空 74 bool isEmpty() { return size == 0; } 75 //返回树中结点个数 76 int Size() { return size; } 77 //基本操作，Insert、Delete、Search 78 virtual TreeNode<T>* Insert(T& value){ return _insert(value, root); } 79 virtual void Delete(TreeNode<T>* node){ return _delete(node, root); } 80 TreeNode<T>* Search(T& value){ return _search(value, root); } 81 82 //返回树中value最大和最小的结点的value 83 T& mininum(){ return _mininum(root)->value; } 84 T& maxinum(){ return _maxinum(root)->value; } 85 //返回某个节点的parent 86 TreeNode<T>* parent(TreeNode<T> *node){ return node->parent; } 87 //<<操作符必须设置为友元，不可以是成员 88 template<typename T> friend ostream& operator<<(ostream &os, BinarySearchTree<T>&BST); 89 90 //一个测试函数 91 void __test(){ cout << "测试_ decrease" << --(this->root->rchild->lchild->lchild)->value << endl; }; 92 93 }; 94 95 template<typename T> 96 TreeNode<T>* BinarySearchTree<T>::_copy(TreeNode<T>* node,TreeNode<T>* q) 97 { 98 //这里q保存node的父节点，调用时初始化为NULL（root的parent为NULL） 99 100 if (node == NULL) 101 return NULL; 102 103 TreeNode<T>* p = new TreeNode<T>(node->value); 104 p->parent = q; 105 p->lchild = _copy(node->lchild,p);//递归复制 106 p->rchild = _copy(node->rchild,p); 107 return p; 108 } 109 110 111 template<typename T> 112 TreeNode<T>* BinarySearchTree<T>::_mininum(TreeNode<T>* node)//最左端结点为最小 113 { 114 TreeNode<T> * p = node; 115 TreeNode<T>* q=NULL; 116 while (p != NULL) 117 { 118 q = p; 119 p = p->lchild; 120 } 121 return q; 122 } 123 template<typename T> 124 TreeNode<T>* BinarySearchTree<T>::_maxinum(TreeNode<T>* node)//最右端结点为最大 125 { 126 TreeNode<T>* p = node; 127 TreeNode<T>* q = NULL; 128 while(p != NULL) 129 { 130 q= p; 131 p = p->rchild; 132 } 133 return q; 134 } 135 template<typename T> 136 TreeNode<T>* TreeNode<T>::_increase() 137 { 138 if (this == NULL) 139 return NULL; 140 else 141 { 142 if (this->rchild != NULL) //当前结点如果有右孩子，则后继为右子树中最小的结点 143 { 144 TreeNode<T> * p = this->rchild; 145 TreeNode<T>* q=p; 146 while (p != NULL) 147 { 148 q= p; 149 p = p->lchild; 150 } 151 152 return q; 153 } 154 else //否则，则向上回溯，直到第一次出现 q 是 p 的左孩子结点为止 155 { 156 TreeNode<T> *q = this; 157 TreeNode<T> *p = this->parent; 158 //cout<<"parent:" << p->value << endl; 159 //cout <<"cur: "<< q->value << endl; 160 while(q != p->lchild) 161 { 162 q = p; 163 p = p->parent; 164 if (p == NULL) 165 break; 166 } 167 //cout << "parent: " << p->value << endl; 168 169 return p; 170 } 171 } 172 173 } 174 template<typename T> 175 TreeNode<T>* TreeNode<T>::_decrease() 176 { 177 if (this == NULL) 178 return NULL; 179 else 180 { 181 if (this->lchild != NULL) //当前结点如果有左孩子，则后继为右子树中最大的结点 182 { 183 TreeNode<T> *p = this->lchild; 184 TreeNode<T> *q = p; 185 while (p != NULL) 186 { 187 q = p; 188 p = p->rchild; 189 } 190 return q; 191 } 192 else //否则，则向上回溯，直到第一次出现 q 是 p 的右孩子结点为止 193 { 194 TreeNode<T> *q = this; 195 TreeNode<T> *p = this->parent; 196 while (q != p->rchild) 197 { 198 q = p; 199 p = p->parent; 200 if (p == NULL) 201 break; 202 } 203 return p; 204 } 205 } 206 207 } 208 209 template<typename T> 210 TreeNode<T>* BinarySearchTree<T>::_insert(T& value, TreeNode<T>* node) //insert操作的返回值为指向插入结点的指针 211 { 212 TreeNode<T> *p = new TreeNode<T>(value); 213 TreeNode<T> *parent_node = NULL; 214 215 while (node != NULL) 216 { 217 if (p->value < node->value) 218 { 219 parent_node = node; 220 node = node->lchild; 221 } 222 else 223 { 224 parent_node = node; 225 node = node->rchild; 226 } 227 } 228 // 找到待插入结点parent_node 229 if (parent_node != NULL) 230 { 231 p->parent = parent_node; 232 if (p->value < parent_node->value) 233 { 234 parent_node->lchild = p; 235 } 236 else 237 { 238 parent_node->rchild = p; 239 } 240 } 241 else //当前树为空 242 { 243 root=p; 244 } 245 return p; 246 247 } 248 template<typename T> 249 void BinarySearchTree<T>::_delete(TreeNode<T>* _delete_node, TreeNode<T>* node) 250 { 251 TreeNode<T> *y, *x; 252 if (_delete_node->lchild == NULL || _delete_node->rchild == NULL) //如果待删除结点有一个孩子或者没有孩子，那么要被移除的结点就是它自己 253 y = _delete_node; 254 else y = _delete_node->_increase(); //如果有两个结点，那么要移除的结点就是它的后继（然后把它的后继的value赋值给它） 255 256 if (y->lchild != NULL) 257 x = y->lchild; //如果y的左孩子不空的话，赋值给x 258 else x = y->rchild; //否则，无论是右孩子空不空，都赋值给x 259 260 TreeNode<T> *parent_of_y = parent(y); 261 262 if (y != _delete_node) 263 { 264 _delete_node->value = y->value; 265 x->parent = parent_of_y; 266 if (y == parent_of_y->lchild) 267 parent_of_y->lchild = x; 268 else 269 parent_of_y->rchild = x; 270 delete y; 271 } 272 else 273 { 274 x->parent = parent_of_y; 275 if (parent_of_y == NULL) 276 { 277 node = x; 278 279 delete y; 280 } 281 else 282 { 283 if (parent_of_y->lchild == y) 284 parent_of_y->lchild = x; 285 else 286 parent_of_y->rchild = x; 287 delete y; 288 } 289 } 290 291 } 292 template<typename T> 293 TreeNode<T>* BinarySearchTree<T>::_search(T& value, TreeNode<T>* node) //search是其最擅长的操作，返回值为找到结点的指针 294 { 295 TreeNode<T>* p = node; 296 while (p != NULL) 297 { 298 if (value < p->value) 299 p = p->lchild; 300 else if (value > p->value) 301 p = p->rchild; 302 else return p; 303 } 304 return NULL; 305 } 306 template<typename T> 307 void BinarySearchTree<T>::_init(T* array,int length) //反复调用insert操作来初始化，并且增大size 308 { 309 310 for (int i = 0; i < length; ++i) 311 { 312 _insert(array[i], root); 313 ++size; 314 } 315 } 316 317 template<typename T> 318 void BinarySearchTree<T>::_clear(TreeNode<T>* node) //递归调用来删除 319 { 320 if (node == NULL) 321 return; 322 323 TreeNode<T>* p = node->lchild; 324 TreeNode<T>* q = node->rchild; 325 delete node; 326 _clear(p); 327 _clear(q); 328 } 329 330 template<typename T> 331 ostream& operator<<(ostream &os, BinarySearchTree<T>& BST) //这里其实是一个迭代版（不用辅助stack）的方法 332 { 333 TreeNode<T>* node = BST.root; 334 while (true) 335 { 336 if (node->lchild != NULL) //一直访问到当前最左边结点 337 node = node->lchild; 338 else 339 { 340 os << node->value << " "; //输出当前结点的value 341 while (node->rchild == NULL) //如果无右孩子，则访问其后继，注意这里是循环 342 { 343 344 node=node->_increase(); 345 346 if (node != NULL) 347 os << node->value << " "; 348 else break; 349 } 350 if (node !=NULL) //如果有右孩子，访问其右孩子（这里是一个尾递归优化而来的迭代，容易理解） 351 { 352 node = node->rchild; 353 } 354 else break; 355 356 } 357 358 } 359 return os; 360 } 361 int main() 362 { 363 const int length = 9; 364 int array[length] = { 13,9,17,5,12,15,18,2,19}; 365 //检测_init _insert operator<< _increase 366 BinarySearchTree<int> BST(array, length); 367 cout <<"BST: "<< BST << endl; 368 int v = 14; 369 BST.Insert(v); 370 cout<<"BST insert one node with value 14: " << BST << endl; 371 372 373 //检测_copy,okay 374 BinarySearchTree<int> Bst(BST); 375 cout << Bst << endl; 376 377 //检测operator=,okay 378 BinarySearchTree<int> bst,bsT; 379 bsT= bst = Bst; 380 cout <<"!"<< bst<<endl; 381 cout <<"!"<< bsT << endl; 382 383 //检测_mininum _maxinum,okay 384 cout << "maxinum" << BST.maxinum()<<endl; 385 cout << "mininum" << BST.mininum()<<endl; 386 387 //检测 _decrease,okay 388 BST.__test(); 389 390 //检测_search,okay 391 TreeNode<int> *p=BST.Search(array[0]); 392 p->_test_display(); 393 p = BST.Search(array[7]); 394 p->_test_display(); 395 p = BST.Search(array[8]); 396 p->_test_display(); 397 398 399 //检测_delete,okay 400 p = BST.Search(array[2]); 401 BST.Delete(p); 402 cout << "delete the node with value 17"<<endl; 403 cout << BST << endl; 404 405 //测试size 406 cout <<"BST size: "<< BST.Size() << endl; 407 cout <<"bsT size: "<< bsT.Size() << endl; 408 system("pause"); 409 410 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
