企业官网建设流程全解析

网站优化seo方案,邢台市第三医院,wordpress如何网页浏览数据库,肇东网站制作有序二叉树#xff08;二叉搜索树#xff09;的核心特性是左子树节点值 根节点值 右子树节点值#xff0c;删除节点时需要保证删除后树的有序性不被破坏。一、为什么删除有序二叉树节点这么麻烦#xff1f;普通二叉树删除节点只需要断开引用#xff0c;但有序二…有序二叉树二叉搜索树的核心特性是左子树节点值 根节点值 右子树节点值删除节点时需要保证删除后树的有序性不被破坏。一、为什么删除有序二叉树节点这么麻烦普通二叉树删除节点只需要断开引用但有序二叉树不行它的节点值之间有严格的大小关系约束。比如删除一个中间节点后必须找到合适的节点 “填补空位”同时保证整个树的有序性。根据目标节点的子节点数量删除操作可以分为三种核心场景我们逐个拆解。二、删除的三种场景先看一个示例有序二叉树后续所有例子都基于这棵树7 / \ 3 10 / \ / 1 5 9 / 2场景 1删除叶子节点无左右子节点叶子节点是树的 “末梢”比如上面树中的2、5、9。原理叶子节点没有子节点删除后不会影响其他节点的关系只需要断开父节点对它的引用即可。步骤拆解1.找到要删除的目标节点比如52.找到目标节点的父节点5的父节点是33.判断目标节点是父节点的左子节点还是右子节点5是3的右子节点4.将父节点对应的子节点引用置为null把3的右子节点设为null。场景 2删除只有一个子节点的节点比如树中的1只有右子节点2、10只有左子节点9。原理目标节点有且只有一个子节点删除后需要让这个子节点 “接替” 目标节点的位置保持树的连续有序。步骤拆解以删除1为例1.找到目标节点1和它的父节点32.确定1是3的左子节点3.确定1的子节点是右子节点24.让3的左子节点直接指向2相当于2接替了1的位置。场景 3删除有两个子节点的节点最复杂比如树中的3有左子节点1、右子节点5、7有左子节点3、右子节点10。难点目标节点有两个子节点直接删除会导致两个子树 “悬空”无法直接接替位置。解决方案用目标节点右子树的最小值或左子树的最大值来替换目标节点的值 —— 因为右子树的最小值是比目标节点大的节点中最小的那个替换后能保证树的有序性而这个最小值节点必然是叶子节点或只有一个子节点右子树的最小值是最左侧节点后续删除它就回到了前两种简单场景。步骤拆解以删除3为例1.找到目标节点32.找到3的右子树节点5并找到该子树的最小值就是5本身3.用5的值替换3的值4.删除右子树中的最小值节点5此时5是叶子节点回到场景 1 的删除逻辑。三、核心工具方法实现1. 查找父节点findParent.要删除节点必须先找到它的父节点才能修改引用。这个方法通过递归遍历树利用有序二叉树的 “左小右大” 特性定位父节点。通过递归遍历树找到目标节点的父节点// 查找目标节点的父节点 public TreeNode findParent(TreeNode root, Integer data) { TreeNode current root; if (current null) { return null; } // 当前节点的左/右子节点是目标节点 → 当前节点是父节点 if ((current.lChild ! null current.lChild.data data) || (current.rChild ! null current.rChild.data data)) { return current; } else { // 递归查找根据有序性向左/右子树遍历 if (current.data data current.rChild ! null) { return findParent(current.rChild, data); } else if (current.data data current.lChild ! null) { return findParent(current.lChild, data); } else { return null; // 未找到父节点目标节点不存在 } } }逻辑解读先判断当前节点的子节点是否是目标节点如果是直接返回当前节点如果不是根据目标值和当前节点的大小关系递归遍历左 / 右子树全程要判断子节点是否为空避免空指针异常。2. 查找右子树最小值findRightTreeMin这个方法是为 “场景 3两个子节点” 服务的找到右子树的最小值同时删除这个最小值节点因为后续要拿它替换目标节点的值。// 查找右子树的最小值并删除该节点 public int findRightTreeMin(TreeNode node) { // 遍历到最左侧节点最小值 while (node.lChild ! null) { node node.lChild; } int min node.data; delete(root, min); // 删除这个最小值节点 return min; }逻辑解读右子树的最小值一定在最左侧因为左子节点值 父节点值找到最小值后调用delete方法删除它此时删除的是简单场景的节点返回这个最小值用于替换目标节点的值。四、删除方法完整实现delete有了辅助方法我们可以实现最终的delete方法把三种删除场景的逻辑整合起来。首先要明确实现delete前需要先有find方法用于查找目标节点find方法我们再上一篇博客已经实现逻辑类似findParent找到目标节点后返回详情请查看上一篇博客。public void delete(TreeNode root, Integer data) { if (root null) { return; } // 特殊情况树只有根节点直接置空 if (root.rChild null root.lChild null) { root null; return; } // 1. 找到目标节点 TreeNode targetNode find(root, data); if (targetNode null) { // 目标节点不存在 return; } // 2. 找到父节点 TreeNode parentNode findParent(root, data); // 情况1删除叶子节点 if (targetNode.rChild null targetNode.lChild null) { if (parentNode.rChild targetNode) { parentNode.rChild null; } else if (parentNode.lChild targetNode) { parentNode.lChild null; } } // 情况2删除有两个子节点的节点 else if (targetNode.rChild ! null targetNode.lChild ! null) { int min findRightTreeMin(targetNode.rChild); targetNode.data min; // 替换目标节点的值 } // 情况3删除只有一个子节点的节点 else { if (parentNode.lChild targetNode) { // 目标是父节点的左子树 if (targetNode.lChild ! null) { parentNode.lChild targetNode.lChild; } else { parentNode.lChild targetNode.rChild; } } else if (parentNode.rChild targetNode) { // 目标是父节点的右子树 if (targetNode.lChild ! null) { parentNode.rChild targetNode.lChild; } else { parentNode.rChild targetNode.rChild; } } } }五、代码测试package com.qcby.Tree; public class Test { public static void main(String[] args) { BinaryTree bt new BinaryTree(); bt.create(7); bt.create(3); bt.create(10); bt.create(1); bt.create(5); bt.create(9); bt.create(2); bt.delete(bt.root, 2); //输出7 3 10 1 5 9 2 bt.levelOrder(bt.root); bt.delete(bt.root, 1); //输出7 3 10 2 5 9 bt.levelOrder(bt.root); bt.delete(bt.root, 7); //输出9 3 10 1 5 2 bt.levelOrder(bt.root); } }