数据结构/C++：二叉搜索树

数据结构/C++：二叉搜索树

• • 概念
  • 模拟实现
  • • 结构分析
    • 插入
    • 中序遍历
    • 查找
    • 删除
    • 析构函数
    • 拷贝构造
    • 赋值重载
    • 递归查找
    • 递归插入
    • 递归删除
    • ���代码展示

      ---

      概念

      二叉搜索树（BST - Binary Search Tree）是一种特殊的二叉树，每个顶点最多可以有两个子节点。其遵顼以下规则：

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

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

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

      比如以下二叉树就是一个二叉搜索树：

      对于节点59，其左子树节点46小于59，其右子树所有节点79，94，87，96都大于59，其它节点以此类推。

      其有两个特性：

      1. 查找数据非常快，每次查找数据，只需要将数据与当前节点比较，然后决定去左子树还是右子树找，如果最后找到了nullptr，那就是不存在。

      比如我们在刚才的二叉树中查找87：

      可以发现：查找一个值，最多只需要树高度次，这也是二叉搜索树得名的原因，很适合搜索值。

      1. 二叉搜索树的中序遍历，得到值是有序的。正是因为二叉搜索树左子树的值都小于根，右子树的值都大于根。中序遍历是 左子树 - 根 - 右子树，所以最后得到的数据就是有序的。

      接下来我们模拟实现这个数据结构，使用的语言是C++语言。

      ---

      模拟实现

      结构分析

      由于二叉树的每一个节点都要存储：左子树根节点，右子树根节点，当前节点，当前节点的存储值。所以要用一个结构体统一处理：

      节点类：

      templatestruct BSTreeNode{    typedef BSTreeNode Node;    Node* _root;    Node* _left;    Node* _right;    K _key;};

      然后我们再给节点写一个构造函数：

      templatestruct BSTreeNode{    typedef BSTreeNode Node;    Node* _root;    Node* _left;    Node* _right;    K _key;        BSTreeNode(const K& key)        :_root(nullptr)        ,_left(nullptr)        ,_right(nullptr)        ,_key(key)    {}};

      对于二叉搜索树的类，我们只需要定义一个指向根节点的_root成员即可：

      二叉搜索树类：

      templateclass BSTree{    typedef BSTreeNode Node;private:    Node* _root = nullptr;};

      ---

      插入

      想要对二叉搜索树进行节点插入，有两种情况：

      1. 节点值存在：此时不再进行插入
      2. 节点值不存在：进行插入

      值得注意的是：如果某一个值不存在于二叉搜索树中，那么插入这个值一定是在nullptr插入。

      那么我们第一步就是要找到适合插入的节点，看到以下代码：

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

      整个Insert函数的返回值是bool类型的，因为Insert有可能插入失败，此时就要返回值检测是否插入成功。

      ---

      首先定义一个cur指针，往下查找待插入的节点，只要因为一定在nullptr插入，所以只要cur不为nullptr，就一直找下去。

      ---

      if (key _key)如果当前的值key小于当前cur节点的值，那么cur就往左子树插入cur = cur->_left;

      ---

      else if (key > cur->_key)如果当前的值key大于当前cur节点的值，那么cur就往右子树插入cur = cur->_right;

      ---

      如果前两个条件不成立，说明当前节点和我们需要插入的值相同，说明原先就有待插入的值，此时返回false

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

      相比于一开始的代码，我们在一开始查找节点时，额外定义了一个parent节点，每次cur节点改变时，都保证parent是其父节点，这样我们就可以完成最后的插入操作了。

      那么我们要如何对父亲节点进行插入？现在我们确定了待插入的父节点，那么我们要插入到父节点的左子树，还是右子树？

      这就涉及到待插入值与父节点的值的判断：如果待插入值小于父节点值，插入左子树；反之插入右子树。

      代码如下：

      cur = new Node(key);if (key _key)    parent->_left = cur;else    parent->_right = cur;

      但是我们的代码还是存在一个问题，那就是：我们目前没有处理空树的情况，也就是_root为nullptr。这种情况下我们直接让_root节点存储key值就可以了。

      代码如下：

      if (_root == nullptr){    _root = new Node(key);    return true;}

      至此，我们就完成了整个插入操作的接口：

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

      ---

      中序遍历

      中序遍历，对于二叉树而言是一个比较简单的操作，我们看到以下代码：

      void InOrder(Node* root){    if (root == nullptr)        return;    InOrder(root->_left);    cout _key _right);}

      比如说我要遍历某一个二叉搜索树bst：

      bst.InOrder(bst._root);

      这个调用是存在问题的，那就是_root是私有成员，外部不能把_root作为参数传入中序遍历的接口。此时我们就需要再在外面套一层接口，像这样：

      void InOrder(){    _InOrder(_root);}void _InOrder(Node* root){    if (root == nullptr)        return;    _InOrder(root->_left);    cout _key _right);}

      我们给函数InOrder创建了一个子函数_InOrder，外部无需传参就可以调用InOrder。我们将中序遍历的代码写在了子函数中，而在InOrder内部，再去调用这个子函数 _InOrder(_root);，就可以正常传参了。

      ---

      查找

      想要查找，基本逻辑就是：

      当前节点的值小于key，到左子树查找

      当前节点的值大于key，到右子树查找

      当前节点的值等于key，返回true

      如果查找到nullptr，说明不存在，返回false

      代码如下：

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

      ---

      删除

      二叉搜索树的删除是最麻烦的一步，因为删除一个节点会牵扯到大量节点，接下来我们一步一步推导。

      首先，既然要删除特定的节点，那么我们就要先查找到该节点。既然要修改该节点，那么也要查找到其父节点，这个思路与前面的插入接口非常相似。代码如下：

      bool Erase(const K& key){    Node* cur = _root;    Node* parent = nullptr;    while (cur)    {        if (key _key)        {            parent = cur;            cur = cur->_left;        }        else if (key > cur->_key)        {            parent = cur;            cur = cur->_right;        }        else        {        //删除节点            return true;        }    }    return false;}

      接下来我们就需要考虑//删除节点这一块的问题了，其会分为很多种情况，我们先看到第一种：

      假设我们要删除以下二叉搜索树的79节点：

      这就涉及到两个方向的问题：其父亲节点59应该怎么办？其孩子节点94应该怎么办？

      首先，由于79只有一个子树，所以不用考虑两个子树之间会出现节点值不满足二叉搜索树要求的冲突。

      对于59节点，其要求右子树的所有值大于59

      对于94节点，因为是右子树，其要求父亲节点必须小于94

      那么我们是不是可以直接将94节点链接到59节点下方，然后删除79，这样下来，整棵树还满足二叉搜索树的结构。

      动图如下：

      也就是说：只要被删除的节点，有一个子树为nullptr，那么就可以将另外一个子树直接链接到其父节点下。这是第一种情况，代码实现：

       if (cur->_left == nullptr) {     if (cur == parent->_left)         parent->_left = cur->_right;     else         parent->_right = cur->_right;     delete cur; } else if (cur->_right == nullptr) {     if (cur == parent->_left)         parent->_left = cur->_left;     else         parent->_right = cur->_left;     delete cur; } else {//其他情况 }

      我们拿出第一段代码解析：

       if (cur->_left == nullptr) {     if (cur == parent->_left)         parent->_left = cur->_right;     else         parent->_right = cur->_right;     delete cur; }

      备注：通过前面查找节点，此时的cur已经是待删除的节点，parent是cur父节点。

      cur->_left == nullptr ：如果待删除节点cur的左子树为为nullptr，那么我们就要把cur的右子树交给其parent节点

      ---

      但是我们不知道要交给parent的左子树，还是右子树，此时看cur与parent的关系。如果cur是parent的左子树 if (cur == parent->_left)，那就插入到parent的左子树 parent->_left = cur->_right;，反之插入到右子树parent->_right = cur->_right;。

      ---

      delete cur;：经过以上操作，我们重新调整了整棵树的结构，现在就可以直接删除cur节点了

      但是这个代码还有一个问题，我们看到以下情况：

      假设我们要删除以下二叉搜索树的98节点：

      由于98右子树为nullptr，那么其会其可以直接将左子树连接到98的父节上。但是98是_root节点，其没有父节点，parent为空指针，此时程序就会发生错误，所以我们要特殊处理一下删除_root的情况，如果我们要删除_root，且_root有一个子树为nullptr，那么我们直接把另外一棵子树的根节点变成_root即可。

      代码如下：

      if (cur->_left == nullptr){    if (cur == _root)    {        _root = cur->_right;    }    else    {        if (cur == parent->_left)            parent->_left = cur->_right;        else            parent->_right = cur->_right;    }    delete cur;}else if (cur->_right == nullptr){    if (cur == _root)    {        _root = cur->_right;    }    else    {        if (cur == parent->_left)            parent->_left = cur->_left;        else            parent->_right = cur->_left;    }    delete cur;}else{//其他情况}

      现在我们再来讨论另外一种情况：当待删除节点的左右子树都不为空，这该怎么办？

      假设我们要删除以下二叉搜索树的36节点：

      我们要如何保证删除36之后，整棵树都满足二叉搜索树？这涉及到以下问题：

      对于99节点，其要求左子树的所有值小于99

      对于27节点，因为是左子树，其要求父亲节点必须大于27

      对于81节点，因为是右子树，其要求父亲节点不许小于81

      也就是说我们要找到一个值，大于所有左子树节点，小于所有右子树节点，放在36原先的位置。

      有两种解决方案：

      1. 取出左子树最大的值替换删除节点
      2. 取出右子树最小的值替换删除节点

      我先讲解一下为什么可以这么做：

      以取出右子树最小值为例：对于原先的二叉搜索树结构，36节点左侧所有值小于36，右边所有值大于36，所以我们从右子树取出任意一个值，都是大于左子树的值的。但是我们取出的值，又要小于右子树所有节点的，所以要取出右子树的最小值。左子树同理。

      那么如何取出右子树最小值？右子树的最小值节点，是第一个左子树为nullptr的节点，也就是最左侧的节点。对于以上代码，从81开始的整棵树，最小值就是49，也是第一个左子树为nullptr的节点。

      取出节点后，我们把右子树最小节点rightMin的值交给待删除节点的cur，但是rightMin还有可能有右子树，那么就要把右子树移交给rightMin的父节点。比如以上树中，就是要把49节点的右子树59交给71。

      那么我们书写一下代码：

      Node* rightMinParent = cur;Node* rightMin = cur->_right;while (rightMin->_left){    rightMinParent = rightMin;    rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinParent->_left == rightMin)    rightMinParent->_left == rightMin->_right;else    rightMinParent->_right == rightMin->_right;delete rightMin;

      解析：

      rightMin代表右子树最小值，rightMinParent代表其父节点

      ---

      通过while (rightMin->_left)来找第一个左子树为nullptr的节点。

      ---

      cur->_key = rightMin->_key;：把需要删除的节点cur的值改为rightMin的值，此时二叉搜索树依然符合要求

      ---

      然后把左子树最小值的节点 rightMin删除掉，if (rightMinParent->_left == rightMin)：如果是父节点的左子树，就把当前 rightMin的右子树移交给父节点左子树rightMinParent->_left == rightMin->_right;。（rightMin下面可能还有子树）反之交给父节点的右子树。

      ---

      最后删除节点：delete rightMin;

      最终效果如下：

      ---

      析构函数

      想要删除整棵树，那就需要递归式地删除每一个节点，为了保证树的节点不会错乱，我们最好通过后序遍历删除，代码如下：

      ~BSTree(){    Destroy(_root);}void Destroy(Node* root){    if (root == nullptr)        return;    Destroy(root->_left);    Destroy(root->_right);    delete root;}

      比较简单，不做详解了。

      ---

      拷贝构造

      想要拷贝一棵树出来，我们也需要进行递归式的深拷贝，不过由于要先有父节点，再有子节点，所以要用前序遍历。代码如下：

      BSTree(const BSTree& t){    _root = Copy(t._root);}Node* Copy(Node* root){    if (root == nullptr)        return nullptr;    Node* newRoot = new Node(root->_key);    newRoot->_left = Copy(root->_left);    newRoot->_right = Copy(root->_right);    return newRoot;}

      解析：

      Node* newRoot = new Node(root->_key);先创建一个根节点，然后将该节点的左子树连接到拷贝后的左子树：newRoot->_left = Copy(root->_left);，右子树同理。当遇到nullptr就停止递归。

      这也是一个二叉树基本操作，不详细讲解了。

      ---

      赋值重载

      代码如下：

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

      这是一个比较现代的赋值重载，注意我们在传参时BSTree t不是一个引用，而是一个不同的参数，此时参数t是实参的一份拷贝，是通过拷贝构造创建的，然后我们把这个形参拷贝构造出来的树直接交换给自己： swap(_root, t._root);。这样就相当于通过拷贝构造，完成了一个赋值重载。

      ---

      接下来，我们再通过递归的模式，来复写几个接口，看看不同的实现方法。

      递归查找

      首先要通过递归查找到指定值，那就是：

      如果key小于当前节点，递归左子树

      如果key大于当前节点，递归右子树

      如果key等于当前节点，返回true

      如果当前节点为nullptr，说明没找到，返回false

      代码如下：

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

      ---

      递归插入

      在递归插入前，先通过一般的形式进行查找：

      如果key小于当前节点，递归左子树

      如果key大于当前节点，递归右子树

      如果key等于当前节点，说明节点存在，返回false

      如果当前节点为nullptr，则在该节点插入一个新的节点，并返回true

      代码如下：

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

      ---

      递归删除

      首先通过递归找到节点：

      bool EraseR(const K& key){    return _EraseR(_root, key);}bool _EraseR(Node*& root, const K& key){    if (root == nullptr)        return false;    if (key _key)    {        return _EraseR(root->_left, key);    }    else if (key > root->_key)    {        return _EraseR(root->_right, key);    }    else    {    //删除节点    }}

      通过递归找到删除节点后，要考虑两种情况：

      1. 待删除节点有一个子树为nullptr
      2. 待删除节点拥有两个子树

      先看到第一种：

      Node* del = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{}delete del;return true;

      备注：此时我们已经通过递归找到了待删除的节点root

      基本原理已经讲解过：如果root左子树为nullptr，就把其右子树交给父节点。但是这里的root = root->_right;是在干啥？

      ---

      注意，我们这的传参是Node*& root，也就是传引用，对于root这个变量而言，他不仅仅是待删除的节点，也是父节点左子树或右子树的别名。所以我们root = root->_right;的过程其实就是在修改父节点的子树。

      ---

      这个操作有两个很大的好处：

      1. 我们不需要再单独保留父节点parent了，直接通过引用即可修改父节点
      2. 如果删除的节点是根节点，那么root就是_root的别名，也不需要额外处理删除根节点的情况了

      当然，这个步骤会导致root被修改，所以我们还要提前保留一份root，方便后续删除。

      接下来我们再看到左右子树都不为nullptr的情况：

       else{    Node* rightMin = root->_right;    while (rightMin->_left)    {        rightMin = rightMin->_left;    }    swap(root->_key, rightMin->_key);    return _EraseR(root->_right, key);}

      首先要查找rightMin ，也就是 while (rightMin->_left)这个循环。

      ---

      找到右子树的最小值后，我们就要把它的值交给待删除节点root，即： swap(root->_key, rightMin->_key);

      ---

      但是这里有一个细节，那就是：反正都要删掉，为什么不直接root->_key, = rightMin->_key这样赋值，然后直接删掉呢？

      ---

      对于右子树而言，root的值小于右子树的所有值，rightMin的值也小于右子树的所有值，所以通过swap交换后，右子树整棵树依然符合二叉搜索树的结构，而且待删除的key值被转移到了左子树为nullptr的节点，此时我们再通过递归_EraseR(root->_right, key)，就可以按照第一种情况把key节点给删掉。这一步非常巧妙，当然你也可以按照原先的方式删除。

      删除代码如下：

      bool EraseR(const K& key){    return _EraseR(_root, key);}bool _EraseR(Node*& root, const K& key){    if (root == nullptr)        return false;    if (key _key)    {        return _EraseR(root->_left, key);    }    else if (key > root->_key)    {        return _EraseR(root->_right, key);    }    else    {        Node* del = root;        if (root->_left == nullptr)        {            root = root->_right;        }        else if (root->_right == nullptr)        {            root = root->_left;        }        else        {            Node* rightMin = root->_right;            while (rightMin->_left)            {                rightMin = rightMin->_left;            }            swap(root->_key, rightMin->_key);            return _EraseR(root->_right, key);        }        delete del;        return true;    }}

      ---

      总代码展示

      BinarySearchTree.h：

      #pragma once#include using namespace std;templatestruct BSTreeNode{    typedef BSTreeNode Node;    Node* _root;    Node* _left;    Node* _right;    K _key;    BSTreeNode(const K& key)        :_root(nullptr)        ,_left(nullptr)        ,_right(nullptr)        ,_key(key)    {}};templateclass BSTree{    typedef BSTreeNode Node;public:    BSTree() = default;    BSTree(const BSTree& t)    {        _root = Copy(t._root);    }    Node* Copy(Node* root)    {        if (root == nullptr)            return nullptr;        Node* newRoot = new Node(root->_key);        newRoot->_left = Copy(root->_left);        newRoot->_right = Copy(root->_right);        return newRoot;    }            ~BSTree()    {        Destroy(_root);    }    void Destroy(Node* root)    {        if (root == nullptr)            return;        Destroy(root->_left);        Destroy(root->_right);        delete root;    }    BSTree& operator=(BSTree t)    {        swap(_root, t._root);        return *this;    }    bool Insert(const K& key)    {        if (_root == nullptr)        {            _root = new Node(key);            return true;        }                Node* cur = _root;        Node* parent = nullptr;        while (cur)        {            if (key _key)            {                parent = cur;                cur = cur->_left;            }            else if (key > cur->_key)            {                parent = cur;                cur = cur->_right;            }            else            {                return false;            }        }        cur = new Node(key);        if (key _key)            parent->_left = cur;        else            parent->_right = cur;        return true;    }    bool Erase(const K& key)    {        Node* cur = _root;        Node* parent = nullptr;        while (cur)        {            if (key _key)            {                parent = cur;                cur = cur->_left;            }            else if (key > cur->_key)            {                parent = cur;                cur = cur->_right;            }            else            {                if (cur->_left == nullptr)                {                    if (cur == _root)                    {                        _root = cur->_right;                    }                    else                    {                        if (cur == parent->_left)                            parent->_left = cur->_right;                        else                            parent->_right = cur->_right;                    }                    delete cur;                }                else if (cur->_right == nullptr)                {                    if (cur == _root)                    {                        _root = cur->_right;                    }                    else                    {                        if (cur == parent->_left)                            parent->_left = cur->_left;                        else                            parent->_right = cur->_left;                    }                    delete cur;                }                else                {                    Node* rightMinParent = cur;                    Node* rightMin = cur->_right;                    while (rightMin->_left)                    {                        rightMinParent = rightMin;                        rightMin = rightMin->_left;                    }                    cur->_key = rightMin->_key;                    if (rightMinParent->_left == rightMin)                        rightMinParent->_left == rightMin->_right;                    else                        rightMinParent->_right == rightMin->_right;                    delete rightMin;                }                return true;            }        }        return false;    }    bool Find(const K& key)    {        Node* cur = _root;        while (cur)        {            if (key _key)                cur = cur->_left;            else if (key > cur->_key)                cur = cur->_right;            else                return true;        }        return false;    }    void InOrder()    {        _InOrder(_root);        cout         return _FindR(_root, key);    }    bool InsertR(const K& key)    {        return _InsertR(_root, key);    }    bool EraseR(const K& key)    {        return _EraseR(_root, key);    }private:    void _InOrder(Node* root)    {        if (root == nullptr)            return;        _InOrder(root-_left);        cout         if (root == nullptr)            return false;        if (key _left, key);        else if (key > root->_key)            return _FindR(root->_right, key);        else            return true;    }    bool _InsertR(Node*& root, const K& key)    {        if (root == nullptr)        {            root = new Node(key);            return true;        }        if (key _key)            return _InsertR(root->_left, key);        else if (key > root->_key)            return _InsertR(root->_right, key);        else            return false;    }    bool _EraseR(Node*& root, const K& key)    {        if (root == nullptr)            return false;        if (key _key)        {            return _EraseR(root->_left, key);        }        else if (key > root->_key)        {            return _EraseR(root->_right, key);        }        else        {            Node* del = root;            if (root->_left == nullptr)            {                root = root->_right;            }            else if (root->_right == nullptr)            {                root = root->_left;            }            else            {                Node* rightMin = root->_right;                while (rightMin->_left)                {                    rightMin = rightMin->_left;                }                swap(root->_key, rightMin->_key);                return _EraseR(root->_right, key);            }            delete del;            return true;        }    }    Node* _root = nullptr;};

      ---