二叉树的概念
二叉搜索树又称为二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
若它的左子树不为空，则左子树上所有结点的值都小于根结点的值。
若它的右子树不为空，则右子树上所有结点的值都大于根结点的值。
它的左右子树也分别是二叉搜索树。
以此设计的二叉树在其查找上就会大大优化了效率，所以二叉搜索树也称为“天才的树”；
就比如下面这个树：
对于根节点8，其左节点为4，比8小，右节点为12比8大，一次类推4，其左节点2比4小，右节点6比6大，同时因为8的左节点全是比8小的，比起大的全在右子树，所以也保证了6小于8。故而左节点，根节点，右节点的大小关系为：左节点<根节点<右节点，所以也可以推出来二叉搜索树进行中序遍历打印所得到的是：升序序列。
二叉搜索树的实现
结点类
要实现二叉搜索树，我们首先还是需要跟二叉树一样，需要实现一个结点类：
结点类当中包含三个成员变量：结点值、左指针、右指针。
结点类当中只需实现一个构造函数即可，用于构造指定结点值的结点。
template
struct BSTreeNode
{
BSTreeNode _left;//左指针
BSTreeNode _right;//右指针
K _key;//结点值
BSTreeNode(const K& key)//构造函数
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
各函数接口总览+小技巧
//二叉搜索树
template
class BSTree
{
typedef BSTreeNode Node;
public:
//构造函数
BSTree();
//拷贝构造函数
BSTree(const BSTree<K>& t);
//赋值运算符重载函数
BSTree<K>& operator=(BSTree<K> t);
//析构函数
~BSTree();
//插入函数
bool Insert(const K& key);
//删除函数
bool Erase(const K& key);
//查找函数
Node* Find(const K& key);
//中序遍历
void InOrder();
private:
Node* _root; //指向二叉搜索树的根结点
};
对于其中得中序遍历，可以看到上面得函数是没有带参数的，这是因为方便随时检查，简单的来说，在main的作用域内，如果中序遍历带上参数根节点，那么如果在代码中途进行检测的时候还需要保存根节点然后进行传参进行遍历，这显然是略有麻烦的，所以最好实现一个二叉搜索树的中序遍历接口，当我们对二叉搜索树进行一次操作后，可以调用中序遍历接口对二叉搜索树进行遍历，若二叉搜索树进行操作后的遍历结果仍为升序，则可以初步判断所实现的接口是正确。
//中序遍历子函数
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
这样在如果要进行中序遍历就会方便很多；
构造函数
构造函数也是最为简单的一个函数，最一开始一个树肯定是空的，所以直接构造一个空树就可以。
//构造函数
BSTree()
{
_root = nullptr;
}
拷贝构造函数
拷贝构造函数也并不难，拷贝一棵和所给二叉搜索树相同的树即可。
但要注意的一点就是要进行深拷贝，不是浅拷贝。
Node _Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newNode = new Node(root->_key); //拷贝根结点
newNode->_left = _Copy(root->_left); //拷贝左子树
newNode->_right = _Copy(root->_right); //拷贝右子树
return newNode;
}
//拷贝构造函数
BSTree(const BSTree<K>& t)
{
_root = _Copy(t._root); //拷贝t对象的二叉搜索树
}
赋值运算符重载函数
对于赋值运算符重载函数，下面提供两种实现方法：
先将当前二叉搜索树中的结点释放，然后完成所给二叉搜索树的拷贝即可。
void free_tree(Node* root)
{
if (root != nullptr)
{
if (root->_left != nullptr)
{
free_tree(root->_left);
root->_left = nullptr;
}
if (root->_right != nullptr)
{
free_tree(root->_right);
root->_right = nullptr;
}
free(root);
root = nullptr;
}
}
//传统写法
BSTree<K>& operator=(const BSTree<K>& t)
{
if (this != &t) //防止自己给自己赋值
{
free_tree(t._root);
_root = _Copy(t._root); //拷贝t对象的二叉搜索树
}
return *this; //支持连续赋值
}
赋值函数的现代写法是非常的经典而且效率还好的一种写法，效率高的原因是因为其中涉及到了左值与右值的知识，使得不需要我们自己去释放的一步，这一部分涉及到c++11。现代的写法中是先将利用拷贝函数进行值传递后进行拷贝，然后再将其要赋值的对象进行swap。
//现代写法
BSTree& operator=(BSTree t) //自动调用拷贝构造函数
{
swap(_root, t._root); //交换这两个对象的二叉搜索树
return *this; //支持连续赋值
}
析构函数
析构函数其实上面已经实现了其子函数，只需要正常调用子函数就可以、
void free_tree(Node* root)
{
if (root != NULL)
{
if (root->left != NULL)
{
free_tree(root->left);
root->left = NULL;
}
if (root->right != NULL)
{
free_tree(root->right);
root->right = NULL;
}
free(root);
root = NULL;
}
}
~BSTree()
{
free_tree(_root);//调用子函数
}
查找节点
为了方便再次给出二叉搜索树的性质：
若它的左子树不为空，则左子树上所有结点的值都小于根结点的值。
若它的右子树不为空，则右子树上所有结点的值都大于根结点的值。
它的左右子树也分别是二叉搜索树
给定目标节点值 key，可以根据二叉搜索树的性质来查找。如图所示，我们声明一个节点 cur ，从二叉树的根节点 _root 出发，循环比较节点值 cur._key和 key之间的大小关系。
若 cur.val < key，说明目标节点在 cur 的右子树中，因此执行 cur = cur.right 。
若 cur.val > key，说明目标节点在 cur 的左子树中，因此执行 cur = cur.left 。
若 cur.val = key，说明找到目标节点，跳出循环并返回true。
若cur==nullptr，说明目标节点不存在该二叉搜索树内，返回false。
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;
}
插入函数
给定一个待插入元素 key，为了保持二叉搜索树“左子树 < 根节点 < 右子树”的性质，插入操作流程如下：
查找插入位置：与查找操作相似，从根节点出发，根据当前节点值和 key 的大小关系循环向下搜索，直到越过叶节点（遍历至 None ）时跳出循环。(None是nullptr)
在该位置插入节点：初始化节点 key，将该节点置于 None 的位置。
在代码实现中，需要注意以下两点。
二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。
为了实现插入节点，我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 None 时，我们可以获取到其父节点，从而完成节点插入操作。
bool Insert(const K& key)
{
if (_root == nullptr)//第一次
{
_root = new Node(key);
return true;
}
Node parent = nullptr;
Node cur = _root;
while (cur)
{
parent = cur;
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
删除函数
二叉搜索树的删除函数是最难实现的，若是在二叉树当中没有找到待删除结点，则直接返回false表示删除失败即可，但若是找到了待删除结点，如果想要达到删除的效果并且不破坏二叉搜索树的规则，这就要分类，分为三种情况：
待删除节点的左子树为空（待删除节点的左右子树均为空包含在内）。
待删除节点的右子树为空。
待删除节点的左右子树均不为空。
若待删除结点的左子树为空，那么当我们在二叉搜索树当中找到该结点后，只需先让其父结点指向该结点的右孩子结点，然后再将该结点释放便完成了该结点的删除，进行删除操作后仍保持二叉搜索树的特性。
若待删除结点的右子树为空，那么当我们在二叉搜索树当中找到该结点后，只需先让其父结点指向该结点的左孩子结点，然后再将该结点释放便完成了该结点的删除，进行删除操作后仍保持二叉搜索树的特性。
若待删除结点的左右子树均不为空，那么当我们在二叉搜索树当中找到该结点后，可以使用与二叉树相似的替换法进行删除。可以将让待删除结点左子树当中值最大的结点，或是待删除结点右子树当中值最小的结点代替待删除结点被删除（下面都以后者为例），然后只进行交换其中的key即可，替换以后我们待删除节点位置所存的值就会变为右子树当中值最小的结点的值，这时候就会转化问题为删除右子树当中值最小的结点；然而这个节点因为是右子树当中值最小的结点，所以肯定是没有左子树的，下面的解决方式就转化为了情况一；
需要注意的是：虽然要与右子树当中值最小的结点进行交换，如果删除的位置为这种情况下：
如果要删除12，但12的右子树当中值最小的结点就是其右节点14，不是右子树当中值最小的结点，所以还有特殊情况需要注意以下。下面展示简易图形解释
bool Erase(const K& key)
{
//删除的地方分为三种情况讨论
//1.左孩子为空（无孩子结点）
//2.右孩子为空
//3.左右都不为空，替换为左的最大 右的最小
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->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
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;
}
else//情况三
{
//左右都不为空
// 替换法
// 右树的最小节点(最左节点)
Node* parent = cur;
Node* subLeft = cur->_right;
while (subLeft->_left)
{
parent = subLeft;
subLeft = subLeft->_left;
}
swap(cur->_key, subLeft->_key);
if (subLeft == parent->_right)//删除的右子树无左结点
{
parent->_right = subLeft->_right;
}
else
{
parent->_left = subLeft->_right;
}
delete subLeft;
}
return true;
}
}
return false;
}
递归实现删除，插入，查找
然而上面的删除，插入，查找代码实现全是利用的非递归，这时候就有人问了能否利用递归实现接口的代码呢？
答案是可以的，首先查找就不多说了，是这三者中最为简单的一个实现
递归实现查找
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
else
{
if (root->_key > key)
{
return _FindR(root->_left, key);
}
else if (root->_key < key)
{
return _FindR(root->_right, key);
}
else
{
return true;
}
}
}
递归实现插入
要想实现递归我们要想好两个问题
1：结束条件是什么？结束时要做什么？
2：如何慢慢逼近这个结束条件？
首先问题一：我们如果要插入的肯定是插入到一个nullptr节点，所以结束条件就是递归到nullptr节点，我们要做的就是new一个对象插入即可；
问题二：就不在解释了，直接利用二叉搜索树的性质逼近即可。
代码如下：
需要注意的就是：递归插入函数的子函数接收参数root时，必须采用引用接收，不可以用_root，否则会与成员歧义；
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else
{
return false;
}
}
递归实现删除
递归实现删除与递归实现插入其实思路差不多，只需要将递归的两个条件想明白，然后再结合非递归实现删除相结合就可以实现出来
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else if (root->_key < key)
{
return _EraseR(root->_right, key);
}
else//找到了要删除的数
{
if (root->_left == nullptr)
{
Node* del = root;
root = root->_right;
delete del;
return true;
}
else if (root->_right == nullptr)
{
Node* del = root;
root = root->_left;
delete del;
return true;
}
else
{
Node* subLeft = root->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
swap(root->_key, subLeft->_key);
return _EraseR(root->_right, key);//问题转化
//return _EraseR(subLeft, key);//这个不行是因为原本subLeft本身就不是引用
//操作过程完全没问题，但他不会修改结点指向
}
}
}
当写完递归实现删除后，就会有人又有疑问了，那非递归实现的时候又要判断删除节点是父节点的左孩子还是右孩子，递归的时候就不需要这样，那么能否进行优化非递归的写法呢？
答案是不行的，因为注意我们的传的参数的就是父的左（右）指针，在进入子递归的情况下，就已经是知道是父节点的左孩子还是右孩子的，所以递归是没有优化，而是已经知道不需要进行复杂的判断，那么又有人说了，那递归的时候没有修改父节点的左（右）指针的指向阿，删除后虽然该节点为空，但是父的左（右）指针的指向还是应该指向原来的空间阿，这时候就要注意了，我们接收的参数是引用，在进行类似的这一步的时候其实也可以修改父的左（右）指针的指向的。
二叉搜索树的应用
二叉搜索树在c++中一般来说是以特定的模型来实现的，不是按照像二叉树一样随便使用，在c++中一般是在K模型与K，V模型中体现。K模型
比如：在我们日常实现的存储double，int，char的二叉树都可以称为K模型的二叉树，以此建立的二叉树中每个节点除了指针外，存储的另一个值就是所说的key，此二叉搜索树称为K模型的二叉搜索树。
KV模型
比如说：一个篮子里面有好多水果，每种水果不止一个，这时候我们要实现代码，使其不仅仅存储水果的种类，还存放每种水果的个数，这时候就可以用到键值对，first存放水果的种类名字，second存放该种水果的个数。
以<水果, 个数>为键值对，构建一棵二叉搜索树。注意：二叉搜索树需要进行比较，键值对比较时只比较key。
查询某种水果有多少时，只需给出该水果的名字可以快速找到与其对应的个数。
二叉搜索树的性能分析
对于二叉搜索树这棵特殊的二叉树，我们每进行一次查找，若未查找到目标结点，则还需查找的树的层数就减少了一层，所以我们最坏情况下需要查找的次数就是二叉搜索树的深度，深度越深的二叉搜索树，比较的次数就越多。
对于有n个结点的二叉搜索树：
最优的情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN
最差的情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2
而时间复杂度描述的是最坏情况下算法的效率，因此普通二叉搜索树各个操作的时间复杂度都是
o(N)。不是logN。
所以实际上，二叉搜索树在极端情况下是没办法保证效率的，因此由二叉搜索树又衍生出来了AVL树、红黑树等，它们对二叉搜索树的高度进行了优化，使得二叉搜索树非常接近完全二叉树，因此对于这些树来说，它们的效率是可以达到logN的。
