二叉搜索树-阿里云开发者社区

二叉搜索树

2024-05-10 13

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 二叉搜索树

1 搜索二叉树的定义

在二叉树的定义的基础上，在加上以下两种特征的树就叫做二叉搜索树：

1️⃣任何一棵子树的左节点的值都要大于根节点的值

2️⃣任何一棵子树的右节点都要小于根节点的值

所以二叉搜索树的中序遍历一定是有序的！

2 搜索二叉树的实现

我们需要一个节点，以下是节点模块

template<class K>
struct BSTreeNode {
  typedef BSTreeNode<K> Node;
  K _val;
  Node* _left;
  Node* _right;

    BSTreeNode(const K& val = K())
    :_val(val)
    ,_left(nullptr)
    ,_right(nullptr)
  {}
};

我们再来定义一个二叉搜索树的类

  template<class K>
  class BinarysearchTree {
  public:
    typedef BSTreeNode<K> Node;
    bool FindK(const K& key)();
    //插入
    bool Insert(const K& key)();
    //删除
    bool erase(const K& key)();
  private:
    Node* _root = nullptr;
  };

2.1 查找函数


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

2.2 插入操作

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

2.3 删除操作

和查找一样，首先就是要找到所要删除节点的位置！

2.3.1 左为空

如果删除的节点是左为空的节点，此时就会有以下三种示意图的情况

2.3.2 右为空

如果删除的节点是右为空的节点，此时也会有三种情况，如下图所示：

2.3.3 左右都不为空

如果删除的节点是左右都不为空的节点，此时就需要去右子树中寻找到最小值（也可以去左子树中找到最大值），进行交换，然后进行删除

完整的实现代码如下：

//删除
bool erase(const K& key)
{
  Node* cur = _root;
  Node* curParent = cur;
  
  while (cur)
  {
    if (key > cur->_val)
    {
      curParent = cur;
      cur = cur->_right;
    }
    else if (key < cur->_val)
    {
      curParent = cur;
      cur = cur->_left;
    }
    else {
      if (cur->_left == nullptr)
      {
        if (_root->_left == nullptr)
        {
          _root = _root->_right;
          return true;
        }
        if (cur == curParent->_left)
        {
          curParent->_left = cur->_right;   
        }
        else {
          curParent->_right = cur->_right;
        }
        delete cur;
        return true;
      }
      else if (cur->_right == nullptr)
      {
        if (_root->_right == nullptr)
        {
          _root = _root->_left;
          return true;
        }
        if (cur == curParent->_left)
        {
          curParent->_left = cur->_left;
        }
        else {
          curParent->_right = cur->_left;
        }
        delete cur;
        return true;
      }
      else {
        Node* curNext= cur->_right;
        curParent = cur;
        while (curNext->_left)
        {
          cur = curNext;
          curNext = curNext->_left;
        }

        curParent->_val = curNext->_val;

        if (cur->_right == curNext)
        {
          cur->_right = curNext->_right;
          
        }
        else {
          cur->_left = curNext->_right;
        }
        delete curNext;
        return true;
      }
    }
  }
  return false;
}