【C++】二叉搜索树（下）-阿里云开发者社区

右为空

右为空时，使用parent节点去接收cur的左子树，但是还需判断下cur的左子树节点在parent的左子树还是右子树

当cur作为根节点时，此时parent为NULL,就会报错

所以要把cur作为根节点的情况单独处理

把cur的左子树的节点作为根，然后直接删除cur节点

删除节点有左孩子和右孩子节点

当找到minright时，minright在9节点位置上，minright可以替代cur的位置，替cur照顾两个孩子，但是minright本身也是有可能有孩子的，所以还需要找到minright的上一个父节点parent，同时需要判断下minright节点是parent节点的左孩子还是有孩子

pminright初始化不能为NULL，若为空，若不进入while循环，则无法更新pminright值，

导致NULL->left，从而报错

，minright不一定是minright的左子树，也有可能是pminright的右子树，所以需要判断下

整体代码

//删除
  bool Erase(const K& key)
  {
    //将第一种和第二种看作一种
    Node* parent = nullptr;//记录cur之前的节点
    Node* cur = _root;
    while (cur!=NULL)
    {
      if (cur->_key > key)
      {
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        cur = cur->_right;
      }
      else
      {
        //相等则说明数据存在，要删除
        //1.左为空
        if (cur->_left == nullptr)
        {
          if (cur == _root)//当cur作为根节点时
          {
            _root = cur->_right;
          }
          else
          {
            if (parent->_left == cur)//若cur在parent节点的左边
            {
              parent->_left = cur->_right;
            }
            else//若cur在parent节点的右边
            {
              parent->_right = cur->_right;
            }
          }
          delete cur;
        }
        //2.右为空
        else if (cur->_right == nullptr)
        {
          if (cur == _root)//当cur作为根节点时
          {
            _root = cur->_left;
          }
          else
          {
            if (parent->_left == cur)//若cur在parent节点的左边
            {
              parent->_left = cur->_left;
            }
            else//若cur在parent节点的右边
            {
              parent->_right = cur->_left;
            }
          }
          delete cur;
        }
        //3.请保姆
        else
        {
          //寻找右子树的最小节点
          Node* pminright = cur;
          Node* minright = cur->_right;//右子树的最小节点 
          //最左节点
          while (minright->_left)//找到最小节点
          {
            pminright = minright;//记录minright之前的节点
            minright = minright->_left;
          }
          cur->_key = minright->_key;
          //由于不知道minright是pminright的左子树还是右子树 ，所以需要判断下
          //再将minright的右子树pminright
          if (pminright->_left == minright)
          {
            pminright->_left = minright->_right;
          }
          else
          {
            pminright->_right = minright->_right;
          }
          delete minright;
        }
        return true;
      }
    }
    //说明要删除的数据不存在
    return false;
  }

二叉搜索树的实现 (递归)

递归实现，全都使用了函数嵌套的方式，与非递归的中序遍历的方式相同，是为了使用_root这个定义在类中的成员变量

查找

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

插入

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;
        }
    }
    bool InsertR(const K& key)
    {
        return _InsertR(_root,key);
    }

通过引用的方式解决遇见NULL连接新节点的问题

因为引用的原因，所以root==NULL进入if判断时， root作为上一个节点左指针的别名，相当于 root->_left 新创建了一个节点，直接与二叉树连接起来了

就不用像非递归一样考虑创建节点后，与它的上一个节点连接的问题

删除

删除节点有左孩子和右孩子节点

    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 == nullptr)//左为空
            {
                root = root->_right;
            }
            else if (root->_right == nullptr)//右为空
            {
                root = root->_left;
            }
            else
            {
                //替代法
                Node* maxleft = root->_left;
                //在左子树中寻找最右 作为左子树最大节点
                while (maxleft->_right != NULL)
                {
                    maxleft = maxleft->_right;
                }
                swap(maxleft, root);
                return EeaseR(root->_left, key);
            }
            delete del;
            return true;
        }
    }
    bool EraseR(const K&key)
    {
        return _EraseR(_root,key);
    }

二叉搜索树实现的整体代码

#pragma once
#include<iostream>
using namespace std;
template <class K>
//BSTree -- BinarySearchTree
struct BSTreeNode
{
  BSTreeNode<K>* _left;//左
  BSTreeNode<K>* _right;//右
  K  _key;//关键字
  BSTreeNode(const K& key)
    :_left(nullptr), _right(nullptr), _key(key)
  {
  }
};
template <class K>
class BSTree
{
  typedef BSTreeNode<K> Node;
public:
  ~BSTree()//析构
  {
    Destroy(_root);
    _root = nullptr;
  }
  /*BSTree(const BSTree<K>& t)
  {
  }
  void cpoy(Node*root)
  {
  }*/
  //插入
  bool Insert(const K& key)
  {
    if (_root == NULL)//若root根节点为nullptr
    {
      _root = new Node(key);
      return true;
    }
    Node* cur = _root;
    Node* parent = nullptr;//用于接收cur之前的节点
    while (cur != NULL)
    {
      if (cur->_key > key)//若插入的值比cur值小
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_key < key)//若插入的值比cur值大
      {
        parent = cur;
        cur = cur->_right;
      }
      else//若相等，则直接返回false
      {
        return false;
      }
    }
    //遇见空指针，连接新节点
    //由于不知道parent的左还是右连接key，所以需要判断
    cur = new Node(key);
    if (parent->_key < key)
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    return true;
  }
  //中序遍历
  void inorder()
  {
    _inorder(_root);
  }
  void _inorder(Node*root)
  {
    if (root == NULL)
    {
      return;
    }
    _inorder(root->_left);//左
    cout << root->_key << " ";//根
    _inorder(root->_right);//右  
  }
  //查找
  bool Find(const K& key)
  {
    Node* cur = _root;
    while (cur != NULL)
    {
      if (cur->_key > key)
      {
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        cur = cur->_right;
      }
      else
      {
        return true;
      }
    }
    return false;
  }
  //删除
  bool Erase(const K& key)
  {
    //将第一种和第二种看作一种
    Node* parent = nullptr;//记录cur之前的节点
    Node* cur = _root;
    while (cur!=NULL)
    {
      if (cur->_key > key)
      {
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        cur = cur->_right;
      }
      else
      {
        //相等则说明数据存在，要删除
        //1.左为空
        if (cur->_left == nullptr)
        {
          if (cur == _root)//当cur作为根节点时
          {
            _root = cur->_right;
          }
          else
          {
            if (parent->_left == cur)//若cur在parent节点的左边
            {
              parent->_left = cur->_right;
            }
            else//若cur在parent节点的右边
            {
              parent->_right = cur->_right;
            }
          }
          delete cur;
        }
        //2.右为空
        else if (cur->_right == nullptr)
        {
          if (cur == _root)//当cur作为根节点时
          {
            _root = cur->_left;
          }
          else
          {
            if (parent->_left == cur)//若cur在parent节点的左边
            {
              parent->_left = cur->_left;
            }
            else//若cur在parent节点的右边
            {
              parent->_right = cur->_left;
            }
          }
          delete cur;
        }
        //3.请保姆
        else
        {
          //寻找右子树的最小节点
          Node* pminright = cur;
          Node* minright = cur->_right;//右子树的最小节点 
          //最左节点
          while (minright->_left)//找到最小节点
          {
            pminright = minright;//记录minright之前的节点
            minright = minright->_left;
          }
          cur->_key = minright->_key;
          //由于不知道minright是pminright的左子树还是右子树 ，所以需要判断下
          //再将minright的右子树pminright
          if (pminright->_left == minright)
          {
            pminright->_left = minright->_right;
          }
          else
          {
            pminright->_right = minright->_right;
          }
          delete minright;
        }
        return true;
      }
    }
    //说明要删除的数据不存在
    return false;
  }
  //--------- 递归
    bool _FindR(Node * root, const K & key)//查找
  {
    if (root == nullptr)
    {
      return false;
    }
    if (root->_key == key)
    {
      return true;
    }
    if (root->_key < key)
    {
      return  _FindR(root->_right, key);
    }
    else 
    {
      return  _FindR(root->_left, key);
    }
  }
  bool FindR(const K & key)
  {
    return _FindR(_root, key);
  }
  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;
    }
  }
  bool InsertR(const K& key)
  {
    return _InsertR(_root,key);
  }
  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 == nullptr)//左为空
      {
        root = root->_right;
      }
      else if (root->_right == nullptr)//右为空
      {
        root = root->_left;
      }
      else
      {
        //替代法
        Node* maxleft = root->_left;
        //在左子树中寻找最右 作为左子树最大节点
        while (maxleft->_right != NULL)
        {
          maxleft = maxleft->_right;
        }
        swap(maxleft, root);
        return EeaseR(root->_left, key);
      }
      delete del;
      return true;
    }
  }
  bool EraseR(const K&key)
  {
    return _EraseR(_root,key);
  }
  void Destroy(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    Destroy(root->_left);
    Destroy(root->_right);
    delete root;
  }
private:
  Node* _root = nullptr;
};

应用搜索场景

1. key模型

在不在

1.门禁系统

2.车库系统

3.检查一篇文章中单词拼写是否正确

你拼写的单词是否在库中，若库则说明拼写正确，若不在，则说明拼写错误

key模型与上述实现的二叉搜索树基本一致

2. key value 模型

1.中英文互译字典

2.电话号码查询快递信息

3. 电话号码+验证码查询考试成绩

4.统计水果出现的次数

key value模型与上述实现的二叉搜索树实现功能差不多，只是增加了一个模板参数value

中英文互译字典的简单实现

通过插入将预先设置好的单词与对应意思输入树中，

输入str时，在树中查找该单词是否存在

若找到则返回节点指针指向的value，若没找到则返回nuullptr

统计水果出现次数的简单实现

3. key value模型代码

#pragma once
#include<iostream>
using namespace std;
namespace key_value
{
  template <class K,class V>//key  
  //BSTree -- BinarySearchTree
  struct BSTreeNode
  {
    BSTreeNode<K,V>* _left;//左
    BSTreeNode<K,V>* _right;//右
    K  _key;//key值
    V _value;//value值
    BSTreeNode(const K& key, const V& value)
      :_left(nullptr), _right(nullptr), _key(key), _value(value)
    {
    }
  };
  template <class K,class V>
  class BSTree
  {
    typedef BSTreeNode<K, V> Node;
  public:
    //插入
    bool Insert(const K& key, const V& value)
    {
      if (_root == NULL)//若root根节点为nullptr
      {
        _root = new Node(key, value);
        return true;
      }
      Node* cur = _root;
      Node* parent = nullptr;//用于接收cur之前的节点
      while (cur != NULL)
      {
        if (cur->_key > key)//若插入的值比cur值小
        {
          parent = cur;
          cur = cur->_left;
        }
        else if (cur->_key < key)//若插入的值比cur值大
        {
          parent = cur;
          cur = cur->_right;
        }
        else//若相等，则直接返回false
        {
          return false;
        }
      }
      //遇见空指针，连接新节点
      //由于不知道parent的左还是右连接key，所以需要判断
      cur = new Node(key, value);
      if (parent->_key < key)
      {
        parent->_right = cur;
      }
      else
      {
        parent->_left = cur;
      }
      return true;
    }
    //查找
    Node* Find(const K& key)
    {
      Node* cur = _root;
      while (cur != NULL)
      {
        if (cur->_key > key)
        {
          cur = cur->_left;
        }
        else if (cur->_key < key)
        {
          cur = cur->_right;
        }
        else
        {
          return cur;//成功就返回当前节点
        }
      }
      return nullptr;//失败就返回空
    }
    //中序遍历
    void inorder()
    {
      _inorder(_root);
    }
    void _inorder(Node* root)
    {
      if (root == NULL)
      {
        return;
      }
      _inorder(root->_left);//左
      cout << root->_key << ":"<<root->_value<<endl;//根
      _inorder(root->_right);//右  
    }
  private:
    Node* _root = nullptr;
  };
}

【C++】二叉搜索树（下）

右为空

删除节点有左孩子和右孩子节点

整体代码

二叉搜索树的实现 (递归)

查找

插入

删除

二叉搜索树实现的整体代码

应用搜索场景

1. key模型

2. key value 模型

3. key value模型代码

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++】二叉搜索树（下）

右为空

删除节点有左孩子和右孩子节点

整体代码

二叉搜索树的实现 (递归)

查找

插入

删除

二叉搜索树实现的整体代码

应用搜索场景

1. key模型

2. key value 模型

3. key value模型代码

热门文章

最新文章

相关课程

相关电子书