【c++篇】：二叉搜索树--有序存储与高效查找的关键

🕗 发布于 2024-11-22 02:32 c++ 开发语言

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：c++篇–CSDN博客

在这里插入图片描述

文章目录

前言
一.二叉搜索树的概念和性质
二.模拟实现
三.完整代码

前言

在之前的初阶数据结构中，我们已经了解过一点关于二叉树的概念和使用，这里我们将要了解一个新的二叉树–二叉搜索树。二叉搜索树也是一种树形结构。

学习二叉搜索树是为了后面学习map和set进行铺垫，有助于我们更好的理解map和set的特性。其次二叉树中有的部分OJ题使用C语言写起来会比较麻烦，而在我们学过c++之后在去尝试写这些OJ题就会非常方便，废话不多说，让我们步入正题，开始学习二叉搜索树。

一.二叉搜索树的概念和性质

二叉搜索树(Binary Search Tree，简称BST)是一种特殊的二叉树，二叉搜索树又称二叉排序树或者二叉查找树，可以是空树，如果不是空树时，具有以下性质：

有序性：

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

递归性：

它的左右子树也分别为二叉搜索树

二叉搜索树的有序性使得二叉搜索树在查找，插入和删除操作上具有高效性。递归性保证了整个树的结构一致性。

在这里插入图片描述

这里查找，插入和删除等操作我们直接通过模拟实现二叉搜索树来详细讲解

二.模拟实现

基本框架

代码实现：

#include<iostream>
#include<algorithm>
using namespace std;

//树的节点类封装
template<class K>
class BSTreeNode{
public:
    //构造函数
    BSTreeNode(const K& key)
    :_left(nullptr)
    ,_right(nullptr)
    ,_key(key)
    {}
    
    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;
    k _key;
};

//二叉搜索树类的封装
template<class K>
class BSTree{
    //重定义节点类型为Node
    typedef BSTreeNode<K> Node;
    
public:
    //构造函数
    BSTree()
    :_root(nullptr)
    {}
    
    //....其他成员函数
    
private:
    Node* _root;
}

实现原理：
- 二叉搜索树中每个树的节点都包含指针域和数据域，指针域中有两个节点指针分别指向_left左子结点和_right右子节点，数据域中存储的是_key节点数据，通过类将节点进行封装
- 二叉搜索树中每个树都含有一个根节点_root，通过类将二叉搜索树进行封装

中序遍历

在前面二叉搜索树的概念中我们可以知道，二叉搜索树也叫二叉排序树，通过其有序性再加上中序遍历就可以实现排序效果，这里展示中序遍历的代码实现

在这里插入图片描述

代码实现：

void InOrder(){
    _InOrder(_root);
    cout<<endl;
}

private:
void _InOrder(Node* root){
    if(root==nullptr){
        return;
    }
    _InOrder(root->_left);
    cout<<root->_key<<" ";
    _InOrder(root->_right);
}

实现原理：
- 因为在类中，根节点_root为私有类型，不能在类外中作为参数使用，所以这里使用两个函数来达到调用效果
- 子函数_InOrder要设置成私有类型，防止在类外中调用，只能通过函数InOrder调用

查找函数

因为二叉搜索树的左右子树结构相同，所以可以实现递归调用，所以查找函数以及之后的插入和删除都展示两种代码实现，递归和非递归实现

非递归代码实现：

bool Find(const K& key){
    //空树时，直接返回false，没有找到
    if(_root==nullptr){
        return false;
    }
    //非空树时，循环查找
    Node* cur=_root;
    while(cur){
        if(cur->_key<key){
            cur=cur->_right;
        }
        else if(cur->_key>key){
            cur=cur->_left;
        }
        else{
            return true;
        }
    }
    return false;
}

递归代码实现：

bool FindR(const k& key){
    return _FindR(_root,key);
}

private:
bool _FindR(Node* root,const K& key){
    if(root==nullptr){
        return false;
    }
    if(root->_key<key){
        return _FindR(root->_right,key);
    }
    else if(root->_key>key){
        return _FindR(root->_left,key);
    }
    else{
        return true;
    }
}

实现原理：
- 查找过程从根节点开始，如果目标值小于当前节点的值，到该节点的左子树中查找；如果目标值大于当前节点的值，到该节点的右子树中查找，当相等时说明已经找到返回true
- 当遇到空节点时，非递归表示没有找到，返回false；递归表示当前子树中没有，返回到上一层的函数调用中去，直到没有找到，依次返回false

插入函数

非递归代码实现：

bool Insert(const K& key){
    if(_root==nullptr){
        _root=new Node(key);
        return true;
    }
    else{
        Node* cur=_root;
        Node* parent=cur;
        while(cur){
            if(cur->_key<key){
                parent=cur;
                cur=cur->_right;
            }
            else if(cur->_key>key){
                parent-cur;
                cur=cur->_left;
            }
            else{
                return false;
            }
        }
        cur=new Node(key);
        if(parent->_key<key){
            parent->_right=cur;
        }
        else{
            parent->_left=cur;
        }
    }
    return true;
}

实现原理：
- 树为空，则直接新增节点，赋值给根节点指针
- 树不为空，按照二叉搜索树的有序性来查找插入位置，同时设置一个parent指针，用来指向插入位置的父节点，找到插入位置后，再判断是插入到父节点指针的左子结点还是右子节点
递归代码实现：

bool InsertR(const K& key){
    return _InsertR(_root,key);
}

private:
bool _InsertR(Node*& root,const K& key){
    if(root==nullptr){
        root=new Node(key)
        return true;
    }
    
    if(root->_key<key){
        return _InsertR(root->_right,key);
    }
    else if(root->_key>key){
        return _InsertR(root->_left,key);
    }
    else{
        return false;
    }
}

实现原理：
- 和非递归不同的是，这里递归调用中，参数节点为指针类型的引用，通过引用，不用在设置父节点来插入，直接找到对应位置，对应节点为空时，赋值给当前节点即可

在这里插入图片描述

删除函数

删除节点时首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：

删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
在删除节点的左子树中寻找最大（最右）结点用它的值填补到被删除节点，或者右子树的最小（最左）节点，交换后再来处理该结点的删除问题–替换法删除

在这里插入图片描述

非递归代码实现：

bool Erase(const K& key){
    Node* parent=nullptr;
    Node* cur=_root;
    
    while(cur){
        if(cur->_key<key){
            parent=cur;
            cur=cur->_right;
        }
        else if(cur->_key>key){
            parent=cur;
            cur=cur->_left;
        }
        else{
            //删除节点的左子结点为空
            if(cur->_left==nullptr){
                if(cur==_root){
                    _root=cur->_right;
                }
                else{
                    if(parent->_right=cur){
                        parent->_right=cur->_right;
                    }
                    else{
                        parent->_left=cur->_right;
                    }
                }
            }
            //删除节点的右子结点为空
            else if(cur->_right==nullptr){
                if(cur==_root){
                    _root=cur->_left;
                }
                else{
                    if(parent->_right==cur){
                        parent->_right=cur->_left;
                    }
                    else{
                        parent->_left=cur->_left;
                    }
                }
            }
            //删除节点的左右子节点都不为空
            else{
                Node* parent=cur;
                Node* leftMax=cur->_left;
                while(leftMax->_right){
                    parent=leftMax;
                    leftMax=leftMax->_right;
                }
                swap(cur->_key,leftMax->_key);
                if(parent->_left==leftMax){
                    parent->_left=leftMax->_left;
                }
                else{
                    parent->_right=leftMax->_right;
                }
                cur=leftMax;
            }
            delete cur;
            cur=nullptr;
            return true;
        }
    }
    return false;
}

实现原理：
- 通过二叉搜索树的有序性找到要删除的节点，当节点的_key值等于key时，该节点就是要删除的节点
- 删除时，分为三种情况
- 删除节点的左子结点为空，判断删除节点是父节点的左子结点还是右子节点，将删除节点的右子节点交给父节点对应的左右子节点
- 删除节点的右子节点为空，判断删除节点是父节点的左子结点还是右子节点，将删除节点的左子结点交给父节点对应的左右子节点
- 删除节点的左右子节点都不为空，从删除节点的左子树中找到最右节点leftMax替换，替换后，将删除节点的子节点交给父节点
- 最后释放节点指针，置为空即可
递归代码实现：

bool EraseR(const K& key){
    return _EraseR(_root,key);
}

private:
bool _EraseR(Node*& root,const K& key){
    if(root==nullptr){
        return false;
    }
    if(root->_key<key){
        return _EraseR(root->_right,key);
    }
    else if(root->_key>key){
        return _EraseR(root->_left,key);
    }
    else{
        Node* del=root;
        //删除节点的左子结点为空
        if(root->_left==nulllptr){
            root=root->_right;
        }
        //删除节点的右子节点为空
        else if(root->_right==nullptr){
            root=root->_left;
        }
        //左右子节点都不为空
        else{
            Node* leftMax=root->_left;
            while(leftMax->_right){
                leftMax=leftMax->_right;
            }
            swap(root->_key,leftMax->_key);
            return _EraseR(root->_left,key);
        }
        delete del;
        del=nullptr;
    }
    return true;
}

实现原理：
- 和非递归不同的是，递归调用的参数root是节点指针类型，所以不用借助父节点来删除，可以直接更改节点指针root的指向
- 还是三种情况
- 如果删除节点的左子结点为空，节点指针root指向删除节点的右子节点
- 若果删除节点的右子节点为空，节点指针root指向删除节点的左子结点
- 如果左右子节点都不为空，找到替换节点，交换后，递归调用该函数从当前root节点的左子树中删除，相当于转换成上面两种情况
- 最后释放节点指针，指针置为空即可

默认成员函数

析构函数代码实现：

~BSTree(){
    Destroy(_root);
}

private:
void Destroy(Node* root){
    if(root==nullptr){
        return;
    }
    Destroy(root->_left);
    Destroy(root->_right);
    delete root;
    root=nullptr;
}

实现原理：

通过后序遍历，先左子结点再右子节点最后再是根节点，依次释放节点指针即可
拷贝构造函数代码实现：

BSTree(const BSTree<K>& t){
    _root=Copy(t._root);
}

private:
Node* Copy(Node* root){
    if(root==nullptr){
        return nullptr;
    }
    TreeNode* copyroot=new Node(root->_key);
    copyroot->_left=Copy(root->_left);
    copyroot->_right=Copy(root->_right);
    return copyroot;
}

实现原理：

通过前序遍历，先拷贝构造出根节点，再递归调用构造左子树和右子树，最后返回根节点即可
赋值运算符重载函数代码实现：

BSTree<K>& operator=(BSTree<K>& t){
    swap(_root,t._root);
    return *this;
}

实现原理：

直接交换赋值对象和被赋值对象的根节点指针即可

测试

测试代码如下：

void test1(){
    int arr[]={6,3,0,5,9,1,2,4,8,7};
    BSTree<int> t;
    for(auto e:arr){
        t.InsertR(e);
    }
    t.InOrder();

    for(auto a:arr){
        t.EraseR(a);
        t.InOrder();
    }
}

void test2(){
    int arr[]={6,3,0,5,9,1,2,4,8,7};
    BSTree<int> T1;
    for(auto e:arr){
        T1.InsertR(e);
    }
    BSTree<int> T2(T1);
    T2.InOrder();

    BSTree<int> T3;
    T3=T1;
    T3.InOrder();

    cout<<T3.FindR(8)<<endl;
    cout<<T3.FindR(100)<<endl;
}

int main(){
    test1();
    test2();
    return 0;
}

测试结果如下：

在这里插入图片描述

三.完整代码

BSTree.h文件完整代码：

#include<iostream>
#include<algorithm>
using namespace std;

template<class K>
class BSTreeNode{              //二叉搜索树的节点类封装
public:

    BSTreeNode(const K& key)
    :_left(nullptr)
    ,_right(nullptr)
    ,_key(key)
    {}

    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;
    K _key;
};

template<class K>
class BSTree{                               //二叉树搜索树类的封装
    typedef BSTreeNode<K> Node;
public:
    BSTree()                                //构造函数
    :_root(nullptr)
    {
        cout<<"BSTree()"<<endl;
    }

    ~BSTree(){                              //析构函数
        cout<<"~BSTree()"<<endl;
        Destroy(_root);
    }

    BSTree(const BSTree<K>& t){             //拷贝构造函数
        cout<<"BSTree(const BSTree<K>& t)"<<endl;
        _root=Copy(t._root);
    }

    BSTree<K>& operator=(BSTree<K>& t){     //赋值运算符重载
        swap(_root,t._root);
        return *this;
    }

    void InOrder(){                         //中序遍历
        _InOrder(_root);
        cout<<endl;
    }
 
    bool FindR(const K& key){               //递归查找函数
        return _FindR(_root,key);
    }

    bool InsertR(const K& key){             //递归插入函数
        return _InsertR(_root,key);
    }

    bool EraseR(const K& key){              //递归删除函数
        return _EraseR(_root,key);
    }

    bool Find(const K& key){
        if(_root==nullptr){
            return false;
        }
        Node* cur=_root;
        while(cur){
            if(cur->_key<key){
                cur=cur->_right;
            }
            else if(cur->_key>key){
                cur=cur->_left;
            }
            else{
                return true;
            }
        }
        return false;
    }

    bool Insert(const K& key){              //插入节点函数
        if(_root==nullptr){                 //如果当前是空树，直接创建根节点
            _root=new Node(key);
            return true;
        }
        else{
            Node* cur=_root;
            Node* parent=cur;
            while(cur){
                if(cur->_key<key){
                    parent=cur;
                    cur=cur->_right;
                }
                else if(cur->_key>key){
                    parent=cur;
                    cur=cur->_left;
                }
                else{
                    return false;
                }
            }
            cur=new Node(key);
            if(parent->_key<key){
                parent->_right=cur;
            }
            else{
                parent->_left=cur;
            }
        }
        return true;
    }

    bool Erase(const K& key){
        Node* parent=nullptr;
        Node* cur=_root;

        while(cur){
            if(cur->_key<key){
                parent=cur;
                cur=cur->_right;
            }
            else if(cur->_key>key){
                parent=cur;
                cur=cur->_left;
            }
            else{                                                 //找到删除节点
                if(cur->_left==nullptr){                          //删除的左子结点为空
                    if(cur==_root){                               //且是根节点的情况
                        _root=cur->_right;
                    }
                    else{                                         //不是根节点的情况
                        if(parent->_right==cur){                  //父节点的右子节点是删除节点
                            parent->_right=cur->_right;
                        }
                        else{                                     //父节点的左子结点是删除节点
                            parent->_left=cur->_right;
                        }
                    }
                }
                else if(cur->_right==nullptr){                    //删除的右子节点为空
                    if(cur==_root){                                //且是根节点
                        _root=cur->_left;
                    }
                    else{                                         //不是根节点的情况
                        if(parent->_right==cur){                  //父节点的右子节点是删除节点
                            parent->_right=cur->_left;
                        }
                        else{                                     //父节点的左子结点是删除节点
                            parent->_left=cur->_left;
                        }
                    }
                }
                else{                                             //删除的节点左右子节点都不为空
                    Node* parent=cur;                             //父节点初始时必须指向cur节点
                    Node* leftMax=cur->_left;                     //定义一个leftMax节点用来找左子树的最大节点也是最右节点
                    while(leftMax->_right){
                        parent=leftMax;
                        leftMax=leftMax->_right;
                    }

                    swap(cur->_key,leftMax->_key);              //交换需要删除的节点和找到的替换节点的值
                    if(parent->_left==leftMax){                   
                        parent->_left=leftMax->_left;
                    }
                    else{
                        parent->_right=leftMax->_right;
                    }
                    cur=leftMax;

                }
            delete cur;                                           //释放需要删除的节点
            cur=nullptr;                                          //节点置为空
            return true;
            }
        }
        return false;
    }

private:
    void _InOrder(Node* root){                                   //中序遍历子函数
        if(root==nullptr){
            return;
        }
        _InOrder(root->_left);
        cout<<root->_key<<" ";
        _InOrder(root->_right);
    }

    void Destroy(Node* root){                                    //析构函数子函数
        if(root==nullptr){                                       //后序遍历即可
            return;
        }
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
        root=nullptr;
    }

    Node* Copy(Node* root){                                     //拷贝构造子函数
        if(root==nullptr){                                      //前序遍历即可
            return nullptr;
        }
        Node* copyroot=new Node(root->_key);
        copyroot->_left=Copy(root->_left);
        copyroot->_right=Copy(root->_right);
        return copyroot;

    }

    bool _FindR(Node*& root,const K& key){                      //递归查找子函数
        if(root==nullptr){
            return false;
        }
        if(root->_key<key){
            return _FindR(root->_right,key);
        }
        else if(root->_key>key){
            return _FindR(root->_left,key);
        }
        else{
            return true;
        }
    }

    bool _InsertR(Node*& root,const K& key){                      //递归插入子函数
        if(root==nullptr){                                        //如果当前节点为空，说明找到了插入的位置
            root=new Node(key);                                   //因为指针引用，所以直接创造新节点
            return true;                                          //插入成功，返回true
        }

        if(root->_key<key){                                       //当前节点_key值小于key值，到右子树中查找
            return _InsertR(root->_right,key);
        }
        else if(root->_key>key){                                  //当前节点_key值大于key值，到左子树中查找
            return _InsertR(root->_left,key);
        }
        else{                                                     //当前节点_key值等于key值，说明已经存在，返回false
            return false;
        }
    }

    bool _EraseR(Node*& root,const K& key){                      //递归删除子函数
        if(root==nullptr){                                       //如果当前节点为空，说明没有找到要删除的节点
            return false;                                        //返回false
        }
        if(root->_key<key){                                      //当前节点_key值小于key值，到右子树中查找
            return _EraseR(root->_right,key);
        }
        else if(root->_key>key){                                 //当前节点_key值大于key值，到左子树中查找
            return _EraseR(root->_left,key);
        }
        else{                                                    //当前节点_key值等于key值，说明找到要删除的节点
            Node* del=root;                                      //从新顶一个指针指向当前要删除的节点                  
            if(root->_left==nullptr){                            //删除节点左子结点为空                   
                root=root->_right;                               //root指向删除节点的右子节点
            }
            else if(root->_right==nullptr){                      //删除节点右子结点为空 
                root=root->_left;                                //root指向删除节点的左子节点
            }
            else{                                                //如果删除节点的左右子节点都不为空
                Node* leftMax=root->_left;                       //定义一个新的节点指针指向删除节点的左子结点
                while(leftMax->_right){                          //查找替换节点，左子树的最大节点，也是最右节点
                    leftMax=leftMax->_right;
                }
                swap(root->_key,leftMax->_key);                  //交换删除节点和替换节点的值
                return _EraseR(root->_left,key);                  //再从左子树中查找要删除的节点
            }
            delete del;                                          //释放删除节点
            del=nullptr;                                         //节点置为空
        }
        return true;
    }


private:
    Node* _root;
};

** 以上就是关于二叉搜索树的概念和模拟实现的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！**
在这里插入图片描述

原文地址：https://blog.csdn.net/2301_82347435/article/details/143836852

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Tomcat(23)如何配置Tomcat的连接器以优化性能？
下一篇：Android 超大图预览防止OOM

学习threejs，使用设置bumpMap凹凸贴图创建褶皱,实现贴图厚度效果
本文详细介绍如何基于threejs在三维场景中使用设置bumpMap凹凸贴图创建褶皱,实现贴图厚度效果，亲测可用。希望能帮助到您。一起学习，加油！加油！
阅读更多2024-11-23
springboot课程答疑系统(代码+数据库+LW)
摘要随着信息互联网信息的飞速发展，无纸化作业变成了一种趋势，针对这个问题开发一个专门适应师生交流形式的网站。本文介绍了课程答疑系统的开发全过程。通过分析企业对于课程答疑系统的需求，创建了一个计算机管理
阅读更多2024-11-23
云服务器部署springboot项目、云服务器配置JDK、Tomcat
（这个server.xml里面有tomcat的配置可以在这里修改，这里可以把tomcat端口改成80，就这里 tomcat默认端口8080 改成80 和http默认端口一样访问就不用输入端口号了。
阅读更多2024-11-23
如何在Linux上安装Canal同步工具
所用到的安装包链接：https://pan.baidu.com/s/1B1LxZUZsKVaHvoSx6VV3sA提取码：v7ta链接：https://pan.baidu.com/s/13RSqPin
阅读更多2024-11-23
MySQL 三大日志详解
Binlog 是 MySQL 数据库的二进制日志，它记录了数据库的所有变更操作，包括数据的插入、更新、删除等。
阅读更多2024-11-23
Redis五大基本类型——Zset有序集合命令详解（命令用法详解+思维导图详解）
有序集合保留了集合不能有重复成员的特点。但和集合不同的是，有序集合中的每一个元素都有一个唯一的浮点类型的分数（score）与之关联，这使得有序集合中的元素是可以维持有序性的。有序集合中的有序并不是用下
阅读更多2024-11-23
【读书】复杂性意义结构框架——Cynefin框架
Cynefin框架是戴维·斯诺登（David Snowden）20世纪90年代的在IBM时创建的，在其后，他继续发展它。斯诺登将框架描述为一种“意义结构框架”（sense-making framewo
阅读更多2024-11-23
洛谷 P1049 [NOIP2001 普及组] 装箱问题 C语言记忆化搜索-＞‘倒序‘dp-＞‘正序‘dp
没有什么正序dp和倒序dp，本质就是状态定义和关系转移的不同。'倒序'dp，代码如下。记忆化搜索，代码如下。'正序'dp代码如下。
阅读更多2024-11-23
Android 设置 bottomnavigation 底部导航栏的样式
样式自定义：通过styles.xml文件自定义的外观，包括背景色、图标颜色、选中文本颜色等。显示方式：可以使用固定（显示所有菜单项）或滚动模式来显示的菜单项。与 ViewPager2 结合：通过来监听
阅读更多2024-11-23
Rust学习（八）：异常处理和宏编程：
异常处理是任何编程语言都会遇到的现象，Rust并没有像其他变成语言一样提供了try catch这样的异常处理方法，而是提供了一种独特的异常处理机制。这里需要指明的是作者在书中将Rust中的失败、错误、
阅读更多2024-11-23

【c++篇】：二叉搜索树--有序存储与高效查找的关键

文章目录

前言

一.二叉搜索树的概念和性质

二.模拟实现

基本框架

中序遍历

查找函数

插入函数

删除函数

默认成员函数

测试

三.完整代码

相关文章