二叉搜索树
目录
一.概述
二.二叉树的查找规则
三.二叉树的插入规则
四.二叉树的删除规则
五.二叉搜索树的模拟实现
插入操作非递归版
中序遍历
递归版插入实现
删除非递归版
待删除的节点只有右子树
待删除的节点只有左子树
待删除的节点左右子树都存在
删除递归版
拷贝构造
operator=赋值
析构函数
查找
完整模拟实现代码
一.概述
二叉搜索树也叫二叉排序树,搜索二叉树，与普通的二叉树相比二叉搜索树满足所有节点右孩子值都比根节点值大，左孩子值都比根节点值小。
下图中第一个二叉树5是10的右孩子但是值比10小，所以不满足二叉搜索树的规则
下图是一个完整的二叉搜索树，如果使用中序遍历的话会发现正好是有序的1,3，4,6,7,8,10,13,14，这也就是为什么二叉搜索树也叫做二叉排序树
二.二叉树的查找规则
从根出发，如果要查找的值比根值小就往左子树走，如果比根值大就往右子树去查找 。用递归的话很容易分解成子问题求解，如果值比根小就转换成去左子树处理查找，如果值比根大就去右子树处理查找。如果走到空就代表这个值不存在直接返回false
三.二叉树的插入规则
与查找类似从根出发，如果要插入的值比根值小就往左子树走，如果比根值大就往右子树去查找 ，走到空了就代表可以在这个位置插入。用递归的话也很容易分解成子问题求解，如果值比根小就转换成去左子树处理，如果值比根大就去右子树处理。如果走到空就代表已经找到了合适的插入位置
四.二叉树的删除规则
依旧是按照查找的规则先查找到要删除的数值
如果待删除的值只有一个孩子节点那么直接把孩子节点和自己的父节点链接起来（与链表的删除有点相似，删除当前节点要将前一个节点的next链接起后一个节点，然后才能将当前值释放删除掉）
但是孩子节点与父节点链接起来也要符合二叉搜索树的规则（左子树节点值都比根节点小，右子树节点值都比根节点大），链接规则的调整是借助当前要删除的节点来辅助进行的，如果当前要删除的节点是父节点的左孩子那么待删除节点的孩子全部链接到父节点的左子树上，相反孩子节点就全部链接到右子树上
举个例子，下图的要删除14，就是把自己的孩子节点链接到父节点的右子树上。为什么它一点能保证是右子树而不是左子树呢，这是二叉搜索树的规则决定的，右子树的值肯定比根节点值大（即使是自己孩子节点的左孩子节点，如果是比10小的话早在插入的时候就链接到了10的左子树上了，而不是成为右孩子节点的孩子节点）
删除14后的形状
如果要删除的节点的孩子节点有两个孩子的话就不适合上面那种直接链接到父节点上，因为如果只链接一个孩子节点，另一个孩子节点连带它的孩子节点都不好处理了。
所以有两个处理规则，一个是取当前待删除节点的左子树的最大值来代替当前节点作为根节点，一个是取右子树的最小节点来代替当前节点作为根节点。为什么呢，因为要符合二叉搜索树左边都比根节点值大，右边都比根节点值小只能这样了，实际上就是取一个中间的不大不小的值来当作代替节点。
比如下面的例子里删除节点3，要么让左子树最大的节点1上来做根节点，此时左子树为空，右子树都比1大，符合二叉搜索树的规则，实际上就是找左子树当中最右边的节点，因为越往右子树走越大；要么让右子树的最小值4上来做根节点，此时左子树只有一个节点1比4小，而右子树节点值为6,7，依旧符合二叉搜索树的规则，实际上就是找右子树当中最左边的节点，因为越往左边走值越小
选取左子树最大节点作为根节点情况
选取右子树最小节点替代根节点的情况
总结一下删除的方法，b和c是可以合到一起去的
五.二叉搜索树的模拟实现
前情提要：插入和删除有递归版和非递归版两个版本
首先是节点的定义，二叉树节点除了存值val外还有left和right两个指针，分别指向左孩子和右孩子
然后是具体的二叉搜索树的成员变量框架，成员变量就一个root根节点，其余的节点都是在插入时才构造出来的
插入操作非递归版
bool insert(const T& key){if (root == nullptr){root = new Node(key);return true;}Node* cur = root;Node* parent = nullptr;while (cur){if (key > cur->val){parent = cur;cur = cur->right;}else if (key < cur->val){parent = cur;cur = cur->left;}else{return false;}}cur = new Node(key);if (parent->val > cur->val){parent->left = cur;}else{parent->right = cur;}return true;}让我来挨个解释一下这段代码
if (root == nullptr)
{
root = new Node(key);
return true;
}这个就是插入第一个节点的情况，此时直接new节点出来给root就可以了
Node* cur = root;
Node* parent = nullptr;
while (cur)
{
if (key > cur->val)
{
parent = cur;
cur = cur->right;
}
else if (key < cur->val)
{
parent = cur;
cur = cur->left;
}
else
{
return false;
}
}这个循环就是按照二叉搜索树的规则左子树都比根小，右子树都比根大找合适的插入位置。如果值相等就直接return false，因为不需要插入了。
cur = new Node(key);
if (parent->val > cur->val)
{
parent->left = cur;
}
else
{
parent->right = cur;
}
return true;}
出来循环走到空说明找到了要插入的位置，但是要判断一下究竟是父节点的左孩子还是右孩子
中序遍历
void midorder()
{_order(root);
}
void _order(const Node* root)
{if (root == nullptr)return;_order(root->left);cout << root->val << " ";_order(root->right);
}中序遍历其实没有什么好说的，因为在二叉树那里就已经学过了。唯一值得注意的是在类里面递归基本上都会写成两个函数相互辅助，为什么呢？中序遍历肯定需要根节点，如果是写成void midorder(const Node* root)，那么就需要传参，这样是不能直接用到类里面的root成员，root成员变量只能在成员函数内部使用。所以写成两个函数来辅助递归
结合中序遍历测试一下二叉搜索树的插入
递归版插入实现
bool insert(const T& key){return _insert(root,key);}bool _insert(Node *&root,const T& key){if (root == nullptr){root = new Node(key);return true;}if (key > root->val){return _insert(root->right, key);}else if (key < root->val){return _insert(root->left, key);}else{return false;}}insert依旧还是利用两个函数来辅助递归，为什么这个不用重新new一个Node出来然后链接呢，因为在 开头bool _insert(Node *&root,const T& key)，这个root节点写成引用了。一般来说如果是有原先有节点的情况要插入新节点，基本都是通过return _insert(root->right, key);return _insert(root->left, key);这两个流程的下一步执行的，而开头函数接口写成了引用，就变成了root其实是上一层root的left指针或者right指针的别名了，那么root=new Node(val)岂不是相当于root->left=new Node（key）了，这样其实是省略了循环那种写法一步步找父节点的过程以及判断是父节点的左孩子和右孩子。
删除非递归版
bool erase(const T& key)
{if (root == nullptr)return false;Node* cur = root;Node* parent = nullptr;while (cur){if (key > cur->val){parent = cur;cur = cur->right;}else if (key < cur->val){parent = cur;cur = cur->left;}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;cur = nullptr;}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;}}delete cur;cur = nullptr;}else{Node* minnode = cur->right;//找右子树的最小节点Node* tampparent = cur;while (minnode->left){tampparent = minnode;minnode = minnode->left;}cur->val = minnode->val;if (tampparent->left == minnode)tampparent->left = minnode->right;elsetampparent->right = minnode->right;delete minnode;minnode = nullptr;}return true;}}return false;
}if (root == nullptr)
return false;
Node* cur = root;
Node* parent = nullptr;
while (cur)
{
if (key > cur->val)
{
parent = cur;
cur = cur->right;
}
else if (key < cur->val)
{
parent = cur;
cur = cur->left;
}这段代码与前面的插入类似，只不过root为空时insert是直接插入节点，而删除是直接返回false。而循环里面是按照二叉搜索树的规则查找要删除的值，如果比cur的值大就往右子树走，比cur值小就往左子树走
找到要删除的值后具体删除操作
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;
cur = nullptr;
}
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;
}
}
delete cur;
cur = nullptr;
}
else
{
Node* minnode = cur->right;//找右子树的最小节点
Node* tampparent = cur;
while (minnode->left)
{
tampparent = minnode;
minnode = minnode->left;
}
cur->val = minnode->val;
if (tampparent->left == minnode)
tampparent->left = minnode->right;
else
tampparent->right = minnode->right;
delete minnode;
minnode = nullptr;
}
return true;
}
}
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;
}
}
delete cur;
cur = nullptr;
}删除就两种情况一种是待删除的节点只有一个孩子节点（没有孩子节点可以这个直接合并了），只有一个孩子节点是采用托孤政策，也就是把自己的孩子节点交给父节点来处理。
这段截取的代码是待删除的节点只有右节点的情况
if (parent == nullptr)
root = cur->right;这两段代码放到后面再继续讲解if (parent->left == cur)
{
parent->left = cur->right;
}
else
{
parent->right = cur->right;
}
}
delete cur;
cur = nullptr;这段代码是具体的托孤政策，因为已经确定了待删除的节点只有右孩子，所以只需要让父节点链接起右节点就可以了。 if (parent->left == cur)做判断是因为cur这个待删除的节点有可能是parent的右节点也有可能是左节点，如果是左节点就说明cur这个待删除的所有孩子节点都比父节点小，所以直接链接为父节点的右子树
再回过头来谈谈为什么要单独写 if (parent == nullptr) root = cur->right;
如果要删除的节点就是根节点而且整颗树只有右子树或者左子树的情况下怎么处理（如下图），下图当中删除8，按照托孤是把待删除的节点给父节点，可是根节点没有父节点。所以此时这种情况需要更新root节点就可以了，也就是 root = 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;
}
}
delete cur;
cur = nullptr;
}这段代码与上面类似，只不过上面是只有右子树，这个是只有左子树
待删除的节点左右子树都存在
else
{
Node* minnode = cur->right;//找右子树的最小节点
Node* tampparent = cur;
while (minnode->left)
{
tampparent = minnode;
minnode = minnode->left;
}
cur->val = minnode->val;
if (tampparent->left == minnode)
tampparent->left = minnode->right;
else
tampparent->right = minnode->right;
delete minnode;
minnode = nullptr;
}两个左右子树都存在的情况分两种情况找待删除的节点左子树的最大值或者找右子树的最小值，这段代码是找右子树的最小值。 while (minnode->left)为什么这个left等于空就找到了呢，因为二叉搜索树规则限制了一颗树最左边的节点就是最小的节点（因为越往左边走越小），最右边节点是最大的。所以当minnode找不到别的左节点的时候就说明此时它就是最小的节点了，然后通过交换值就替代根节点了cur->val = minnode->val; 剩余的代码是为了删除原来的最小节点minnode，因为它已经上去当根节点了，所以它也要删除，因为它是最左节点所以肯定只有右节点，所以在删除它时也要使用托孤方案处理好它的右孩子
删除递归版
bool erase(const T& key){return _erase(root, key);}bool _erase(Node*& root, const T& key){if (root == nullptr)return false;if (key > root->val){return _erase(root->right, key);}else if (key < root->val){return _erase(root->left, key);}else{Node* cur = root;if (root->left == nullptr){root = root->right;}else if (root->right == nullptr){root = root->left;}else{Node* minnode = root->right;while (minnode->left){minnode = minnode->left;}swap(minnode->val, cur->val);return _erase(root->right,key);}delete cur;cur = nullptr;return true;}}
if (root == nullptr)
return false;
if (key > root->val)
{
return _erase(root->right, key);
}
else if (key < root->val)
{
return _erase(root->left, key);
}这些和前面的处理类似就不多加赘述了
Node* cur = root;
if (root->left == nullptr)
{
root = root->right;
}
else if (root->right == nullptr)
{
root = root->left;
}这段代码是代删除节点只有一个孩子的情况，采用托孤措施，把自己的孩子节点托给父节点。root其实上一层root节点left和right节点的别名，所以root=root->right,其实就是把孩子节点和父节点链接起来
else
{
Node* minnode = root->right;
while (minnode->left)
{
minnode = minnode->left;
}
swap(minnode->val, cur->val);
return _erase(root->right,key);
}这段代码是处理代删除节点有两个孩子的情况，依旧是先找出右子树的最小节点。为什么采用 _erase(root->right,key);而不是 _erase(minnode,key);，因为如果是直接递归minnode少了父节点指针引用链接，这时候引用的是minnode本身，如果它还有孩子节点的话就会与父节点断开联系
拷贝构造
拷贝构造按照先序的顺序一个一个节点进行递归拷贝，唯一值得注意的拷贝构造也算靠构造函数，只要写明了构造函数就不会生成默认构造函数。所以加这一句 BStree() = default;是强行生成构造函数
BStree() = default;BStree(const BStree<T>& tamp){root=copy(tamp.root);}Node* copy(Node* tamroot){if (tamroot == nullptr)return nullptr;Node* copynode = new Node(tamroot->val);copynode->left = copy(tamroot->left);copynode->right = copy(tamroot->right);return copynode;}operator=赋值
依旧是利用拷贝构造先构造出一个临时的的二叉搜索树出来，然后直接交换根节点
BStree operator=(BStree<T> tamp)
{std::swap(tamp.root, root);return *this;
}析构函数
~BStree()
{_destory(root);
}
void _destory(Node*& root)
{if (root == nullptr)return;_destory(root->left);_destory(root->right);delete root;root = nullptr;
}查找
这个与insert有点类似
bool find(const T& key){return _find(root, key);}bool _find(Node* root, const T& key) {if (root == nullptr){return false; // 未找到 }if (key > root->val){return _find(root->right, key); // 查找右子树 }else if (key < root->val){return _find(root->left, key); // 查找左子树 }else{return true; // 找到 }}完整模拟实现代码
#pragma once
#include<iostream>
using namespace std;template<class K>
struct BStreeNode
{BStreeNode<K>* left;BStreeNode<K>* right;K val;BStreeNode(const K& value) :left(nullptr), right(nullptr), val(value) {};
};template<class T>
struct BStree
{
public:typedef BStreeNode<T> Node;/*bool insert(const T& key){if (root == nullptr){root = new Node(key);return true;}Node* cur = root;Node* parent = nullptr;while (cur){if (key > cur->val){parent = cur;cur = cur->right;}else if (key < cur->val){parent = cur;cur = cur->left;}else{return false;}}cur = new Node(key);if (parent->val > cur->val){parent->left = cur;}else{parent->right = cur;}return true;}*/bool insert(const T& key){return _insert(root,key);}bool _insert(Node *&root,const T& key){if (root == nullptr){root = new Node(key);return true;}if (key > root->val){return _insert(root->right, key);}else if (key < root->val){return _insert(root->left, key);}else{return false;}}//bool erase(const T& key)//{// if (root == nullptr)// return false;// Node* cur = root;// Node* parent = nullptr;// while (cur)// {// if (key > cur->val)// {// parent = cur;// cur = cur->right;// }// else if (key < cur->val)// {// parent = cur;// cur = cur->left;// }// 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;// cur = nullptr;// }// 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;// }// }// delete cur;// cur = nullptr;// }// else// {// Node* minnode = cur->right;//找右子树的最小节点// Node* tampparent = cur;// while (minnode->left)// {// tampparent = minnode;// minnode = minnode->left;// }// cur->val = minnode->val;// if (tampparent->left == minnode)// tampparent->left = minnode->right;// else// tampparent->right = minnode->right;// delete minnode;// minnode = nullptr;// }// return true;// }// // }// return false;//}void midorder(){_order(root);}void _order(const Node* root){if (root == nullptr)return;_order(root->left);cout << root->val << " ";_order(root->right);}bool erase(const T& key){return _erase(root, key);}bool _erase(Node*& root, const T& key){if (root == nullptr)return false;if (key > root->val){return _erase(root->right, key);}else if (key < root->val){return _erase(root->left, key);}else{Node* cur = root;if (root->left == nullptr){root = root->right;}else if (root->right == nullptr){root = root->left;}else{Node* minnode = root->right;while (minnode->left){minnode = minnode->left;}swap(minnode->val, cur->val);return _erase(root->right,key);}delete cur;cur = nullptr;return true;}}BStree() = default;BStree(const BStree<T>& tamp){root=copy(tamp.root);}Node* copy(Node* tamroot){if (tamroot == nullptr)return nullptr;Node* copynode = new Node(tamroot->val);copynode->left = copy(tamroot->left);copynode->right = copy(tamroot->right);return copynode;}BStree operator=(BStree<T> tamp){std::swap(tamp.root, root);return *this;}bool find(const T& key){return _find(root, key);}bool _find(Node* root, const T& key) {if (root == nullptr){return false; // 未找到 }if (key > root->val){return _find(root->right, key); // 查找右子树 }else if (key < root->val){return _find(root->left, key); // 查找左子树 }else{return true; // 找到 }}~BStree(){_destory(root);}void _destory(Node*& root){if (root == nullptr)return;_destory(root->left);_destory(root->right);delete root;root = nullptr;}
private:Node* root=nullptr;
};六.时间复杂度分析
插入和删除都依赖于查找规则，所以查找效率代表了二叉搜索树各个操作的性能，很多人认为二叉搜索树时间复杂度是logn，因为树的高度是logn，但是其实不是logn，因为没法控制树的高度，如果是一颗有序的树，比如下图，要找值为13的节点，那就意味着要从开始一直遍历到结尾，n个节点都要遍历到。而时间复杂度是考虑最坏情况的，所以时间复杂是O（n），只有接近完全二叉树的时候时间复杂度才是logn
