1.基础概念介绍
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3.它的左右子树也分别为二叉搜索树
如图所示就是一颗二叉树，其先从根开始找起（一般走中序遍历），因为节点左边的值总比节点小，右边的值总比节点打，所以遍历完一遍还没有找到的话，说明这个数字不存在。
2.二叉搜索树的基本功能实现
2.1单个节点类
tmeplate<class K>
strust BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
,_rihgt(nullptr)
,_ket(key)
{}
};
2.2BS树主体
tmepalte<class k>
class BSTree
{
typedef BSTreeNode<K> Node; //其实还是那老一套，这里的封装就相对简单多了
BSTree()
:_root(nullptr)
{}
private:
Node* _root
};
2.3插入
bool insert(const k& key)
{
if(_root == nullptr)
{
Node* cur = new Node(kety);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while(cur)
{
if(cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key);
if(parent->_key > key)
{
parent->_left = parent;
}
else
{
parent->_right = parent;
}
return true;
}
2.4删除
bool Erase(const k& key)
{
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(parent == nullptr)
{
_root->cur->_right;
}
else
{
if(parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
}
if(cur->_right == nullptr)
{
if(parent == nullptr)
{
_root->cur->_left;
}
else
{
if(parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
}
if(cur->_right != nullptr && cur->_left != nullptr)
{
Node* minParent = cur;
Node* min = cur->right;
while(min->left)
{
minParent = min;
min = min->left;
}
cur->_key = min->_key;
if (minParent->_left == min)
minParent->_left = min->_right;
else
minParent->_right = min->_right;
delete min;
}
return true;
}
}
return false;
}
这棵树的重点其实就是删除功能，可以看到上图我们一共会出现这三种情况（当然这里的图画的不完全，但是大致我们可以分为3类）：
我们先来讲解一二两类：
如一二两图所示当出现这种情况时候我们优先考虑：
1.此时要删除的节点是否为根节点（根节点要是变化了需要更改）
2.删除后我们将其左结点或者右结点和其父结点相互连接，此时应该去区分是父结点的右和我相互关联还是左。
而碰到图三的情况我将讲解下这里用到的代码细节和思路：
1.其实我们遇到图三这种情况，处理方法无非是找其左端的最大值，或者右端的最小值，而这里我们采用的是寻找右端最小数值的方法（可以画图比较一下这两方法我为什么选择后者）
2.其次这里不需要考虑删除的是否为根结点的问题（因为我实际操作是不可能去删根结点的）
3.在我使用第二种方法后，其依旧需要判断一下父结点是连哪个方向（具体参考下面这张图）
2.5查找
bool Find(const k& key)
{
Node*cur = _root;
while(cur)
{
if(cur->_key > key)
{
cur = cur->left;
}
else if(cur->_key<key)
{
cur = cur->right;
}
else
{
return true;
}
}
return false;
}
基本功能到这里已经实现完成了，当然这里会有一个递归的版本，但是正常情况下我们不会去使用递归的这种方法去实现，当递归深度足够大时栈容易溢出。
