数据结构：二叉搜索树（排序树）
1.二叉搜索树的定义
二叉搜索树要么是空树，要么是满足以下特性的树
（1）左子树不为空，那么左子树左右节点的值都小于根节点的值
（2）右子树不为空，那么右子树左右节点的值都大于根节点的值
（3）其所有子树也满足二叉搜索树性质
（4）二叉搜索树有两种形态，一种是支持插入冗余值，一种是不支持的（一般默认不支持冗余）
简单来说就是左边节点值 < 根节点值 < 右边节点值
二叉搜索树又叫二叉排序树，这是因为如果对他进行中序遍历，将会得到一组升序排序的数据
2.二叉搜索树的性能
二叉搜索树的搜索次数是等于树的高度的
最优情况：对于类似完全二叉树的树结构，时间复杂度可以达到O(logn)
最差情况：对于几乎所有数据都单侧分布的情况，时间复杂度会到O(n)
为了使他保持最优的性能，我们后续会引入平衡的概念，使他保持左右子树高度差小于等于1
3.部分实现非冗余二叉搜索树
节点基本结构搭建：
对于bstree的搭建：只需要加一个private的根节点指针即可
3.1插入
（1）若树为空，则直接新建节点，然后把新节点的地址给bs树的根节点，返回true，表示插入成功
（2）若树不为空，则判断key和当前节点的值的大小
若key小于当前节点的值：往左边搜索
若大于当前节点的值：往右边搜索
若等于当前节点值：直接返回false
如果我只用一个cur指针，是不能完成节点的链接的，因为链接节点的是cur的直接根节点，也就是prvcur节点，所以这里我们才创建一个prvnode指针，就是用于把新节点和bs树进行连接的。
（3）找到之后判断key于待链接节点的值的大小决定插入在左侧还是右侧
接下来进入测试阶段，不过在测试之前我们需要写一个中序遍历的方法，以便更直观的检查逻辑是否正确
我们利用递归的方式实现，结束条件是节点为空。
由于二叉搜索树左子树 < 根节点 < 右子树的性质，我们使用中序遍历可以实现升序输出
不过这里有个问题，我们需要传递bstree的private变量，可以使用友元，实现get函数等方法去获取m_root，现在我们介绍一个新的方式
封装进类中
我们在_inorder中实现具体功能，然后封装到inorder中，inorder主要用于调用m_root给_inorder传递参数
3.2查找
由于我们在插入部分已经进行过查找数据，所以我们只需要对insert的代码稍微改一下即可
下面我们进行调试
对1的查找成功，对11的查找失败，符合预期
3.3删除
对于删除，总共有四种情况
情况1：delete节点为叶子节点
解决方法：找到该节点后让他的父节点指向nullptr，并释放该节点空间
情况2：delete节点只有左节点
解决方法：让他的父节点指向他的那一侧指向delete的左节点
情况3：delete节点只有右节点
解决方法：让他的父节点指向他的那一侧指向delete的右节点
情况4：delete节点左右节点均有
解决方法：寻找delete左子树的最大节点，或者delete右子树的最小节点，然后交换delete位置的值与replace节点的值，让replace的父节点空余的一侧指向replace节点的左侧（从左子树找时），或者右侧（从右子树找时）。最后释放replace位置的空间
疑问一：为什么是寻找delete左子树的最大节点，或者delete右子树的最小节点？
答：
因为我们需要保持二叉搜索树的排序结构，只能从左树找一个最大数据（保证替换后根大于左树，且由于是从左树找的数据，必然也是小于右树的数据的），或者从右数找一个最小数据（和左树同理）
疑问二：寻找到的replace节点为什么可以直接让其父节点接入另一侧？
答：
因为replace已经是最左或者最右节点，所以不可能两侧都有节点，最多只有另一侧有节点。
特殊情况分析：
（1）对于delete节点有左右节点，且replace的节点就是左子树根节点，或右子树根节点
我们需要把replace的父节点设置为cur，而不是空，否则会有空指针访问。
并且replace父节点的指向侧也不是确定的，这种情况下和会更新replace父节点的情况，父节点的指向侧是相反的
（2）对于delete节点只有右节点或左节点，且delete节点为搜索树的根节点
由于这种基于情况1,2,3的情况下，我们需要释放delete节点的空间，所以根节点需要删除就涉及根节点的指针指向变更。
我们对cur==m_root的情况用if语句单独处理，让m_root指向cur->left或cur->right
代码实现：
(1)大框架搭建：我们使用insert的代码作为查找大框架
我们的代码写在找到delete节点cur的位置
（2）对情况1-3进行处理，并把特殊情况1纳入考虑
由于右侧为空/左侧为空的情况可以兼容两侧为空的情况，所以我们不用单独处理两侧为空的情况
（1）cur左为空
对于cur左为空且cur为根节点：更改m_root,指向cur有节点的一侧，也就是右侧
对于cur非根节点的情况：让父节点指向cur的那一侧指向cur有节点的一侧
（2）cur右为空
（3）cur左右非空
我们实现的是从左子树中查找最大节点，也可以换成从右子树查找最小节点
第一步：
查找replace节点：循环更改replace与replaceprv指针，直到replace指向的节点右侧为空
第二步：
交换delete与replace节点的值
第三步：让replace父节点指向replace节点的左侧
注意:
若replace父节点就是cur，说明节点就在cur的左侧，用父节点左侧指向replace节点左侧。
若replace父节点不为cur，说明进入了循环，而replace父节点就是上一次的replace，replace一直在往右走，所以其父节点一定是右侧指向replace节点
