一、二叉搜索树定义
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
1.非空左子树上所有节点的值都小于根节点的值。
2.非空右子树上所有节点的值都大于根节点的值。
3.左右子树也都为二叉搜索树。
如下图所示：
二、二叉搜索树的操作
二叉搜索树结构：
template<class k>
struct BSTreeNode {
typedef BSTreeNode<k> Node;
Node* _left;//左子树指针
Node* _right;//右子树指针
k _key;//节点数据
};2.1 二叉搜索树的查找
1.从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
2.最多查找高度次，走到到空，还没找到，这个值不存在。
非递归查找：
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 _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.2 二叉搜索树的插入
插入的具体过程如下：
1. 树为空，则直接新增节点，赋值给root指针。
2. 树不空，按二叉搜索树性质查找插入位置，插入新节点。
插入key值为9的节点，如下图所示：
非递归插入：
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;//key值已存在
}
}
cur = new Node(key);//以key值开辟节点
if (parent->_key < key) {//新节点>父亲节点，在父亲的右边
parent->_right = cur;
}
if (parent->_key > key) {//新节点<父亲节点，在父亲的左边
parent->_left = cur;
}
return true;
}递归插入：
bool _InsertR(Node*& root, const k& key)
{//递归查找传参指针的引用，修改原指针，让原指针直接指向当前节点
if (root == nullptr)//root节点为空，开辟新结点
{
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;
}
}2.3 二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情 况：
1. 要删除的结点无孩子结点 2. 要删除的结点只有左孩子结点 3. 要删除的结点只有右孩子结点 4.要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程 如下：
1.删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除。
2.删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除。
3.查找删除结点的右子树的最左节点或者左子树的最右节点（距离删除节点最近，替换后不影响其他节点位置），用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除。下面用右子树的最左节点进行替换。
非递归删除：
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->_right)
{//判断删除节点是parent的left还是right
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_right)
{//判断删除节点是parent的left还是right
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
else
{
//左右子树均有节点，将删除节点替换为其右子树的最左节点（左子树的最右节点）
Node* rightMinParent = cur;//考虑右子树的根节点为最左节点，不进循环
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMin == rightMinParent->_left)
{
rightMinParent->_left = rightMin->_right;
//rightMin（右子树最左）为替换节点，替换后删除，rightMinParent的左或右指向rightMin的right
}
else
{
rightMinParent->_right = rightMin->_right;
}
delete rightMin;
return true;
}
}
}
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->_right == nullptr)
{//删除节点右为空，将左节点赋值给要删除的节点
root = root->_left;
}
else if (root->_left == nullptr)
{//删除节点左为空，将右节点赋值给要删除的节点
root = root->_right;
}
else
{
Node* rightMin = root->_right;
while (rightMin->_left)
{
rightMin = rightMin->_left;
}
swap(root->_key, rightMin->_key);//交换删除节点和右子树节点的key值
return _EraseR(root->_right, key);//交换后，删除节点为右子树最左节点，走left为空时情况
}
delete del;
return true;
}
}三、二叉搜索树的模拟实现
//二叉搜索树的模拟实现
namespace rab {
template<class k>
struct BSTreeNode {
typedef BSTreeNode<k> Node;
Node* _left;
Node* _right;
k _key;
BSTreeNode(const k& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
template<class k>
class BSTree {
typedef BSTreeNode<k> Node;
public:
//强制生成构造函数
BSTree() = default;
//拷贝构造函数
BSTree(const BSTree<k>& t)
{
_root = Copy(t._root);//传入拷贝对象的根节点
}
//析构函数
~BSTree() {
Destroy(_root);
}
//插入
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;//key值已存在
}
}
cur = new Node(key);
if (parent->_key < key) {
parent->_right = cur;
}
if (parent->_key > key) {
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->_right)
{//判断删除节点是parent的left还是right
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_right)
{//判断删除节点是parent的left还是right
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
else
{
//左右子树均有节点，将删除节点替换为其右子树的最左节点（左子树的最右节点）
Node* rightMinParent = cur;//考虑右子树的根节点为最左节点，不进循环
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMin == rightMinParent->_left)
{
rightMinParent->_left = rightMin->_right;//rightMin（右子树最左）为替换节点，替换后删除，rightMinParent的左或右指向rightMin的right
}
else
{
rightMinParent->_right = rightMin->_right;
}
delete rightMin;
return true;
}
}
}
return false;
}
/二叉搜索树的递归实现
//递归查找
bool FindR(const k& key)
{
return _FindR(key);
}
//递归插入
bool InsertR(const k& key)
{
return _InsertR(_root, key);
}
//递归删除节点
bool EraseR(const k& key)
{
return _EraseR(_root, key);
}
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
//递归中序遍历
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
//递归销毁搜索二叉树
void Destroy(Node* root) {
if (root == nullptr) {
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete 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;
}
//递归查找
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;
}
}
//递归插入
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->_right == nullptr)
{
root = root->_left;
}
else if (root->_left == nullptr)
{
root = root->_right;
}
else
{
Node* rightMin = root->_right;
while (rightMin->_left)
{
rightMin = rightMin->_left;
}
swap(root->_key, rightMin->_key);
return _EraseR(root->_right, key);//交换后，删除节点为右子树最左节点，走left为空时情况
}
delete del;
return true;
}
}
private:
Node* _root = nullptr;
};
}