【C++练级之路】【Lv.14】二叉搜索树（进化的二叉树—

引言

二叉树在之前的数据结构章节讲解过，当时使用C来实现。而如今学习的二叉搜索树，便是二叉树的进阶，也更适合使用C++来实现。

一、二叉搜索树介绍

二叉搜索树（BST，Binary Search Tree），又称为二叉排序树。

它满足以下性质：

非空左子树的所有键值小于其根结点的键值
非空右子树的所有键值大于其根结点的键值
左右子树均为二叉搜索树

二、二叉搜索树的模拟实现

2.1 结点

template<class K>
struct BSTreeNode
{
  BSTreeNode<K>* _left;
  BSTreeNode<K>* _right;
  K _key;

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

细节：在二叉搜索树中，一般更喜欢用K作为模板参数，用key作为数据，称为键值。

2.2 成员变量

template<class K>
class BSTree
{
  typedef BSTreeNode<K> Node;
protected:
  Node* _root = nullptr;
};

2.3 默认成员函数

2.3.1 constructor

//写法一
BSTree()
  : _root(nullptr)
{}
//写法二
BSTree() = default;//强制生产默认构造

2.3.2 copy constructor

BSTree(const BSTree<K>& 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;
}

细节：写一个子函数Copy，进行前序遍历递归拷贝

2.3.3 operator=

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

细节：现代写法，直接拷贝完交换

2.3.4 destructor

~BSTree()
{
  Destroy(_root);
}

void Destroy(Node*& root)
{
  if (root == nullptr)
  {
    return;
  }

  Destroy(root->_left);
  Destroy(root->_right);
  delete root;
  root = nullptr;
}

细节：

写一个子函数Destroy，进行后序遍历递归释放
参数为Node*&，这样就可以在函数内置空根节点

2.4 中序遍历

为什么只介绍中序遍历呢？二叉搜索树，之所以又称为二叉排序树，是因为在中序遍历时，便能将数据按升序遍历。

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

void _InOrder(Node* root)
{
  if (root == nullptr)
  {
    return;
  }

  _InOrder(root->_left);
  cout << root->_key << " ";
  _InOrder(root->_right);
}

细节：同样，一般要递归写一个子函数，再进行传参控制

2.5 查找

二叉搜索树，其最大优势肯定是在于搜索！

2.5.1 迭代实现

bool Find(const K& key)
{
  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;
}

细节：

查找的key比当前结点的_key大，则往右查找
查找的key比当前结点的_key小，则往左查找
找到返回true，走到空找不到返回false

2.5.2 递归实现

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

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;
  }
}

2.6 插入

2.6.1 迭代实现

bool Insert(const K& key)
{
  if (_root == nullptr)
  {
    _root = new Node(key);
    return true;
  }

  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
    {
      return false;
    }
  }

  cur = new Node(key);
  if (parent->_key < key)
  {
    parent->_right = cur;
  }
  else
  {
    parent->_left = cur;
  }
  return true;
}

细节：

若根为空，直接创建结点，返回true
设置parent变量，记录父节点，以便在cur走到空时进行插入
插入前，要判断用左指针还是右指针链接

2.6.2 递归实现

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 (root->_key < key)
  {
    return _InsertR(root->_right, key);
  }
  else if (root->_key > key)
  {
    return _InsertR(root->_left, key);
  }
  else
  {
    return false;
  }
}

细节：参数为Node*&，使得当前root为空，却可以直接创建节点链接（因为此时root是其父节点左右指针的引用）

2.7 删除

2.7.1 迭代实现

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->_right == nullptr)//右子树为空
      {
        if (cur == _root)
        {
          _root = _root->_left;
        }
        else
        {
          if (parent->_right == cur)
          {
            parent->_right = cur->_left;
          }
          else
          {
            parent->_left = cur->_left;
          }
        }
        delete cur;
      }
      else if (cur->_left == nullptr)//左子树为空
      {
        if (cur == _root)
        {
          _root = _root->_right;
        }
        else
        {
          if (parent->_left == cur)
          {
            parent->_left = cur->_right;
          }
          else
          {
            parent->_right = cur->_right;
          }
        }
        delete cur;
      }
      else//左右子树均不为空
      {
        //这里选择找右子树的最左节点
        Node* pminRight = cur;
        Node* minRight = cur->_right;
        while (minRight->_left)
        {
          pminRight = minRight;
          minRight = minRight->_left;
        }

        cur->_key = minRight->_key;

        if (pminRight->_right == minRight)
        {
          pminRight->_right = minRight->_right;
        }
        else
        {
          pminRight->_left = minRight->_right;
        }

        delete minRight;
      }
      return true;
    }
  }
  return false;
}

细节：

首先依然要parent记录父节点，进行查找
找到了，分三种删除情况：

右子树为空
左子树为空
左右子树均不为空

左右子树一边为空时，先判断parent是否为空，如果为空，代表cur为_root，需要移动_root；如果不为空，则再判断左右指针链接
左右子树均不为空时，寻找右子树的最左结点minRight（也可以是左子树的最右结点）来替代cur，注意minRight可能有孩子，还要设置pminRight记录其父节点位置，判断左右指针链接

2.7.2 递归实现

bool EraseR(const K& key)
{
  return _EraseR(_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->_right == nullptr)//右子树为空
    {
      root = root->_left;
    }
    else if (root->_left == nullptr)//左子树为空
    {
      root = root->_right;
    }
    else
    {
      Node* minRight = root->_right;
      while (minRight->_left)
      {
        minRight = minRight->_left;
      }

      swap(root->_key, minRight->_key);
      return _EraseR(root->_right, key);
    }
    delete del;
    return true;
  }
}

细节：

参数为Node*&，使得左右子树一边为空时，不用判断，直接链接（将两种情况一并处理了）
左右子树均不为空时，交换待删除root和minRight的键值key，再递归其右子树删除

三、二叉搜索树的应用

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

四、二叉树进阶面试题

二叉树进阶面试题

一、根据二叉树创建字符串

二、二叉树的层序遍历

三、二叉树的最近公共祖先

四、二叉搜索树转换双向链表

五、构造二叉树

5.1 前序与中序

5.2 中序与后序

六、二叉树的前中后序遍历（非递归）

6.1 前序

6.2 中序

6.3 后序

真诚点赞，手有余香

【C++练级之路】【Lv.14】二叉搜索树（进化的二叉树——BST）

引言