【数据结构】手撕二叉搜索树

目录二叉搜索树的概念二叉搜索树的实现节点类构造函数拷贝构造函数赋值运算符重载析构函数插入函数查找函数删除函数中序遍历二叉搜索树的应用(k和k/v模型 )二叉搜索树的概念⼆叉搜索树⼜称⼆叉排序树它或者是⼀棵空树或者是具有以下性质的⼆叉树若它的左⼦树不为空则左⼦树上所有结点的值都⼩于等于根结点的值若它的右⼦树不为空则右⼦树上所有结点的值都⼤于等于根结点的值它的左右⼦树也分别为⼆叉搜索树⼆叉搜索树中可以⽀持插⼊相等的值也可以不⽀持插⼊相等的值具体看使⽤场景定义后续我们学习map/set/multimap/multiset系列容器底层就是⼆叉搜索树其中map/set不⽀持插⼊相等值multimap/multiset⽀持插⼊相等值例如下面就是一棵二叉搜索树由于二叉搜索树中每个结点左子树上所有结点的值都小于该结点的值右子树上所有结点的值都大于该结点的值因此对二叉搜索树进行中序遍历后得到的是升序序列也就不难理解了。至于什么是中序遍历我在讲解二叉树的时候已经讲解过这里还不清楚的兄弟们可以去看看我以前的文章。二叉搜索树的实现节点类要实现二叉搜索树我们首先需要实现一个结点类结点类当中包含三个成员变量结点值、左指针、右指针。结点类当中只需实现一个构造函数即可用于构造指定结点值的结点。templateclassKstructBSTNode{K _key;BSTNodeK*_left;BSTNodeK*_right;BSTNode(constKkey):_key(key),_left(nullptr),_right(nullptr){}};构造函数我们先定义一个节点对象出来typedefBSTNodeKNode;Node*_rootnullptr;构造函数就把这个祖宗节点初始化BSTree():_root(nullptr){}拷贝构造函数//拷贝树Node*_Copy(Node*root){if(rootnullptr)//空树直接返回returnnullptr;Node*copyNodenewNode(root-_key);//拷贝根结点copyNode-_left_Copy(root-_left);//拷贝左子树copyNode-_right_Copy(root-_right);//拷贝右子树returncopyNode;//返回拷贝的树}//拷贝构造函数BSTree(constBSTreeKt){_root_Copy(t._root);//拷贝t对象的二叉搜索树}赋值运算符重载对于赋值运算符重载函数下面提供两种实现方法先把当前二叉搜索树的节点全部释放再把另外一颗二叉搜索树的所有节点拷贝过来。//释放树中结点void_Destory(Node*root){if(rootnullptr)//空树无需释放return;_Destory(root-_left);//释放左子树中的结点_Destory(root-_right);//释放右子树中的结点deleteroot;//释放根结点}//传统写法constBSTreeKoperator(constBSTreeKt){if(this!t)//防止自己给自己赋值{_Destory(_root);//先将当前的二叉搜索树中的结点释放_root_Copy(t._root);//拷贝t对象的二叉搜索树}return*this;//支持连续赋值}析构函数析构函数完成对象中二叉搜索树结点的释放注意释放时采用后序释放当二叉搜索树中的结点被释放完后将对象当中指向二叉搜索树的指针及时置空即可。//释放树中结点void_Destory(Node*root){if(rootnullptr)//空树无需释放return;_Destory(root-_left);//释放左子树中的结点_Destory(root-_right);//释放右子树中的结点deleteroot;//释放根结点}//析构函数~BSTree(){_Destory(_root);//释放二叉搜索树中的结点_rootnullptr;//及时置空}插入函数根据二叉搜索树的性质其插入操作非常简单如果是空树则直接将插入结点作为二叉搜索树的根结点。如果不是空树则按照二叉搜索树的性质进行结点的插入。若不是空树插入结点的具体操作如下若待插入结点的值小于根结点的值则需要将结点插入到左子树当中。若待插入结点的值大于根结点的值则需要将结点插入到右子树当中。若待插入结点的值等于根结点的值则插入结点失败。如此进行下去直到找到与待插入结点的值相同的结点判定为插入失败或者最终插入到某叶子结点的左右子树当中即空树当中。但是需要注意在连接parent和cur时需要判断应该将cur连接到parent的左边还是右边。//插入函数boolInsert(constKkey){if(_rootnullptr)//空树{_rootnewNode(key);//直接申请值为key的结点作为二叉搜索树的根结点returntrue;//插入成功返回true}Node*parentnullptr;Node*cur_root;while(cur){if(keycur-_key)//key值小于当前结点的值{//往该结点的左子树走parentcur;curcur-_left;}elseif(keycur-_key)//key值大于当前结点的值{//往该结点的右子树走parentcur;curcur-_right;}else//key值等于当前结点的值{returnfalse;//插入失败返回false}}curnewNode(key);//申请值为key的结点if(keyparent-_key)//key值小于当前parent结点的值{parent-_leftcur;//将结点连接到parent的左边}else//key值大于当前parent结点的值{parent-_rightcur;//将结点连接到parent的右边}returntrue;//插入成功返回true}查找函数根据二叉搜索树的特性我们在二叉搜索树当中查找指定值的结点的方式如下若树为空树则查找失败返回nullptr。若key值小于当前结点的值则应该在该结点的左子树当中进行查找。若key值大于当前结点的值则应该在该结点的右子树当中进行查找。若key值等于当前结点的值则查找成功返回对应结点的地址。boolfind(constKkey){Node*cur_root;while(cur){if(cur-_keykey){curcur-_right;}elseif(cur-_keykey){curcur-_left;}else{returntrue;}}returnfalse;}删除函数待删除结点的左子树为空待删除节点右子树节点为空也是一样的处理方法但是如果我们删除的节点是祖宗节点那么祖宗节点没有父节点该怎么办呢//找到了准备删除if(cur-_leftnullptr)//左子树为空{if(_rootcur)//删除的节点是祖宗节点{_rootcur-_right;//删除祖宗节点后让我的右孩子节点成为新的祖宗节点}else{if(parent-_rightcur)//判断删除的节点是父节点的左孩子节点还是右孩子节点{parent-_rightcur-_right;}else{parent-_leftcur-_right;}}deletecur;}elseif(cur-_rightnullptr)//右子树为空{if(_rootcur)//删除的节点是祖宗节点{_rootcur-_left;//删除祖宗节点后让我的左孩子节点成为新的祖宗节点}else{if(curparent-_right)//判断删除的节点是父节点的左孩子节点还是右孩子节点{parent-_rightcur-_left;}else{parent-_leftcur-_left;}}deletecur;}待删除的两个节点都不为空这个时候其实还有一个问题那就是删除的节点如果是祖宗节点呢//找个人替代我的位置//找右子树的最小节点Node*minRightcur-_right;Node*minRightParentcur;//不能写成nullptr,如果不进循环会对minRightParent-_left minRight-_right;空指针解引用while(minRight-_left){minRightParentminRight;minRightminRight-_left;}cur-_keyminRight-_key;if(minRightParent-_leftminRight){minRightParent-_leftminRight-_right;}else{minRightParent-_rightminRight-_right;}deleteminRight;中序遍历如果想要中序遍历我们就需要提供二叉树的祖宗节点但是我们节点是封装起来的但是我们又要在类外用有没有一个方法能不在类外提供祖宗节点就可以完成中序遍历呢有的兄弟有的。我们在类里面再实现一个函数用来调用中序遍历的函数我们知道在类外是可以使用类的成员变量的这个时候我们就可以提供祖宗节点调用中序遍历函数然后我们只需要调用这个调用中序遍历函数的函数即可。voidInOrder(){_InOrder(_root);coutendl;}private:void_InOrder(Node*root){if(rootnullptr){return;}_InOrder(root-_left);coutroot-_key ;_InOrder(root-_right);}二叉搜索树的应用(k和k/v模型 )