【C++航海王：追寻罗杰的编程之路】一篇文章带你了解二叉搜索树

#pragma once
#include <iostream>
using namespace std;
 
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;
public:
  bool Insert(const K& key)
  {
    if (_root == nullptr)
    {
      _root = new Node(key);
      return true;
    }
 
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      parent = cur;
      if (cur->_key < key)
      {
        cur = cur->_right;
      }
      else if (cur->_key > key)
      {
        cur = cur->_left;
      }
      else
      {
        return false;
      }
    }
 
    cur = new Node(key);
    if (parent->_key < key)
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
 
    return true;
  }
 
  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;
  }
 
  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->_left == nullptr)
        {//左为空
          if (cur == _root)
          {
            _root = cur->_right;
          }
          else
          {
            if (cur == parent->_left)
            {
              parent->_left = cur->_right;
            }
            else
            {
              parent->_right = cur->_right;
            }
          }
 
          delete cur;
        }
        else if (cur->_right == nullptr)
        {//右为空
          if (cur == _root)
          {
            _root = cur->_left;
          }
          else
          {
            if (cur == parent->_left)
            {
              parent->_left = cur->_left;
            }
            else
            {
              parent->_right = cur->_left;
            }
          }
 
          delete cur;
        }
        else
        {//左右都不为空
 
          // 右树的最小节点(最左节点)
          Node* parent = cur;
          Node* subLeft = cur->_right;
          while (subLeft->_left)
          {
            parent = subLeft;
            subLeft = subLeft->_left;
          }
 
          swap(cur->_key, subLeft->_key);
 
          if (subLeft == parent->_left)
            parent->_left = subLeft->_right;
          else
            parent->_right = subLeft->_right;
 
          delete subLeft;
        }
 
        return true;
      }
    }
 
    return false;
  }
 
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
 
  bool FindR(const K& key)
  {
    return _FindR(_root, key);
  }
 
  bool InsertR(const K& key)
  {
    return _InsertR(_root, key);
  }
 
  bool EraseR(const K& key)
  {
    return _EraseR(_root, key);
  }
 
private:
  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
    {
      // 删除
      if (root->_left == nullptr)
      {
        Node* del = root;
        root = root->_right;
        delete del;
 
        return true;
 
      }
      else if (root->_right == nullptr)
      {
        Node* del = root;
        root = root->_left;
        delete del;
 
        return true;
      }
      else
      {
        Node* subLeft = root->_right;
        while (subLeft->_left)
        {
          subLeft = subLeft->_left;
        }
 
        swap(root->_key, subLeft->_key);
 
        // 转换成在子树去递归删除
        return _EraseR(root->_right, 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 _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;
    }
  }
 
  void _InOrder(Node* root)
  {
    if (root == nullptr)
      return;
 
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
  }
private:
  Node* _root = nullptr;
};

// 改造二叉搜索树为KV结构
template<class K, class V>
struct BSTNode
{
  BSTNode(const K& key = K(), const V& value = V())
    : _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value)
  {}
  BSTNode<T>* _pLeft;
  BSTNode<T>* _pRight;
  K _key;
  V _value
};
 
template<class K, class V>
class BSTree
{
  typedef BSTNode<K, V> Node;
  typedef Node* PNode;
public:
  BSTree() : _pRoot(nullptr) {}
  PNode Find(const K& key);
 
  bool Insert(const K& key, const V& value)
    bool Erase(const K& key)
 
private:
  PNode _pRoot;
};
 
void TestBSTree3()
{
  // 输入单词，查找单词对应的中文翻译
  BSTree<string, string> dict;
  dict.Insert("string", "字符串");
  dict.Insert("tree", "树");
  dict.Insert("left", "左边、剩余");
  dict.Insert("right", "右边");
  dict.Insert("sort", "排序");
 
  // 插入词库中所有单词
  string str;
  while (cin >> str)
  {
    BSTreeNode<string, string>* ret = dict.Find(str);
    if (ret == nullptr)
    {
      cout << "单词拼写错误，词库中没有这个单词:" << str << endl;
    }
    else
    {
      cout << str << "中文翻译:" << ret->_value << endl;
    }
  }
}
 
void TestBSTree4()
{
  // 统计水果出现的次数
  string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
   "苹果", "香蕉", "苹果", "香蕉" };
  BSTree<string, int> countTree;
 
  for (const auto& str : arr)
  {
    // 先查找水果在不在搜索树中
    // 1、不在，说明水果第一次出现，则插入<水果, 1>
    // 2、在，则查找到的节点中水果对应的次数++
    //BSTreeNode<string, int>* ret = countTree.Find(str);
    auto ret = countTree.Find(str);
    if (ret == NULL)
    {
      countTree.Insert(str, 1);
    }
    else
    {
      ret->_value++;
    }
  }
 
  countTree.InOrder();
}