【C++】二叉搜索树

介绍：

一，二叉搜索树操作

1，搜索二叉树的简单封装

2，二叉搜索树的查找

3，二叉搜索树的插入

4，二叉搜索树的删除

二，递归实现二叉搜索树的操作

1，二叉搜索树的递归查找

2，二叉搜索树的递归插入

3，二叉搜索树的递归删除

三，构造函数、析构函数和赋值运算符重载

四，二叉搜索树的综合实现

介绍：

二叉搜索树又称二叉排序树。它或者是一棵空树，或者是具有这样性质的二叉树：若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。它的左右子树也分别为二叉搜索树。如下图：

一，二叉搜索树操作

1，搜索二叉树的简单封装

搜索二叉树的节点封装很好设计，这里跟普通二叉树的节点设计一样，而搜索二叉树的封装设计只需包含根节点即可，因为具体功能设计都是通过根节点开始进行的。代码如下：

template <class K>
struct BSTreeNode
{
   BSTreeNode(const K& x = K())
       : _key(x)
       , _left(nullptr)
       , _right(nullptr)
   {   }
   typedef BSTreeNode<K> Node;
   Node* _left; //左子树
   Node* _right; //右子树
   K _key; //数据
};

template <class K>
class BSTree
{
   typedef BSTreeNode<K> Node;
public:

.........
private:
   Node* _root; //根节点
};

2，二叉搜索树的查找

由于二叉搜索树的这种结构，我们可从根开始比较查找，比根大则往右边走查找，比根小则往左边走查找，依次往下走，直到走到为空，若还没找到，这个值不存在。

bool Find(const K& x) {
   Node* cur = _root;
   while (cur) {
       if (cur->_key > x) {
           cur = cur->_left;
       }
       else if (cur->_key < x) {
           cur = cur->_right;
       }
       else {
           return true;
       }
   }
   return false;
}

3，二叉搜索树的插入

在插入中，分为两种情况，当树为空时，则直接新增节点，然后将此节点赋值给根节点root；当树不为空时，按二叉搜索树性质不断往下查找，将其插入到最末尾的合适位置。如下图：

bool Insert(const K& x) {
   Node* cur = _root;
   Node* parent = _root;
   if (cur == nullptr) {
       _root = new Node(x);
       return true;
   }
   while (cur) {
       if (cur->_key > x) {
           parent = cur;
           cur = cur->_left;
       }
       else if (cur->_key < x) {
           parent = cur;
           cur = cur->_right;
       }
       else {
           return false; //插入失败，二叉搜索树中已有此数据
       }
   }
   cur = new Node(x);
   if (parent->_key < x) {
       parent->_right = cur;
   }
   else {
       parent->_left = cur;
   }
   return true;
}

4，二叉搜索树的删除

二叉搜索树的删除较为麻烦，通常使用替换法删除。删除的节点也分三种情况而论，即要删除节点没有孩子、有一个孩子、有两个孩子。

当要删除的节点有一个孩子时，这里也分两种情况：当此节点只有左孩子，没有右孩子时，删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点，可直接删除。当此节点只有右孩子，没有左孩子时，删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点，也可直接删除。

当要删除的节点没有孩子时情况就很简单了，这里可归并到只有一个节点时的情况。无论被删除节点的双亲结点指向被删除节点的左孩子还是右孩子，都为空。

当要删除的节点有两个孩子时，需用替换法删除，即找到一个节点数据，此节点可以替换被删除节点的数据，然后交换被删除的节点，进行转移的删除。这里在寻找可替代被删除节点的节点时，寻找的规则是左子树的最大节点(左子树的最右孩子)或右子树的最小节点(右子树的最左孩子)。因为此节点必须满足大于左子树的所有节点值，小于右子树的所有节点值，最终替换后要删除的节点就变成了只有一个孩子或没有孩子的节点，然后根据只有一个孩子或没有孩子的情况进行操作。

这里要注意的是要考虑当删除节点为头节点时的情况，思想仍与上一样。

bool Erase(const K& key) {
   Node* cur = _root;
   Node* parent = _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 (parent->_left == cur) {
                   parent->_left = cur->_right;
               }
               else {
                   parent->_right = cur->_right;
               }
               delete cur;
               cur = nullptr;
               return true;
           }
           //当要删除的节点只有左子树没有右子树或为根节点的情况
           else if (cur->_right == nullptr) {
               if (cur == _root) { //删除节点为头节点时的情况
                   _root = cur->_left;
               }
               else if (parent->_left == cur) {
                   parent->_left = cur->_left;
               }
               else {
                   parent->_right = cur->_left;
               }
               delete cur;
               cur = nullptr;
               return true;
           }
           //当要删除的节点有左右子树的情况，即替换法
           //这里我们使用查找左边最大（也可使用查找右边最小）
           else {
               Node* LeftMaxNode = cur->_left;
               Node* LeftMaxNodeParent = cur;
               while (LeftMaxNode->_right) {
LeftMaxNodeParent = LeftMaxNode;
                   LeftMaxNode = LeftMaxNode->_right;
               }
               swap(cur->_key, LeftMaxNode->_key);
               if (LeftMaxNodeParent == cur) { //当没有进入循环时的情况
                   LeftMaxNodeParent->_left = LeftMaxNode->_left;
               }
               else {
                   LeftMaxNodeParent->_right = LeftMaxNode->_left;
               }
               delete LeftMaxNode;
               LeftMaxNode = nullptr;
               return true;
           }
       }
   }
   return false; //表示不存在要删除的数据
}

二，递归实现二叉搜索树的操作

1，二叉搜索树的递归查找

在封装操作中，由于根节点是内部数据，不能直接访问，所以这里要套装一个递归结构。具体实现只需遍历整个结构，直到找到指定数据不断返回即可。

//运用时，直接调用FindB即可

bool FindB(const K& key) {
   return _FindB(_root, key);
}

//递归查找的具体实现
bool _FindB(Node* root, const K& key) {
   if (root == nullptr) {
       return false;
   }
   if (root->_key > key) {
       return _FindB(root->_left, key);
   }
   else if (root->_key < key) {
       return _FindB(root->_right, key);
   }
   else {
       return true;
   }
}

2，二叉搜索树的递归插入

递归插入操作与查找思想基本一致，先遍历，找到合适位置后进行插入。这里问题是要如何保证连接，其实很简单，这里可使用指向指针的引用，当不断递归左子树右子树遍历时，此时的遍历节点就是上一次递归遍历的孩子。当找到合适位置后直接插入即可。

//运用时，直接调用InsertB即可

bool InsertB(const K& key) {
   return _InsertB(_root, key);
}

//具体递归功能的实现
bool _InsertB(Node*& root, const K& key) { //运用指向指针的引用
   if (root == nullptr) {
       root = new Node(key);
       return true;
   }
   if (root->_key > key) {
       return _InsertB(root->_left, key);
   }
   else if (root->_key < key) {
       return _InsertB(root->_right, key);
   }
   else {
       return false;
   }
}

3，二叉搜索树的递归删除

递归删除时，为了保证删除节点后正确连接，所以这里递归参数要使用指向指针的引用。

当被删除节点的左子树为空或右子树为空或为叶子节点时可直接将被删除节点的左或右子树将其节点覆盖，然后直接删除即可。

当被删除节点的左右子树都不为空时，跟原来的一样进行替换，这里使用左子树找最大(也可使用右子树找最小)，然后以此时替换节点的左子树开始递归遍历去寻找要删除的节点(使用右子树找最小去此时替换节点的右子树开始递归遍历寻找要删除的节点)，这时被删除的节点要么只有一个孩子，要么没有孩子，就回到了简单的情况。

注意：这里以替换节点的左子树开始递归遍历去寻找要删除的节点或使用右子树找最小去此时替换节点的右子树开始递归遍历寻找要删除的节点，是因为若以替换节点开始递归寻找会找不到被删除的节点，若直接递归传入删除节点的位置，会导致有些节点指向不为空的情况。

bool EraseB(const K& key) {
   return _EraseB(_root, key);
}
bool _EraseB(Node*& root, const K& key) {
   if (root == nullptr) {
       return false;
   }
   if (root->_key > key) {
       return _EraseB(root->_left, key);
   }
   else if (root->_key < key) {
       return _EraseB(root->_right, key);
   }
   else {

//左子树为空的情况
       if (root->_left == nullptr) {

//注意，由于这里指针指向的不是引用，所以对其赋值操作时不是对原本搜索二叉树的操作

//这里也不能使用引用，因为下面的释放空间会出问题
           Node* node = root;
           root = root->_right; //指针引用使用，可改变原结构
           delete node;
           node = nullptr;
           return true;
       }

//右子树为空的情况
       else if (root->_right == nullptr) {
           Node* node = root; //与上同理
           root = root->_left; //指针引用使用，可改变原结构
           delete node;
           node = nullptr;
           return true;
       }

//左右子树都不为空时的情况
       else {
           //这里替换左子树最大值
           Node* LeftMaxNode = root->_left;
           while (LeftMaxNode->_right) {
               LeftMaxNode = LeftMaxNode->_right;
           }
           swap(LeftMaxNode->_key, root->_key);
           //注意:return _EraseB(LeftMaxNode, key);是错误的，因为当删除节点后，无法使此时的指向为空，导致遍历出错
           return _EraseB(root->_left, key); //递归遍历左子树

       }
   }
}

三，构造函数、析构函数和赋值运算符重载

普通构造函数的实现只需把类中的个根节点初始化为nullptr即可，拷贝构造函数的实现要进行深拷贝。由于拷贝构造函数的实现跟赋值运算符重载效果一样，这里拷贝构造函数可直接调用赋值运算符重载(注意: 构造函数不能自己调用，所以不能用赋值运算符调用拷贝构造)。至于析构函数的实现直接使用后序遍历释放空间即可，前序和中序都不行。

//普通构造函数

BSTree() : _root(nullptr) {   }

//拷贝构造函数

BSTree(const BSTree<K>& t) {
   *this = t; //直接调用赋值运算符
}

//赋值运算符重载

BSTree<K>& operator=(const BSTree<K>& t) {
   if (this->_root) { //注意赋值前要先清空原数据
       Destory(this->_root);
   }
   Copy(this->_root, t._root);
   return *this;
}
void Copy(Node*& _root, const Node* root) {
   if (root == nullptr) {
       return;
   }
   _root = new Node(root->_key);
   Copy(_root->_left, root->_left);
   Copy(_root->_right, root->_right);
}

//析构函数
~BSTree()
{
   Destory(_root);
}

//注意: 这里形参不可为const Node*& root,因为这里const修饰的是Node*,不是引用
//传入的_root是Node*，使用const Node*& root类型是const Node*,属于不同类型转换，会产生临时变量，此时就必须用const修饰引用(注意:const必须修饰的是引用)
//若使用常引用，将不能给常引用赋值
void Destory(Node*& root) {
   if (root == nullptr) {
       return;
   }
   Destory(root->_left);
   Destory(root->_right);
   delete root;
   root = nullptr;
}

四，二叉搜索树的综合实现

综合结构这里只用封装即可，代码如下：

#pragma once
#include <iostream>
using namespace std;
namespace bite
{
   template <class K>
   struct BSTreeNode
   {
       BSTreeNode(const K& x = K())
           : _key(x)
           , _left(nullptr)
           , _right(nullptr)
       {   }
       typedef BSTreeNode<K> Node;
       Node* _left;
       Node* _right;
       K _key;
   };
   template <class K>
   class BSTree
   {
       typedef BSTreeNode<K> Node;
   public:
       BSTree() : _root(nullptr) {   }
       //这里也可强制生成默认构造：BSTree() = default;
       BSTree(const BSTree<K>& t) {
           *this = t;
       }
       BSTree<K>& operator=(const BSTree<K>& t) {
           if (this->_root) { //注意赋值前要先清空原数据
               Destory(this->_root);
           }
           Copy(this->_root, t._root);
           return *this;
       }
       bool Find(const K& x) {
           Node* cur = _root;
           while (cur) {
               if (cur->_key > x) {
                   cur = cur->_left;
               }
               else if (cur->_key < x) {
                   cur = cur->_right;
               }
               else {
                   return true;
               }
           }
           return false;
       }
       bool Insert(const K& x) {
           Node* cur = _root;
           Node* parent = _root;
           if (cur == nullptr) {
               _root = new Node(x);
               return true;
           }
           while (cur) {
               if (cur->_key > x) {
                   parent = cur;
                   cur = cur->_left;
               }
               else if (cur->_key < x) {
                   parent = cur;
                   cur = cur->_right;
               }
               else {
                   return false; //插入失败，二叉搜索树中已有此数据
               }
           }
           cur = new Node(x);
           if (parent->_key < x) {
               parent->_right = cur;
           }
           else {
               parent->_left = cur;
           }
           return true;
       }
       bool Erase(const K& key) {
           Node* cur = _root;
           Node* parent = _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 (parent->_left == cur) {
                           parent->_left = cur->_right;
                       }
                       else {
                           parent->_right = cur->_right;
                       }
                       delete cur;
                       cur = nullptr;
                       return true;
                   }
                   //当要删除的节点只有左子树没有右子树或为根节点的情况
                   else if (cur->_right == nullptr) {
                       if (cur == _root) { //删除节点为头节点时的情况
                           _root = cur->_left;
                       }
                       else if (parent->_left == cur) {
                           parent->_left = cur->_left;
                       }
                       else {
                           parent->_right = cur->_left;
                       }
                       delete cur;
                       cur = nullptr;
                       return true;
                   }
                   //当要删除的节点有左右子树的情况，即替换法
                   //这里我们使用查找左边最大（也可使用查找右边最小）
                   else {
                       Node* LeftMaxNode = cur->_left;
                       Node* LeftMaxNodeParent = cur;
                       while (LeftMaxNode->_right) {
                           LeftMaxNodeParent = LeftMaxNode;
                           LeftMaxNode = LeftMaxNode->_right;
                       }
                       swap(cur->_key, LeftMaxNode->_key);
                       if (LeftMaxNodeParent == cur) { //当没有进入循环时的情况
                           LeftMaxNodeParent->_left = LeftMaxNode->_left;
                       }
                       else {
                           LeftMaxNodeParent->_right = LeftMaxNode->_left;
                       }
                       delete LeftMaxNode;
                       LeftMaxNode = nullptr;
                       return true;
                   }
               }
           }
           return false; //表示不存在要删除的数据
       }

       //递归的实现
       bool FindB(const K& key) {
           return _FindB(_root, key);
       }
       bool InsertB(const K& key) {
           return _InsertB(_root, key);
       }
       bool EraseB(const K& key) {
           return _EraseB(_root, key);
       }
       void Inorder() {
           _Inorder(_root);
           cout << endl;
       }
       ~BSTree()
       {
           Destory(_root);
       }
   private:
       Node* _root;
       void Copy(Node*& _root, const Node* root) {
           if (root == nullptr) {
               return;
           }
           _root = new Node(root->_key);
           Copy(_root->_left, root->_left);
           Copy(_root->_right, root->_right);
       }
       void _Inorder(const Node* root) {
           if (root == nullptr) {
               return;
           }
           _Inorder(root->_left);
           cout << root->_key << " ";
           _Inorder(root->_right);
       }
       //注意: 这里形参不可为const Node*& root,因为这里const修饰的是Node*,不是引用
       //传入的_root是Node*，使用const Node*& root类型是const Node*,属于不同类型转换，会产生临时变量，此时就必须用const修饰引用(注意:const必须修饰的是引用)
       //若使用常引用，将不能给常引用赋值
       void Destory(Node*& root) {
           if (root == nullptr) {
               return;
           }
           Destory(root->_left);
           Destory(root->_right);
           delete root;
           root = nullptr;
       }
       bool _FindB(Node* root, const K& key) {
           if (root == nullptr) {
               return false;
           }
           if (root->_key > key) {
               return _FindB(root->_left, key);
           }
           else if (root->_key < key) {
               return _FindB(root->_right, key);
           }
           else {
               return true;
           }
       }
       bool _InsertB(Node* &root, const K& key) {
           if (root == nullptr) {
               root = new Node(key);
               return true;
           }
           if (root->_key > key) {
               return _InsertB(root->_left, key);
           }
           else if (root->_key < key) {
               return _InsertB(root->_right, key);
           }
           else {
               return false;
           }
       }

       bool _EraseB(Node* &root, const K& key) {
           if (root == nullptr) {
               return false;
           }
           if (root->_key > key) {
               return _EraseB(root->_left, key);
           }
           else if (root->_key < key) {
               return _EraseB(root->_right, key);
           }
           else {
               if (root->_left == nullptr) {
                   Node* node = root; // 注意，由于这里指针指向的不是引用，所以对其赋值操作时不是对原本搜索二叉树的操作
                   //注意: 这里不能使用引用，因为下面的释放空间会出问题
                   root = root->_right; //指针引用使用，可改变原结构
                   delete node;
                   node = nullptr;
                   return true;
               }
               else if (root->_right == nullptr) {
                   Node* node = root; //与上同理
                   root = root->_left; //指针引用使用，可改变原结构
                   delete node;
                   node = nullptr;
                   return true;
               }
               else {
                   //这里替换左子树最大值
                   Node* LeftMaxNode = root->_left;
                   while (LeftMaxNode->_right) {
                       LeftMaxNode = LeftMaxNode->_right;
                   }
                   swap(LeftMaxNode->_key, root->_key);
                   //注意:return _EraseB(LeftMaxNode, key);是错误的，因为当删除节点后，无法使此时的指向为空，导致遍历出错
                   return _EraseB(root->_left, key);
               }
           }
       }
   };
}