前言：

此前我们在C语言实现数据结构的时候学习过二叉树，但是那个时候我们没有深入学习二叉搜索树。本章重提二叉树并详解二叉搜索树有下面两个原因：

1、为我们下一章学习set和map做准备；
2、详解我们进阶一点的二叉树的面试OJ题，加强我们深入的理解。

（一）二叉搜索树的概念

（二）二叉搜索树的模拟实现

（1）结点的声明

（2）几个默认成员函数

（3）非递归版本的增删查改操作

（4）递归版本的增删查改操作

（一）二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵 空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

图示：

也就是说一棵二叉搜索树的任一个根节点，它的左子树所有节点的值都是小于根节点的值的，它的右子树所有结点的值都是大于根节点的值的。

二叉搜索树查找的时间复杂度：

根据二叉搜索树的性质
我们大多数人认为其搜索的一个值的速度是为树的高度次
树的高度次的话，很多人就会认为是log2N次
但是事实并不是，正确得查找时间复杂度是〇（N）

只有当是满二叉树或者是完全二叉树时间复杂度才是〇（logN）！！

当出现单边树的情况时，就是〇（N）的情况。

如：

由于没有二叉搜索树的官方库，我们增删查改的实现需要我们自己来完成，见下面的模拟实现。

（二）二叉搜索树的模拟实现

（1）结点的声明

template<class K>class BSTreeNode{public:BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}};

（2）几个默认成员函数

template<class K>class BSTree{typedef BSTreeNode<K> Node;public:BSTree() = default;//强制生成默认构造BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);//_root = nullptr;}
protected: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;}void Destroy(Node*& root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}private:Node* _root = nullptr;
}

构造函数：

这里我们可以采用传统的方法
直接初始化成员变量
也可以用C++11的语法default
强制编译器自己生成构造函数

拷贝构造函数：

这里我们用了递归的方式进行拷贝
采用根 - 左 - 右的前序遍历的递归方式对整个二叉树拷贝
最后将跟结点返回

赋值重载：

我们采用“现代写法”
我们把原根节点拷贝给一个形参k
然后交换this指针指向的跟结点和k
最后返回this指针的解引用

析构函数：

析构函数我们这里也是采用递归的方式进行一个一个结点析构
同样的我们再嵌套一个子函数
也是采用类似前序遍历的方法将整个二叉树释放掉

采用递归方式的缺点就是如果数的结点个数足够多的时候，就会有爆栈的风险！！

（3）非递归版本的增删查改操作

1、查找find

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

根据二叉搜索树的性质，查找规则如下：

从根节点找起
如果比该结点指向的key小，往左子树查找
如果比该结点指向的key大，往右子树查找
在子树重复上述操作，最终找到寻找的值
否则，返回false

所以再没有平衡二叉搜索树的情况下，查找的时间复杂度为〇（N）

2、插入insert

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->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}if (parent->_key > key){parent->_left = cur;}return true;}

根据二叉搜索树的性质，插入规则如下：

插入的前提是找到要插入的位置
参考find，我们先找到要插入的位置
切记在查找位置时，要注意记录结点的父亲，以便插入

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 (parent->_left == cur){parent->_left = cur->_right;}else if (parent->_right == cur){parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else if (parent->_right == cur){parent->_right = cur->_left;}}delete cur;}else{// 找右树最小节点替代，也可以是左树最大节点替代Node* pminRight = cur;Node* minRight = cur->_right;while (minRight->_left){pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (pminRight->_left == minRight){pminRight->_left = minRight->_right;}else{pminRight->_right = minRight->_right;}delete minRight;}return true;}}return false;}

在讲解之前我们先分析一下不同位置结点删除的情况：

（1）当没有孩子或者只有一个孩子时

可以直接删除，孩子托管给父亲 — (托孤)

如我们要删除7和14：

此时我们就是将该结点直接删除，然后把该删除结点的孩子托给他的父亲。

以删除14这个结点为例：

该结点比10这个结点（父结点）大，在其右子树
那么该右子树的所有的值都比10这个结点大
所以要链接在10这个结点的右边

以删除7这个结点为例：

该结点比6这个结点（父结点）大，在其右子树
因为7这个结点没有孩子
直接删除，将父节点（6结点）的右指向空

（2）当有两个孩子时

这个时候就没法托孤了，我们要想一个新的方法。

这里我们直接给出核心步骤：

要找到【左子树的最大值节点，或者右子树的最小值节点】
找到之后，将要删除的结点和找到的结点的值进行交换（这里我们暂时用的是值交换）
再将被交换过之后的值的结点删除
一般被交换的结点都是末尾的叶子结点（按照上述的没有孩子的结点删除方式删除）

仔细思考为什么要这样做？

首先，找到左子树最大结点或者右子树最小结点替代原来的相对的根结点位置，那么他的左右满足搜索二叉树的性质；
其次，我们找到之后交换他和待删除的结点的值，左子树最大结点或者右子树最小结点肯定是叶子结点，交换后易删除，不会对结构有大的影响。

以删除3这个结点为例：

先找到以3为根节点的右子树的最小的结点，然后交换结点的key
然后参考上面的方法我们删除交换后3的结点然后“托孤”。

（4）递归版本的增删查改操作

在分块讲解前，我们要明白，递归要传根节点，但是用户平常使用这些借口并不会传根节点，而是直接调用，所以我们嵌套一层，这样就可以满足双方的需求了。如下：

1、查找FindR

我们把握好递归结束的条件然后左右递归即可。

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

2、插入InsertR

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;}}

该如何链接上树呢？

可以在递归的参数中多一个父亲结点，每次递归都更新一下Parent，然后再带到下一层递归
显然这样在学过C++之后就麻烦了。
用了一个指针的引用就解决了问题

因为root的值此时是空，但是root同时是这个结点里的_left这个指针的别名
相当于当前结点的父节点的左指针的别名
意味着此时再去给root赋值就是去给该结点父亲结点的_left赋值
那么此时就链接起来了

3、删除EraseR

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->_left == nullptr)root = root->_right;else if (root->_right == nullptr)root = root->_left;else{Node* maxleft = root->_left;while (maxleft->_right){maxleft = maxleft->_right;}swap(root->_key, maxleft->_key);return _EraseR(root->_left, key);}delete del;return true;}}