二叉搜索树

说起二叉树或许每个人都多多少少听过它 但是二叉搜索树是个啥玩意 下面就来简单介绍一下

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3.它的左右子树也分别为二叉搜索树

如图所示:

总而言之就是左子树上的所有结点的值都是小于父亲结点的值的，右子树上的所有结点的值都是大于父亲结点的值的。
因为它的构造就是在插入新结点的时候小于父亲的值的结点往父亲的左边插入，大于父亲的结点往父亲的右边插入。

下面就讲解一下二叉搜索树的增删查，该就没必要说明了。

一、二叉搜索树的插入

上面提到了二叉搜索树的插入得遵循值小的往父亲的左边插入 值大的往父亲的右边插入

下面是二叉搜索树的结点的定义 封装为一个类

//结点类template<classT>structBSTreeNode//每次要插入结点的时候new一个BSTreeNode即可{structBSTreeNode<T>* _left;//每个结点包含左右孩子 和一个值_keystructBSTreeNode<T>* _right;
    T _key;BSTreeNode(const T& key)//初始化列表初始化:_left(nullptr),_right(nullptr),_key(key){}};

需要注意的情况：
1、 如果是第一次插入就是根结点为空 直接插入即可 并且让刚插入的结点做根结点
2、不是第一次插入就再插入的时候从根结点开始往下比较根结点的值和插入结点的值的大小，新增结点值小就往根结点左边插入，大就是往右边插入，等于就说明该值存在，不插入。（一直往下迭代直到找到空结点就停止，说明找到了正确的插入位置）

动图演示：

代码:

template<classT>//模板参数classBSTree{public:typedef BSTreeNode<T> Node;//简化类结点的名称BSTree()//构造函数初始化根节点为空:_root(nullptr){}boolInsert(T key)//插入操作 插入成功返回true 否返回 false{if(_root ==nullptr)//考虑第一次插入根为空的情况{
            _root =newNode(key);//new一个结点作为根结点 并返回truereturntrue;}//走到这里说明不是第一次插入 需要记录一个父亲结点来辅助寻找插入位置的过程
        Node* parent =nullptr;
        Node* cur = _root;
        Node* newnode =newNode(key);//new出新结点方便下面插入while(cur)//从根结点开始往下找正确的插入位置{if(key > cur->_key)//新增结点值大于根结点值往右边找插入位置{
                parent = cur;
                cur = cur->_right;}elseif(key < cur->_key)//小于就往左找{
                parent = cur;
                cur = cur->_left;}else//等于说明这个值已经存在树中 返回false{returnfalse;}}//走到这里说明cur已经为空了 这个空的位置就是新增结点插入的正确位置if(key > parent->_key)//判断新增结点和其父亲的关系 从而知道往父亲左边插入还是右边插入{
            parent->_right = newnode;//大插入在右边}else{
            parent->_left = newnode;//小插入在左边}returntrue;//插入成功返回true}}

二、二叉搜索树的删除

二叉树的删除相比于插入情况和细节就多了
主要分为以下几种情况：
1、要删除的结点的孩子小于二（没有孩子 或者只有一个左孩子或一个右孩子 那么至少有一边是空的），将要删除结点的孩子链接到要删除结点的父亲的左边或右边即可
2、要删除的结点的孩子为2 （两边都不为空既有左孩子又有右孩子）就要用替换法来删除了

第一种情况：要删除的结点的孩子小于二

这种情况比较好处理 值得注意的是
1、找到了要删除的节点后要判断其是他父亲的左孩子还是右孩子然后让其父亲的左边或者右边链接上要删除结点的左孩子或者右孩子
2、如果要删除的结点就是根结点就根结点就要特殊处理，更新根结点。例如根结点左边为空然后要删除根结点就需要让根结点的右孩子来做新的根，反之，如果根结点的右边为空然后要删除根结点就要让根结点的左孩子来当新的根。（这点容易被忽略掉 注意！）

第二种情况：要删除结点的左右孩子都不为空 用替换删除法来解决

上图是基本思想
还需要注意的细节是:左子树的最右为空，或者右子树的最左为空，那么替换结点就没有找到了，这该怎么办呢？
不慌，只要知道中序遍历二叉搜索树出来的是有序的就不难知道，既然左子树的最右为空，那么就让中序遍历顺序中该结点的前一个结点当作替换结点（因为它是距离要删除结点最近的非空结点 左边最近）；反之如果取右子树的最左结点当作替换结点的时候，右子树的最左结点为空，就取中序遍历中右子树的最左结点的后一个结点来当作替换结点即可（因为它是距离删除结点最近的非空结点 右边最近）

画图展示:

这几种情况就是删除的关键！！！
下面看代码:

boolErase(const T& key){//先找到那个值 要有key结点的父亲 方便删除
        Node* cur = _root;
        Node* parent =nullptr;while(cur){//先找要删除的结点的位置if(key > cur->_key){
                parent = cur;
                cur = cur->_right;}elseif(key < cur->_key){
                parent = cur;
                cur = cur->_left;}else{//这里是找到那个值的情况 //走到这里说明找到了给定的值的结点 分情况删除即可//2种情况：//1.该结点的左为空或者右为空或者左右都为空（该结点的子结点个数小于2）//2.该结点的左右都不为空 就要用替换法来删除了//第一种情况处理if(cur->_left ==nullptr)//包含了左右都为空的情况{//这里还有一个问题是如果第一个要删的那个结点是根结点的话那么我们定义的父亲结点就是空结点了 （根节点没有父亲结点）要做特殊处理 让根结点换人if(cur == _root){
                        _root = cur->_right;}else{if(parent->_left == cur)//说明该结点是父亲结点的左孩子{
                            parent->_left = cur->_right;}else{
                            parent->_right = cur->_right;}}delete cur;returntrue;}elseif(cur->_right ==nullptr){//这里也要考虑要删的结点是根结点的情况if(cur == _root){
                        _root = cur->_left;}else{if(parent->_left == cur){
                            parent->_left = cur->_left;}else{
                            parent->_right = cur->_left;}}delete cur;//置不置空都可以 反正这里的cur都是局部变量外面是访问不到的returntrue;}//第二种情况else{//根据推理可以用要删除结点的左子树的最右边的孩子代替要删除的结点或者用其右子树的最左边的孩子代替 都可以保证搜索二叉树的结构不被破坏//第一步找替换的结点
                    Node* RightMin = cur->_right;//Node* parent = nullptr;//考虑不周的写法
                    Node* parent = cur;while(RightMin->_left){
                        parent = RightMin;
                        RightMin = RightMin->_left;}//考虑不周的写法 因为//int val = RightMin->_key;//parent->_left = RightMin->_right;//因为RightMin是右子树中的最左边的 其可能右边还有结点 要把右边的结点于父亲结点连上//cur->_key = val;//delete RightMin;int val = RightMin->_key;if(parent->_left == RightMin){
                        parent->_left = RightMin->_right;}else//不一定是parent的左就是RightMin 如果上面的while循环根本就没进去就会出现parent的右是RightMin的情况 {
                        parent->_right = RightMin->_right;}
                    cur->_key = val;delete RightMin;returntrue;}}}returnfalse;//走到这里说明没有找到要删除的结点返回false}

三、二叉搜素树的查找

查找就比较简单了 插入和删除中就有查找的功能 就不多解释了
就是从根结点开始迭代往下找 如果新增结点的值比当前结点的值大就往当前结点的右边找，小就往左边找，相等就是找到了。

代码：

//非递归写法
Node*Find(const T& key){
        Node* cur = _root;while(cur){if(key > cur->_key){
                cur = cur->_right;}elseif(key < cur->_key){
                cur = cur->_left;}else{return cur;}}returnnullptr;}//递归写法
Node*_FindR(const Node* root,const T& key)//子函数{if(nullptr== root){returnnullptr;}elseif(key > root->_key){return_FindR(root->_right, key);}elseif(key < root->_key){return_FindR(root->_left, key);}else{return root;}}

    Node*FindR(const T& key){return_FindR(_root, key);}

Node*FindR(const T& key)//主函数 写子函数是未了在调用的时候不用自己传根结点过去{return_FindR(_root, key);//return _Find(_root,key);}

奉上源码:

#define_CRT_SECURE_NO_WARNINGS#include<iostream>usingnamespace std;template<classT>structBSTreeNode{structBSTreeNode<T>* _left;structBSTreeNode<T>* _right;
    T _key;BSTreeNode(const T& key):_left(nullptr),_right(nullptr),_key(key){}};template<classT>classBSTree{public:typedef BSTreeNode<T> Node;BSTree()//构造函数:_root(nullptr){}
    Node*copy(const Node* copyroot){if(copyroot ==nullptr)returnnullptr;
        Node* newroot =newNode(copyroot->_key);
        newroot->_left=copy( copyroot->_left);
        newroot->_right=copy( copyroot->_right);return newroot;}BSTree(const BSTree<T>& Bst)//拷贝构造{//得保证是深拷贝
        _root=copy(Bst._root);}
    BSTree<T>&operator=(BSTree<T> Bst)//现代写法{swap(Bst._root, _root);return*this;}voiddestory(const Node* root){if(root ==nullptr){return;}destory(root->_left);destory(root->_right);delete root;}~BSTree()//析构函数{//一个节点一个节点去释放空间destory(_root);
        _root =nullptr;}//插入数据boolInsert(const T& key){if(_root ==nullptr){
            _root =newNode(key);returntrue;//记得要返回不要继续}
        Node* cur = _root;
        Node* parent =nullptr;while(cur){if(key > cur->_key){
            parent = cur;
            cur = cur->_right;}elseif(key < cur->_key){
            parent = cur;
            cur = cur->_left;}else{returnfalse;}}
        Node* newnode =newNode(key);//这里是要判断大小而不是指向关系 插入的数比父亲大就放到右边否则放左边if(key>parent->_key){
            parent->_right = newnode;}else{
            parent->_left = newnode;}returntrue;}

    Node*Find(const T& key){
        Node* cur = _root;while(cur){if(key > cur->_key){
                cur = cur->_right;}elseif(key < cur->_key){
                cur = cur->_left;}else{return cur;}}returnNULL;}boolErase(const T& key){//先找
        Node* cur = _root;
        Node* parent =nullptr;while(cur){if(key > cur->_key){
                parent = cur;
                cur = cur->_right;}elseif(key < cur->_key){
                parent = cur;
                cur = cur->_left;}else{//然后分三种情况来判断 左为空 右为空 左右都不为空if(cur->_left ==nullptr){//当只有一个根结点待删除的时候 根节点是没有父亲结点的 if(cur == _root){
                        _root = cur->_right;//return true;}else{if(parent->_left == cur){
                            parent->_left = cur->_right;}else{
                            parent->_right = cur->_right;}}delete cur;returntrue;}elseif(cur->_right ==nullptr){if(cur == _root){
                        _root = cur->_left;//    return true;}else{if(parent->_left == cur){
                            parent->_left = cur->_left;}else{
                            parent->_right = cur->_left;}}delete cur;returntrue;}else//左右都不为空的情况{//找替换结点
                    Node* RightMin = cur->_right;
                    Node* parent = cur;while(RightMin->_left){
                        parent = RightMin;
                        RightMin = RightMin->_left;}//走到这里就找到了替换节点了int val = RightMin->_key;if(parent->_left == RightMin){
                        parent->_left = RightMin->_right;}else{
                        parent->_right = RightMin->_right;}

                    cur->_key = val;delete RightMin;returntrue;}}}returnfalse;//妈的括号害死人 少个括号还我查了三遍 心态爆炸 fuck}//插入删除查找的i递归写法bool_InsertR( Node*& root,const T& key){if(root ==nullptr){
            root =newNode(key);returntrue;}if(key > root->_key){_InsertR(root->_right, key);}elseif(key < root->_key){_InsertR(root->_left, key);}else{returnfalse;}}boolInsertR(const T& key){return_InsertR(_root, key);}
    Node*_FindR(const Node* root,const T& key){if(nullptr== root){returnnullptr;}elseif(key > root->_key){return_FindR(root->_right, key);}elseif(key < root->_key){return_FindR(root->_left, key);}else{return root;}}

    Node*FindR(const T& key){return_FindR(_root, key);}bool_EraseR(Node*& root,const T& key){if(root ==nullptr)returnfalse;elseif(key > root->_key){return_EraseR(root->_right, key);}elseif(key < root->_key){return_EraseR(root->_left, key);}else{//说明找到了 这里的root是引用 是其父亲的左或者右结点的引用 这样就不用去找父亲结点了 if(root->_left ==nullptr){
                Node* del = root;
                root = root->_right;delete del;}elseif(root->_right ==nullptr){
                Node* del = root;
                root = root->_left;delete del;}else{
                Node* RightMin = root->_right;while(RightMin->_left){
                    RightMin = RightMin->_left;}int val = RightMin->_key;_EraseR(root->_right, val);
                root->_key = val;}returntrue;}}boolEraseR(const T& key){return_EraseR(_root, key);}void_Inorder(Node* root){if(root ==nullptr){return;}_Inorder(root->_left);
        cout << root->_key <<" ";_Inorder(root->_right);}voidInorder(){_Inorder(_root);
        cout << endl;}private:
    Node* _root;};

本文结束~