目录
概念
关于二叉树的基本结构已经进行过详细剖析，本篇博客将对一种特殊的二叉树进行分析。
二叉搜索树在二叉树的基础上，有三个要求。
1）若一个节点的左树不为空，则其左树的所有节点要小于该节点；
2）若一个节点的右树不为空，则其右树的所有节点要大于该节点；
3）一个节点的左右树也是搜索二叉树。
以上就是一个二叉搜索树。
二叉搜索树在对数据进行查找的时候效率很高，对于一个完全二叉树或趋于完全二叉树的结构，其查找的效率可以达到O(logN)，但是如果一个二叉树在使用的时候退化成一个单叉树的时候，其结构就类似于一个链表，查找效率就变成了O(N)。
平衡二叉搜索树会解决搜索二叉树退化的问题。在AVL树中会详细讲解。
关于搜索二叉树的底层在下面的代码实现中会进行详细分析。
代码实现
二叉搜索树有两个模型：1）key模型；2）key_value模型；
key模型主要是对单个数据进行排序的；key_value模型是在对key排完序后，可以通过key查找到另一个value模型。
比如：key模型会用在快速判断一个事物存不存在，比如小区门禁，通过信息进行排序，快速寻找访客是不是户主；key_value 会用在像电子字典上，将单词排序后，在查找key中的英文时，也能读取value中存储的含义。
下面代码会进行key_value模型的实现。
成员
在C++中有一个类是专门用来存储key和value值的，叫做pair；该模型也是专门为map设计的，此处写代码时就直接使用了。
pair - C++ Reference
https://legacy.cplusplus.com/reference/utility/pair/?kw=pair
关于pair的构造，有两种：1）可以通过一个函数make_pair创建对象来实现构造。
2）在C++11后支持多参数的构造，但是需要{}进行构造。
pair<int, int> p;
pair<string, int> p2(make_pair("make", 1)); //通过函数make_pair进行构造
pair<int, int> p1({ 1,2 }); //多参数构造基本结构
与二叉树的主要区别在与：搜索二叉树的成员时pair对象。
template<class K ,class V>
struct BSTreeNode //二叉树的每一个节点
{
//构造函数
BSTreeNode(const pair<K,V>& vk)
:_vk(vk)
, left(nullptr)
, right(nullptr)
{}
pair<K, V> _vk; //储存key和value的容器
BSTreeNode* left; //左节点
BSTreeNode* right; //右节点
};
template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> BSTreeNode;
private:
BSTreeNode* _root=nullptr;
};查找
二叉搜索树满足：左树小，右树大的特点，所以只需要将查找的值和当前节点的值进行对比，就能确定是往左树走，还是往右树走。
当前节点小了，往右树找；当前节点大了，往左树找；只当找到或到空节点。
//查找
bool Find(const pair<K, V> vk)
{
BSTreeNode* cur = _root;
while (cur)
{
if (cur->_vk.first > vk.first)
{
cur = cur->left; //当前节点大，往左找
}
else if (cur->_vk.first < vk.first)
{
cur = cur->right; //当前节点小,往右找
}
else
{
return true; //相等，返回
}
}
return false; //没找到，返回
}插入
关于二叉搜索树的插入，需要考虑要插入到哪一个位置？？？ ：二叉搜索树是有要求的，在插入数据后还需要满足是二叉搜索树的结构。
二叉搜索树是没有重复数据的，所以不需要考虑找不到位置的情况。那插入的位置必定是空节点。
像查找一样，通过比较来确定节点的位置。当找到位置后，插入即可。
//插入
bool Insert(const pair<K, V>& vk)
{
BSTreeNode* newnode = new BSTreeNode(vk);
if (_root == nullptr)
{
_root = newnode;
return true;
}
else
{
BSTreeNode* cur = _root;
BSTreeNode* parent = nullptr; //保存新节点的父节点，保证后续节点的链接
while (cur)
{
if (cur->_vk.first > vk.first)
{
parent = cur;
cur = cur->left;
}
else if (cur->_vk.first < vk.first)
{
parent = cur;
cur = cur->right;
}
else
{
return false; //相等，说明树中已经有该节点了，不需要再插入
}
}
//循环出来了，说明找到位置了
//将新节点插入到指定位置，注意还需要判断其是父节点左子树还是右子树
if (parent->_vk.first > vk.first)
{
parent->left = newnode;
}
else
{
parent->right = newnode;
}
return true;
}
}删除
删除的情况，有三种；
1）删除节点没有左节点：将右节点和父节点链接即可；
2）删除节点没有右节点：将左节点和父节点链接即可；
3）有左右节点：找一个位置能满足当前位置节点得到要求，即比左树都大，比右树都小。这个节点可以是左树的最大值(即左树的最右边)，或右树的最小值(即右树的最左边)。
//删除
bool Erase(const pair<K, V> vk)
{
BSTreeNode* cur = _root;
BSTreeNode* parent = nullptr;
while (cur)
{
if (cur->_vk.first > vk.first)
{
parent = cur;
cur = cur->left;
}
else if (cur->_vk.first < vk.first)
{
parent = cur;
cur = cur->right;
}
else
{
break; //找到了
}
}
if (cur == nullptr) //不存在要删除的节点
return false;
if (cur->left == nullptr) //左树为空
{
if (parent == nullptr) //判断删除节点是否为根节点
_root = cur->right;
else
{
if (parent->left == cur) //是父节点的坐支还是右支
parent->left = cur->right;
else
parent->right = cur->right;
}
}
else if (cur->right == nullptr)
{
if (parent == nullptr)
_root = cur->left;
else
{
if (parent->left == cur)
parent->left = cur->left;
else
parent->right = cur->left;
}
}
else
{
//找左树的最大节点
BSTreeNode* leftMax = cur->left;
BSTreeNode* Maxparent = cur;
while (leftMax->right)
{
Maxparent = leftMax;
leftMax = leftMax->right;
}
if (Maxparent->left== leftMax) //检leftMax是在parent的左还是右
{ //如果循环没进去就在左
Maxparent->left = leftMax->left;
}
else
{
Maxparent->right = leftMax->left;
}
//将左树的最大节点的vk和要删除节点的vk进行交换即可
swap(leftMax->_vk, cur->_vk);
//此时leftMax存储的是需要删除的数据
cur = leftMax;
}
delete cur;
return true;
}以上对于左右树都有节点的删除方法是：找左树的最大节点。
下面是找右树的最小节点方法。
else
{
//找右树的最小节点
BSTreeNode* rightMin = cur->right;
BSTreeNode* Maxparent = cur;
while (rightMin->left)
{
Maxparent = rightMin;
rightMin = rightMin->left;
}
if (Maxparent->left == rightMin) //检leftMax是在parent的左还是右
{ //如果循环没进去就在左
Maxparent->left = rightMin->right;
}
else
{
Maxparent->right = rightMin->right;
}
//将左树的最大节点的vk和要删除节点的vk进行交换即可
swap(rightMin->_vk, cur->_vk);
//此时leftMax存储的是需要删除的数据
cur = rightMin;
} 中序遍历
二叉搜索树通过中序遍历得到的是一个升序数组。
进行中序遍历的时候采用递归的方式进行，所以参数需要传_root才行，但是对于类外是不能访问_root的，所以此处通过函数调用函数来实现。
public:
//中序遍历
void InOrder()
{
_InOrder(_root);
}
private:
void _InOrder(BSTreeNode* _root)
{
if (_root == nullptr)
return;
if(_root->left)
_InOrder(_root->left);
cout << _root->_vk.first << " " << _root->_vk.second << endl;
if(_root->right)
_InOrder(_root->right);
}拷贝构造
拷贝构造可以直接通过前序遍历即可。
public:
//拷贝构造
BSTree(BSTree<K, V>& tree)
{
_root=_BSTree(tree._root);
}
private:
BSTreeNode* _BSTree(const BSTreeNode* root)
{
if (root == nullptr)
return nullptr;
BSTreeNode* _root = new BSTreeNode(root->_vk);
_root->left = _BSTree(root->left);
_root->right = _BSTree(root->right);
return _root;
}赋值运算符重载
赋值可以直接运用形参是实参的拷贝来实现。
//赋值运算符重载
BSTree& operator=(BSTree tmp)
{
swap(tmp._root, _root); //形参是实参的拷贝，所以直接将形参和要赋值的树交换即可
return *this;
}析构函数
析构函数需要用后序遍历来实现。
public:
~BSTree()
{
_Destory(_root);
}
private:
void _Destory(BSTreeNode* root)
{
if (root == nullptr)
return;
_Destory(root->left);
_Destory(root->right);
free(root);
}以上代码中某些方法的实现其实可以使用递归来实现，但是为了易于理解采用了非递归的思想方法。下面对部分代码用递归的方法实现。
递归实现
递归实现查找
递归查找与非递归一样，只需要对节点的key值进行分类即可。
public:
bool _Find(const pair<K, V>& vk)
{
return _FindR(_root, vk);
}
private:
bool _FindR(const BSTreeNode* root, const pair<K, V>& vk)
{
if (root == nullptr)
return false;
if (root->_vk.first == vk.first)
return true;
if (root->_vk.first > vk.first)
{
return _FindR(root->left, vk);
}
else
{
return _FindR(root->right, vk);
}
}递归实现插入
在递归实现插入的时候，形参直接使用引用就可以不用再去考虑父节点了。
public:
//递归实现插入
bool _Insert(const pair<K, V> vk)
{
return _InsertR(_root, vk);
}
private:
bool _InsertR(BSTreeNode*& _root, const pair<K, V> vk)
{
if (_root == nullptr)
{
_root = new BSTreeNode(vk);
return true;
}
if (_root->_vk.first > vk.first)
{
return _InsertR(_root->left, vk);
}
else if(_root->_vk.first < vk.first)
{
return _InsertR(_root->right, vk);
}
else //相等，不用插入
{
return false;
}
}递归实现删除
递归实现删除并不是完全递归，只是在找位置的时候，使用递归。在删除的时候还是需要分类讨论。
public:
//递归删除
bool _Erase(const pair<K, V> vk)
{
return _EraseR(_root,vk);
}
private:
//递归删除
bool _EraseR(BSTreeNode*&root,const pair<K, V> vk)
{
if (root == nullptr)
return false;
if (root->_vk.first > vk.first)
{
return _EraseR(root->left, vk);
}
else if (root->_vk.first < vk.first)
{
return _EraseR(root->right, vk);
}
else
{
BSTreeNode* del = root;
if (root->left == nullptr)
{
root = root->right;
}
else if (root->right == nullptr)
{
root = root->left;
}
else
{
//找到了删除
//找左树的最大节点替换
BSTreeNode* leftMax = root->left;
while (leftMax->right)
{
leftMax = leftMax->right;
}
swap(root->_vk, leftMax->_vk);
return _EraseR(root->left, vk); //不能直接删除del,这样会导致del节点与父节点
//的联系没有处理
}
delete del;
del = nullptr;
return true;
}
}