前言有关一些二叉树的基础概念可以看看我之前的文章【数据结构】二叉树基本概念及堆的C语言模拟实现虽然那篇文章和本篇文章的关系大概只有二叉与树本文要实现的搜索二叉树主要是以非递归的方式来实现增、删、查1. 搜索二叉树介绍1.1 搜索二叉树概念介绍二叉搜索树也可以叫做搜索二叉树怎么叫取决于你顾名思义它是一颗二叉树但搜索二叉树具有以下几个特殊的性质左子树所有节点 当前节点右子树所有节点 当前节点它的左右⼦树也分别为⼆叉搜索树二叉树可以支持插入相同的值也可以不支持相同的值这点要看使用的场景来决定我这里实现的搜索二叉树并不支持插入相同值的元素1.2 搜索二叉树性能分析根据前面对搜索二叉树性质的观察不难发现这颗树在搜索上有着比较明显的优势这也正对应着它的名字这颗树是为了搜索而生的。当要查找一个元素时理想情况下当这颗树的形状比较的接近满二叉树也就是比较平衡时它的查找就会变得像是二分查找那样效率很高T ( N ) O ( l o g N ) T(N)O(logN)T(N)O(logN)但是当情况变得比较的极端时这个二叉树有可能会退化成一个类似链表的结构就像是如下图这个时候再想去查找里面的某个元素时时间复杂度就为最坏情况下的T ( N ) O ( N ) T(N)O(N)T(N)O(N)但是这种比较极端的情况毕竟比较的少所以它的查找平均时间复杂度为O ( l o g N ) O(logN)O(logN)因此关于搜索二叉树的性能可以总结成下面的表格操作平均情况最坏情况查找O ( l o g N ) O(logN)O(logN)O ( N ) O(N)O(N)插入O ( l o g N ) O(logN)O(logN)O ( N ) O(N)O(N)删除O ( l o g N ) O(logN)O(logN)O ( N ) O(N)O(N)为了解决这种极端的情况有些比较高级的数据结构对搜索二叉树进行了升级使得这颗树获得了自动保持平衡的能力也就是红黑树、AVL树、B树但这里我们先不做介绍想要了解这些高级的数据结构还是先得把基础给打好从实现这个不平衡的搜索二叉树开始后面再慢慢过渡到高级的数据结构2. 搜索二叉树的实现算法逻辑2.1 搜索二叉树插入元素插入元素比较的简单主要是分为两种情况1.当树为空树的时候2.当树不为空那就按照二叉搜索树的性质来走让这个值每遍历到一个结点让这个值和这个结点的值做比较如果值要比较小就往该结点的左孩子走反正如果要大就往该结点的右孩走当找到空位置时就直接插入就可以了3.下面我实现的二叉搜索树是不支持重复元素的所以到时候发现重复元素就直接退出了想要允许重复元素的话也可以往左走还是往右走随你但是一定要保证逻辑一致不然就全乱了2.2 查找元素查找元素相比于插入元素的逻辑来说更加的简单首先从根部的位置开始如果元素比该结点大就往右左如果小就往左走发现相等了就退出并返回true, 如果都找到空了还是没有就说明该树没有这个元素的结点返回一个false即可但是有一点需要注意如果实现的是一颗支持存放相同元素的搜索二叉树时就要把迭代改成DFS并且以中序遍历到的第一个元素为准比如在下面的图中存在着两个结点3那就返回中序遍历的第一个结点也就是1的右孩子2.3 搜索二叉树的删除这里是搜索二叉树的难点也是搜索二叉树比较核心的操作之一这里就先把算法逻辑给交代下。但是实际实现上有很多种细节需要处理也是让我调了挺久且需要分出很多种情况来处理反正我写的时候就代码实现来说我都套了有5层的 if、else 了当然大多数代码就只是在复读机把逻辑想清楚CV一下改改还是很快的。想要删除树的某个结点时主要分为下面的四种情况要删除的结点的左右子树都为空时也就是为叶子结点时这是最好处理的情况直接把该结点删除就可以了比如这里我们想要删除结点1直接delete掉该结点即可2.当要删除的结点N左孩子为空右孩子不为空时我们可以把 N 结点的父亲指向 N 的那个的指针让它直接指向 N 的右孩子3.和第二种情况类似当要删除的结点N右孩子为空左孩子不为空时我们可以把 N 结点的父亲指向 N 的那个的指针让它直接指向 N 的左孩子4.当要删除的结点 N 的左右都不为空时会面临一种尴尬的境地就是删除了 N 之后N 的两个孩子没有安身之地所以我们就不能用上面的两种方法。因此我们需要使用替换法来解决这个问题那么我们要使用哪个结点来替换呢 观察搜索二叉树的性质不能发现想要不破坏搜索二叉树的性质我们只能找到 N 的左子树的最大结点或者是右子树的最小结点然后与 N 结点做替换接着再把 N 替换到的那个位置删除掉即可3. 搜索二叉树的代码实现下面我们就来实现这个搜索二叉树首先先让我们定义出单个结点的结构体与搜索二叉树这个类这里为了更加的灵活且兼容更多的数据类型我这里就都统一实现成模板这样编译器就可以根据我们的需要实例化出我们需要存放指向数据的对象3.1 结点与树的类定义树结点的定义templatetypenameKstructTreeNode{K _key;TreeNodeK*_left;TreeNodeK*_right;TreeNode(constKkey):_key(key),_left(nullptr),_right(nullptr){}};二叉搜索树的定义templatetypenameKclassBSTree{typedefTreeNodeKNode;public://///private:Node*_rootnullptr;};3.2 插入函数boolInsert(constKkey){if(_rootnullptr){_rootnewNode(key);returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else{//实现一共不允许重复元素的二叉树所以//找到相同的元素就直接返回returnfalse;}}curnewNode(key);if(parent-_keykey)parent-_rightcur;elseparent-_leftcur;returntrue;}3.2 查找函数boolFind(constKkey)const{Node*cur_root;while(cur){if(cur-_keykey){curcur-_right;}elseif(cur-_keykey){curcur-_left;}else{returntrue;}}returnfalse;}3.3 删除函数boolErase(constKkey){Node*parentnullptr;Node*cur_root;while(cur){if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else// cur-_key key{if(cur-_leftnullptr){// 处理下边界情况if(cur_root){_rootcur-_right;deletecur;returntrue;}// 如果 cur 是 parent 的左孩子// 就把 parent 的 _left 链接上 cur 的 _rightif(parent-_leftcur){parent-_leftcur-_right;}else{parent-_rightcur-_right;}deletecur;returntrue;}elseif(cur-_rightnullptr){if(cur_root){_rootcur-_left;deletecur;returntrue;}if(parent-_leftcur){parent-_leftcur-_left;}else{parent-_rightcur-_left;}deletecur;returntrue;}else// 要删除的结点有两个孩子的情况{// replaceParent要初始化成 cur, 否则// 当 _root cur 时后面会引发空指针访问Node*replaceParentcur;Node*replacecur-_right;while(replace-_left)// 我这里找的是右子数中最小的{replaceParentreplace;replacereplace-_left;}cur-_keyreplace-_key;if(replaceParent-_leftreplace)replaceParent-_leftreplace-_right;elsereplaceParent-_rightreplace-_right;deletereplace;returntrue;}}}returnfalse;}删除函数这里要考虑一下当 cur _root 时的特殊情况否则就会引发空指针访问的问题剩下的东西我在注释里也有写我这里就不在赘述了3.4 中序遍历、构造拷贝、析构函数、赋值重载// 让他强制生成默认构造BSTree()default;BSTree(constBSTreet){_rootcopy(t._root);}BSTreeKoperator(BSTreeKt){std::swap(this-_root,t._root);return*this;}~BSTree(){_rootDestroy(_root);}voidInOrder()const{_InOrder(_root);std::coutstd::endl;}void_InOrder(constNode*cur)const{if(curnullptr)return;_InOrder(cur-_left);std::coutcur-_key ;_InOrder(cur-_right);}Node*copy(constNode*cur){if(curnullptr){returnnullptr;}Node*newNodenewNode(cur-_key);newNode-_leftcopy(cur-_left);newNode-_rightcopy(cur-_right);returnnewNode;}Node*Destroy(Node*cur){if(curnullptr){returnnullptr;}cur-_leftDestroy(cur-_left);cur-_rightDestroy(cur-_right);deletecur;returnnullptr;}这里要解释一下为什么要专门写Destroy、copy、_InOrder这些小函数首先这些小函数都是被private修饰的而剩下的则全是被public修饰的之所以这样设计是我想要通过递归来实现拷贝、 析构、 遍历 而想要实现这样我又需要穿入_root但这样不安全我不期望外界可以访问到这个_root除了写一个getRoot函数外我还可以通过上面的方法封装一层这样就相对来说比较的安全4. 搜索二叉树key / value 版的实现搜索二叉树key / value 与普通的搜索二叉树的差别很小只不过一个结点中多了value你可以选择这个值是否可以被修改我这里想要value可以被修改所以在Find中我返回那个结点的指针其他普通几乎都是直接 CV 一下上面的带么再简单改改就可以了我这里就直接贴代码了#pragmaonce#includeiostreamnamespaceKey_val{templatetypenameK,typenameVstructTreeNode{K _key;V _value;TreeNodeK,V*_left;TreeNodeK,V*_right;TreeNode(constKkey,constVvalude):_key(key),_value(valude),_left(nullptr),_right(nullptr){}};templatetypenameK,typenameVclassBSTree{typedefTreeNodeK,VNode;public:// 让他强制生成默认构造BSTree()default;BSTree(constBSTreet){_rootcopy(t._root);}BSTreeK,Voperator(BSTreeK,Vt){std::swap(this-_root,t._root);return*this;}~BSTree(){_rootDestroy(_root);}boolInsert(constKkey,constVvalue){if(_rootnullptr){_rootnewNode(key,value);returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else{//实现一共不允许重复元素的二叉树所以//找到相同的元素就直接返回returnfalse;}}curnewNode(key,value);if(parent-_keykey)parent-_rightcur;elseparent-_leftcur;returntrue;}boolErase(constKkey){Node*parentnullptr;Node*cur_root;while(cur){if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else// cur-_key key{if(cur-_leftnullptr){// 处理下边界情况if(cur_root){_rootcur-_right;deletecur;returntrue;}// 如果 cur 是 parent 的左孩子// 就把 parent 的 _left 链接上 cur 的 _rightif(parent-_leftcur){parent-_leftcur-_right;}else{parent-_rightcur-_right;}deletecur;returntrue;}elseif(cur-_rightnullptr){if(cur_root){_rootcur-_left;deletecur;returntrue;}if(parent-_leftcur){parent-_leftcur-_left;}else{parent-_rightcur-_left;}deletecur;returntrue;}else// 要删除的结点有两个孩子的情况{// replaceParent要初始化成 cur, 否则// 当 _root cur 时后面会引发空指针访问Node*replaceParentcur;Node*replacecur-_right;while(replace-_left)// 我这里找的是右子数中最小的{replaceParentreplace;replacereplace-_left;}cur-_keyreplace-_key;cur-_valuereplace-_value;if(replaceParent-_leftreplace)replaceParent-_leftreplace-_right;elsereplaceParent-_rightreplace-_right;deletereplace;returntrue;}}}returnfalse;}// key/value 支持修改 val 所以这里稍作改动返回那个结点Node*Find(constKkey)const{Node*cur_root;while(cur){if(cur-_keykey){curcur-_right;}elseif(cur-_keykey){curcur-_left;}else{returncur;}}returnnullptr;}voidInOrder()const{_InOrder(_root);std::coutstd::endl;}private:void_InOrder(constNode*cur)const{if(curnullptr)return;_InOrder(cur-_left);std::coutcur-_key-:cur-_value ;_InOrder(cur-_right);}Node*copy(constNode*cur){if(curnullptr){returnnullptr;}Node*newNodenewNode(cur-_key,cur-_value);newNode-_leftcopy(cur-_left);newNode-_rightcopy(cur-_right);returnnewNode;}Node*Destroy(Node*cur){if(curnullptr){returnnullptr;}cur-_leftDestroy(cur-_left);cur-_rightDestroy(cur-_right);deletecur;returnnullptr;}Node*_rootnullptr;};}5.总结本篇文章主要还是为了学习 红黑树 、AVL树、B树打基础我们这里实现的搜索二叉树除了删除元素那里有点绕其他的地方也还好几乎都在前面的文章都有涉猎过。完