二叉搜索树

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

二叉搜索树实现

非递归插入|非递归查找

#include<iostream>
using namespace std;
template<class K>
class BStreeNode
{
public:
  BStreeNode(const K& key)
    :_left(nullptr),
    _right(nullptr),
    _key(key)
  {}
  BStreeNode<K>* _left;
  BStreeNode<K>* _right;
  K _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)
    {
      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;
  }
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 true;
  }
  void InOrder()
  {
    _InOrder(_root);
  }
private:
  void _InOrder(Node *root)
  {
    if (root == nullptr)
      return;
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
  }
private:
  Node* _root = nullptr;
};
int main()
{
  BStree<int> t;
  int a[] = { 1,1,2,2,3,6,165,132,4185,123 };
  for (auto e : a)
  {
    t.Insert(e);
  }
  t.InOrder();
  return 0;
}

可去重

删除

推导阶段

1.若要删除的节点是叶子节点，直接删除即可

2.删除节点只有一个孩子

若左为空，则让父亲节点指向该节点的右子树以删除3为例

若果要删除跟节点，而且左为空，若要删除8，我们更新根节点即可，让根节点指向10

若右为空，则让父亲指向左子树，以删除14为例

若果要删除跟节点，而且右为空，若要删除8，让根节点指向3即可

3.要删除的节点其左右节点都不为空

我们可以采用替换法删除节点

用左子树的最大节1点或右子树的最小节点4，若采用右树的最小节点，交换3和4删除4之后，删除3，但还有一个子节点5，我们让5成为6的左节点

若要删除8，这里采用右树最左节点的替换法，右树的最左节点就是10自己，如果这样写会有错误，while循环都不会进去，minparent就是空，而后面minParent->_left = min->_right;这个语句会出错，修正方法，让minparent一开始就是cur，并且加个判断。

这样写即可

非递归删除代码

  bool Erase(const K& key)//删除
  {
    //若有一个子节点，删除父节点后，让子节点填充
    //若有俩个子节点，父节点删除后
    //1.用左子树的最大节点替换父节点
    //2.或右子树的最小节点替换父节点
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      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;
          cur = nullptr;
        }
        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;
          cur = nullptr;
        }
        else//左右都为空，叶子节点,这里采用用右树的最小节点进行删除
        {
          Node* minParent = cur;
          Node*min = cur->_right;//cur是要删除的节点
          while (min->_left)//寻找最小节点
          {
            minParent = min;
            min = min->_left;
          }
          swap(cur->_key, min->_key);
          if (minParent->_left == min)
          {
            minParent->_left = min->_right;
          }
          else
          minParent->_right = min->_right;
          delete min;
        }
        return true;
      }
    }
    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;
    }
  }

递归插入

这种插入写法会导致二叉树断开

这里的Node没有跟父节点连接上，而是创建了一个空间单独在那里

加上引用即可

  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 _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->_left == nullptr)
      {
        root = root->_right;
      }
      else if (root->_right == nullptr)
      {
        root = root->_left;//由于是引用，可直接这样将二叉树连接起来
      }
      else
      {
        //找右树的最左节点
        Node* min = root->_right;
        while (min->_left)
        {
          min = min->_left;
        }
        swap(root->_key, min->_key);
        return _Eraser(root->_right, key);
      }
      delete del;
      return true;
    }
  }

析构函数

  ~BStree()
  {
Destory(_root);
  }
private:
  void Destory(Node*& root)//采用引用可让root置空起作用
  {
    if (root ==nullptr)
      return;
    Destory(root->_left);
    Destory(root->right);
    delete root;
    root=nullptr
  }

拷贝构造

注：拷贝构造也是构造，如果写了构造，编译器不会生成默认构造，会报错没有合适的默认构造

  BStree(const BStree<K> & t)
  {
    _root = _Copy(t._root);
  }
Node* _Copy(Node* root)
  {
    if (root == nullptr)
    {
      return nullptr;
    }
    Node* copyRoot = new Node(root->_key);
    copyRoot->_left = _Copy(root->_left);
    copyRoot->_right = _Copy(root->_right);
    return copyRoot;
  }

我们需加默认构造 
默认构造也可写为BSTree()=default;
这是强制编译器生成默认构造，是C++11的用法

赋值重载

1.  BStree<K>& operator=(BStree<K> t)
2.  {
3.    swap(_root, t._root);
4.    return *this;
5.  }

搜索二叉树增删查的时间复杂度是：O（h），h代表高度

完整代码

#include<iostream>
using namespace std;
template<class K>
class BStreeNode
{
public:
  BStreeNode(const K& key)
    :_left(nullptr),
    _right(nullptr),
    _key(key)
  {}
  BStreeNode<K>* _left;
  BStreeNode<K>* _right;
  K _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)
    {
      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;
  }
  void InOrder()//排序
  {
    _InOrder(_root);
  }
  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 true;
  }
  bool Erase(const K& key)//删除
  {
    //若有一个子节点，删除父节点后，让子节点填充
    //若有俩个子节点，父节点删除后
    //1.用左子树的最大节点替换父节点
    //2.或右子树的最小节点替换父节点
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      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;
          cur = nullptr;
        }
        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;
          cur = nullptr;
        }
        else//左右都为空，叶子节点,这里采用用右树的最小节点进行删除
        {
          Node* minParent = cur;
          Node* min = cur->_right;//cur是要删除的节点
          while (min->_left)//寻找最小节点
          {
            minParent = min;
            min = min->_left;
          }
          swap(cur->_key, min->_key);
          if (minParent->_left == min)
          {
            minParent->_left = min->_right;
          }
          else
            minParent->_right = min->_right;
          delete min;
        }
        return true;
      }
    }
    return false;
  }
  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);
  }
  ~BStree()
  {
    Destory(_root);
  }
  BStree()
  {}
  BStree(const BStree<K>& t)
  {
    _root = _Copy(t._root);
  }
  BStree<K>& operator=(BStree<K> t)
  {
    swap(_root, t._root);
    return *this;
  }
private:
  Node* _Copy(Node* root)
  {
    if (root == nullptr)
    {
      return nullptr;
    }
    Node* copyRoot = new Node(root->_key);
    copyRoot->_left = _Copy(root->_left);
    copyRoot->_right = _Copy(root->_right);
    return copyRoot;
  }
  void Destory(Node*& root)//采用引用可让root置空起作用
  {
    if (root == nullptr)
      return;
    Destory(root->_left);
    Destory(root->_right);
    delete root;
    root = nullptr;
  }
  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->_left == nullptr)
      {
        root = root->_right;
      }
      else if (root->_right == nullptr)
      {
        root = root->_left;//由于是引用，可直接这样将二叉树连接起来
      }
      else
      {
        //找右树的最左节点
        Node* min = root->_right;
        while (min->_left)
        {
          min = min->_left;
        }
        swap(root->_key, min->_key);
        return _Eraser(root->_right, key);
      }
      delete del;
      return true;
    }
  }
  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;
};
int main()
{
  BStree<int> t;
  int a[] = { 1,1,2,2,3,6,165,132,4185,123 };
  for (auto e : a)
  {
    t.Insert(e);
  }
  BStree<int> copy = t;
  copy.InOrder();
  t.InOrder();
  BStree<int> t1;
  t1.Insert(2);
  t1.Insert(1);
  t1.Insert(3);
  copy = t1;
  copy.InOrder();
  cout << endl;
  t1.InOrder();
  cout << endl;
  return 0;
}

二叉搜索树的应用

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

的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树

在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方

式在现实生活中非常常见：

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英

文单词与其对应的中文就构成一种键值对；

再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出

现次数就是就构成一种键值对

KV模型通过K去找V

Key/Value模型

namespace KeyValue
{
  template<class K, class V>
  struct BSTreeNode
  {
    BSTreeNode<K, V>* _left;//Key和Value绑到一起
    BSTreeNode<K, V>* _right;
    K _key;
    V _value;
    BSTreeNode(const K& key, const V& value)
      :_left(nullptr)
      , _right(nullptr)
      , _key(key)
      , _value(value)
    {}
  };
  template<class K, class V>
  class BSTree
  {
    typedef BSTreeNode<K, V> Node;
  public:
    bool Insert(const K& key, const V& value)
    {
      if (_root == nullptr)
      {
        _root = new Node(key, value);
        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, value);
      if (parent->_key < key)
      {
        parent->_right = cur;
      }
      else
      {
        parent->_left = cur;
      }
      return true;
    }
    Node* Find(const K& key)//查找的时候以K去查找，返回的时候返回节点指针，以便于修改
    {
      Node* cur = _root;
      while (cur)
      {
        if (cur->_key < key)
        {
          cur = cur->_right;
        }
        else if (cur->_key > key)
        {
          cur = cur->_left;
        }
        else
        {
          return cur;
        }
      }
      return nullptr;
    }
    bool Erase(const K& key)//用K删除
    {
      //...
      return true;
    }
    void InOrder()
    {
      _InOrder(_root);
      cout << endl;
    }
  private:
    void _InOrder(Node* root)
    {
      if (root == nullptr)
      {
        return;
      }
      _InOrder(root->_left);
      cout << root->_key << ":" << root->_value << endl;
      _InOrder(root->_right);
    }
  private:
    Node* _root = nullptr;
  };

英译汉

统计水果出现的次数

链表相交和复杂链表的赋值可用kv模型。

C++——二叉搜索树