STL源码笔记(17)—二叉排序树BST(C++封装)
stl中还有一类非常重要的容器,就是关联容器,比如map啊set啊等等,这些容器说实话,在应用层上还不能完全得心应手(比如几种容器效率的考虑等等),更别说了,因此这一部分打算稳扎稳打,好好做做笔记研究一番。
说到关联容器,我们想到了什么avl树,红黑树等等,但大多时候我们仅仅局限于知道其名字,或者知道其概念,俗话说“talk is cheap,show me the code”,因此,我打算从他们的祖爷爷二叉排序树开始下手。(其实,侯老师的书上也是这么安排的哈)
1.概念
1.任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
2.任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
3.任意节点的左、右子树也分别为二叉查找树;
4.没有键值相等的节点。
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为
2.性质
1.中序遍历是一个升序的有序序列。
2.搜索、插入、删除的复杂度等于树高,期望
3.二叉排序树的实现
既然看到此,不如试着实现一下二叉排序树,主要需要包含这些操作:构建二叉排序树输入一个序列输出一个二叉排序树,插入、删除节点。
写代码之前考虑的问题:
1.二叉排序树的插入一定是在叶子节点处。
2.二叉排序树的删除需要考虑三种情况:
a)待删除节点在叶子节点处
直接另其父节点相应指针制空,并删除该节点即可。
b)待删除节点只含有一个孩子(左子树为空或者右子树为空)
将待删除节点父节点对应指针指向待删除节点的孩子节点。
c)待删除节点即包含左右孩子都不为空
找到待删除节点的右子树的最小值(右子树一路向左),并将该值替换待删除节点的值,最后删除最小值原本所在位置的节点(叶子节点)。3.二叉排序树的中序遍历是升序。
4.摈弃以前的c语言写法,我这次想把bst封装成一个c++类,虽然困难重重,勉强实现了吧。
5.既然是c++类,在析构函数中做所有节点内存释放处理(最后一个根节点需要特殊处理)。
上述5个问题中除了对c++的熟悉程度外,涉及bst算法部分最麻烦的就是删除操作了,因为它考虑的情况比较多,这里贴出侯老师书中的示意图方便理解:
目标节点只有一个孩子节点
喎? f/ware/vc/"="" target="_blank" class="keylink">vcd4ncjxoncbpzd0="目标节点有两个子节点">目标节点有两个子节点
代码
编译运行环境:visual studio 2013,windows 7 32 bits
(1)二叉排序树的节点数据结构
//bstnode.h #ifndef __bstnode_h__ #define __bstnode_h__ #include class bstnode{ public: bstnode(); bstnode(int val); int value; bstnode *lchild; bstnode *rchild; }; #endif //-------------------------------------------- //-------------------------------------------- //-------------------------------------------- //bstnode.cpp #include "bstnode.h" bstnode::bstnode() { value = 0; lchild = null; rchild = null; } bstnode::bstnode(int val) { value = val; lchild = null; rchild = null; }
(2)二叉排序树的c++类封装
//bst.h #ifndef __bst_h__ #define __bst_h__ #include "bstnode.h" #include #include class bstnode; class bst { //说明: //为了数据结构私有化,不为外部访问,这里提供一些私有内部函数实现真正的操作以"__"开头。 //对于public的接口来说,只需要直接调用内部函数即可 private: bstnode * bstroot;//二叉排序树数据结构 bstnode * __search(bstnode* root,const int& key);//查找关键字 bstnode * __treemin(bstnode*const root,bstnode *&parent);//返回当前节点的最小孩子(一路向左) bstnode * __treemax(bstnode*const root);//查找最大值(未实现) bool __insert( const int &key);//插入节点 bool __delete(const int &key);//删除删除 bool __isleaf(bstnode* const &);//判断是否是叶子节点 bool __isnodewithtwochild(bstnode * const &);//判断是否有两个孩子 void __inordertraversal(bstnode *root,std::vector&result);//中序遍历 void __deleteallnodes(bstnode *root);//删除所有节点 public: //构造函数 bst();//默认构造函数 bst(std::vectorarr); bst(int *arr, int len); //析构函数 ~bst(); bool isempty() const;//判断树空 bool search(const int &key);//查找关键字是否存在的对外接口 bool insert(const int &key);//插入节点的外部接口 bool delete(const int &key);//删除节点的外部接口 void inordertraversal(std::vector&);//中序遍历的外部接口 }; #endif
(3)二叉排序树c++类实现部分
//bst.cpp #include "bst.h" //判断树空 bool bst::isempty() const { return bstroot == null; } //判断是否是叶子节点(删除部分用到) bool bst::__isleaf(bstnode*const & root) { if ((root->lchild == null) && (root->rchild == null)) return true; else return false; } //判断节点是否有两个孩子(删除部分用到) bool bst::__isnodewithtwochild(bstnode * const & root) { if (root->lchild != null &&root->rchild != null) return true; else return false; } //找到当前节点为根的子树中的最小值(删除部分用到,因此返回其父节点和当前节点) bstnode * bst::__treemin(bstnode*const root,bstnode *&parent) { bstnode * curr = root; while (curr->lchild != null) { parent = curr; curr = curr->lchild; } return curr; } //删除节点内部实现 bool bst::__delete(const int &key) { bool found = false;//找到待删除的元素 if (isempty()) { std::cerr << "binary search tree is empty" << std::endl;//bst为空 return false; } bstnode * curr = bstroot; bstnode *parent = null; while (curr != null)//查找待删除节点 { if (key == curr->value) { found = true; break; } else { parent = curr; if (key < curr->value) curr = curr->lchild; else curr = curr->rchild; } } if (!found) { std::cerr << "keyvalue not found" << std::endl; return false; } if (null == parent)//删除最后一个节点(根节点需要特殊处理) { bstroot = null; delete curr; return true; } //对于待删除的节点有三种可能: //1.叶子节点 //2.只包含左子树或者右子树(单个孩子) //3.既包含左子树又包含右子树 //删除节点的时候需要分3种情况进行考虑 if (__isleaf(curr))//叶子节点 { if (parent->lchild == curr) parent->lchild = null; else parent->rchild = null; delete curr; return true; }//end if else if (__isnodewithtwochild(curr))//有两个孩子的节点 { //以当前节点的右子树中的最小值取代它 bstnode*parent=curr; bstnode *tmp = __treemin(curr->rchild,parent); curr->value = tmp->value; if (parent->rchild == tmp) parent->rchild = null; else parent->lchild = null; delete tmp; return true; }//end else-if else//只有一个孩子的节点 { if (curr->lchild != null)//只有左孩子 { if (parent->lchild == curr) { parent->lchild = curr->lchild; delete curr; return true; } else { parent->rchild = curr->lchild; delete curr; return true; } } if (curr->rchild != null)//只有右孩子 { if (parent->lchild == curr) { parent->lchild = curr->rchild; delete curr; return true; } else { parent->rchild = curr->rchild; delete curr; return true; } } }//end else return false; } //删除操作的外部接口 bool bst::delete(const int &key) { return __delete(key); } //插入节点的内部实现,插入操作一定都在叶子节点处。 bool bst::__insert(const int & key) { bstnode* t = new bstnode(key);//临时节点 bstnode*parent = null; if (isempty())//新树 { bstroot = t; return true; } else { bstnode* curr; curr = bstroot; while (curr) { //插入位置都位于叶子节点处 parent = curr; if (t->value > curr->value) curr = curr->rchild; else curr = curr->lchild; } if (t->value < parent->value) { parent->lchild = t; return true; } else { parent->rchild = t; return true; } } return false; } //插入节点的外部接口 bool bst::insert(const int &key) { return __insert(key); } //构造函数 bst::bst()//默认构造函数 { bstroot = null; } bst::bst(int*arr, int len)//数组构造 { bstroot = null; for (int i = 0; i < len; i++) { __insert(*(arr + i)); } } bst::bst(std::vectorarr)//容器构造 { bstroot = null; for (int i = 0; i < (int)arr.size(); i++) { __insert(arr[i]); } } //内部查找函数 //递归调用 bstnode* bst::__search(bstnode*root,const int& key) { if (null == root) return null; if (key == root->value) return root; else if (key < root->value) return __search(root->lchild, key); else return __search(root->rchild, key); } //查找函数接口 bool bst::search(const int& key) { bstnode*t = __search(bstroot, key); return t == null ? false : true; } //中序遍历内部实现 void bst::__inordertraversal(bstnode *root,std::vector&result) { if (null == root) return; __inordertraversal(root->lchild, result); std::cout << root->value << " "; result.push_back(root->value); __inordertraversal(root->rchild, result); } //中序遍历接口,vector保存遍历结果 void bst::inordertraversal(std::vector&result) { __inordertraversal(bstroot, result); } //删除所有节点(析构用) void bst::__deleteallnodes(bstnode *root) { if (root == null) { return; } __deleteallnodes(root->lchild); __deleteallnodes(root->rchild); __delete(root->value); } //析构函数 bst::~bst() { bstnode*curr = bstroot; __deleteallnodes(curr); }
(4)二叉排序树的测试代码
//main.cpp #include "bst.h" int main() { std::vectorvec = { 8,6,2,5,1,3,7 }; bst bst(vec); bst.delete(9);//not found bst.insert(4); bool found=bst.search(4); if (!found) std::cout << "not found" << std::endl; else std::cout << "found!" << std::endl; std::vectorresult; bst.inordertraversal(result); std::cout << std::endl; for (int i = 0; i < result.size(); i++) { std::cout << result[i] << " "; } std::cout << std::endl; system("pause"); return 0; }
喎?>
上一篇: 日本为何敢侵略中国?看看日本绘制的中国地图就知道了!
下一篇: 为什么好朋友之间的关系会变淡?