【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）

引言

一、二叉搜索树介绍

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

2.1 结点

2.2 成员变量

2.3 默认成员函数

2.3.1 constructor

2.3.2 copy constructor

2.3.3 operator=

2.3.4 destructor

2.4 中序遍历

2.5 查找

2.5.1 迭代实现

2.5.2 递归实现

2.6 插入

2.6.1 迭代实现

2.6.2 递归实现

2.7 删除

2.7.1 迭代实现

2.7.2 递归实现

三、二叉搜索树的应用

四、二叉树进阶面试题

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

引言

一、二叉搜索树介绍

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

2.1 结点

2.2 成员变量

2.3 默认成员函数

2.3.1 constructor

2.3.2 copy constructor

2.3.3 operator=

2.3.4 destructor

2.4 中序遍历

2.5 查找

2.5.1 迭代实现

2.5.2 递归实现

2.6 插入

2.6.1 迭代实现

2.6.2 递归实现

2.7 删除

2.7.1 迭代实现

2.7.2 递归实现

三、二叉搜索树的应用

四、二叉树进阶面试题

热门文章

最新文章

相关课程

相关电子书