首页 > 代码库 > BinarySearchTree示例——C++模板实现
BinarySearchTree示例——C++模板实现
数据结构和算法理解很简单，深感算法导论的介绍更是精辟而无累赘。
例如：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 else141 {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 else180 {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 else223 {224 parent_node = node;225 node = node->rchild;226 }227 } 228 // 找到待插入结点parent_node229 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 else237 {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的左孩子不空的话，赋值给x258 else x = y->rchild; //否则，无论是右孩子空不空，都赋值给x259 260 TreeNode<T> *parent_of_y = parent(y);261 262 if (y != _delete_node)263 {264 _delete_node->value = http://www.mamicode.com/y->value;265 x->parent = parent_of_y;266 if (y == parent_of_y->lchild)267 parent_of_y->lchild = x;268 else269 parent_of_y->rchild = x;270 delete y;271 }272 else273 {274 x->parent = parent_of_y;275 if (parent_of_y == NULL)276 {277 node = x;278 279 delete y;280 }281 else282 {283 if (parent_of_y->lchild == y)284 parent_of_y->lchild = x;285 else286 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操作来初始化，并且增大size308 { 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 else339 {340 os << node->value << " "; //输出当前结点的value341 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<< _increase366 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,okay374 BinarySearchTree<int> Bst(BST);375 cout << Bst << endl;376 377 //检测operator=,okay378 BinarySearchTree<int> bst,bsT;379 bsT= bst = Bst;380 cout <<"!"<< bst<<endl;381 cout <<"!"<< bsT << endl;382 383 //检测_mininum _maxinum,okay384 cout << "maxinum" << BST.maxinum()<<endl;385 cout << "mininum" << BST.mininum()<<endl;386 387 //检测 _decrease,okay388 BST.__test();389 390 //检测_search,okay391 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,okay400 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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。