【C++高阶(一)】二叉搜索树深度剖析

从本篇文章开始正式进入C++高阶
的学习,C++高阶主要包括二叉搜索树
,AVL树,红黑树,哈希等高阶数据结构,
以及C++11和智能指针,抛异常等等.
高阶的内容往往是与普通人拉开差距的
内容,请同学们耐心学习!

[1,3,4,6,7,8,10,14,13] 有序序列

template<class K>
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;
private:
  Node* _root = nullptr;
}

bool insert(const K& key)//左小右大
{
  if (_root == nullptr)//第一次插入时的操作
  {
    _root = new Node(key);
    return true;
  }
  Node* cur = _root;
  Node* prev = nullptr;
  while (cur != nullptr)
  {
    if (cur->_key < key)
    {
      prev = cur;
      cur = cur->_right;
    } 
    else if (cur->_key > key)
    {
      prev = cur;
      cur = cur->_left;
    }
    else if (cur->_key == key)
      return false;
  }
  cur = new Node(key);
  if (prev->_key > key)
    prev->_left = cur;
  else
    prev->_right = cur;
  return true;
}

bool erase(const K& key)//非递归版本
{
Node* prev = nullptr;
Node* cur = _root;
while (cur != nullptr)//先找到此节点再删除
{
  if (cur->_key < key)
  {
    prev = cur;
    cur = cur->_right;
  }
  else if (cur->_key > key)
  {
    prev = cur;
    cur = cur->_left;
  }
  else//找到了此节点后,开始删除
  {
    //1. 左边为空
    //2. 右边为空
    //3. 左右都不为空
    if (cur->_left == nullptr)//左孩子为空情况
    {
      if (cur == _root)
        _root = cur->_right;
      else
      {
        if (cur == prev->_left)
          prev->_left = cur->_right;
        else
          prev->_right = cur->_right;
      }
      delete cur;
      return true;
    }
    else if (cur->_right == nullptr)//右孩子为空情况
    {
      if (cur == _root)
        _root = cur->_left;
      else
      {
        if (cur == prev->_left)
          prev->_left = cur->_left;
        else
          prev->_right = cur->_left;
      }
      delete cur;
      return true;
    }
}

//注,此时的cur即为要删除的节点
Node* tmp = cur->_right;
Node* prevtmp = cur;
while (1) //寻找右子树中的最左节点
{
  if (tmp->_left != nullptr)
  {
    prevtmp = tmp;
    tmp = tmp->_left;
  }
  else
    break;
}
cur->_key = tmp->_key;
if (tmp->_right == nullptr)//如果被替换的节点的右为空
{
  if (prevtmp == cur)//被删除节点右边只有一个节点,直接将被删除节点的右置空
    prevtmp->_right = nullptr;
  else
    prevtmp->_left = nullptr;
  delete tmp;
  tmp = nullptr;
}
else
{
  if (prevtmp == cur)
    prevtmp->_right = tmp->_right;
  else
    prevtmp->_left = tmp->_right;
  delete tmp;
  tmp = nullptr;
}