网站备案成功后可以改吗,建网站 赚钱,在线设计发型,django做的网站模板1.二叉搜索树的定义 二叉搜索树要么是空树#xff0c;要么是满足以下特性的树 #xff08;1#xff09;左子树不为空#xff0c;那么左子树左右节点的值都小于根节点的值 #xff08;2#xff09;右子树不为空#xff0c;那么右子树左右节点的值都大于根节点的值 #…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删除 对于删除总共有四种情况 情况1delete节点为叶子节点 解决方法找到该节点后让他的父节点指向nullptr并释放该节点空间 情况2delete节点只有左节点 解决方法让他的父节点指向他的那一侧指向delete的左节点 情况3delete节点只有右节点 解决方法让他的父节点指向他的那一侧指向delete的右节点 情况4delete节点左右节点均有 解决方法寻找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节点的空间所以根节点需要删除就涉及根节点的指针指向变更。 我们对curm_root的情况用if语句单独处理让m_root指向cur-left或cur-right 代码实现 (1)大框架搭建我们使用insert的代码作为查找大框架 我们的代码写在找到delete节点cur的位置 2对情况1-3进行处理并把特殊情况1纳入考虑 由于右侧为空/左侧为空的情况可以兼容两侧为空的情况所以我们不用单独处理两侧为空的情况 1cur左为空 对于cur左为空且cur为根节点更改m_root,指向cur有节点的一侧也就是右侧 对于cur非根节点的情况让父节点指向cur的那一侧指向cur有节点的一侧 2cur右为空 3cur左右非空 我们实现的是从左子树中查找最大节点也可以换成从右子树查找最小节点 第一步 查找replace节点循环更改replace与replaceprv指针直到replace指向的节点右侧为空 第二步 交换delete与replace节点的值 第三步让replace父节点指向replace节点的左侧 注意: 若replace父节点就是cur说明节点就在cur的左侧用父节点左侧指向replace节点左侧。 若replace父节点不为cur说明进入了循环而replace父节点就是上一次的replacereplace一直在往右走所以其父节点一定是右侧指向replace节点
