news 2026/5/8 18:03:55

有序二叉树节点的删除

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
有序二叉树节点的删除

一、细节思考和分类

我们删除二叉树的节点时候，要保证删除以后的数据继续保持有序状态，那么就会分为三种情况

a.删除叶子节点；

b.删除只有一个子节点的节点；

c.删除有两个子节点的节点。

二、实现思路和代码实现

1.删除叶子节点

实现思路：

①找到要删除的节点targetNode；

②找到targetNode的父节点parentNode（判断是否存在）；

③确定当前targetNode是parentNode的左子树和右子树；

④根据以上情况进行删除：

左子节点：parentNode.lChild==null;

右子节点: parentNode.rChild==null;

代码实现:

//确定targetNode是parentNode的左子树还是右子树 if(parentNode.lChild!=null&&parentNode.lChild==target){ parentNode.lChild=null; } else if(parentNode.rChild!=null&&parentNode.rChild==target){ parentNode.rChild=null; }

判断是targetNode是parentNode的左子树还是右子树,是哪边的树就让哪边指空.

2.删除有两个子节点的节点

实现思路:

①找到要删除的节点targetNode；

②找到targetNode的父节点parentNode（判断是否存在）；

③去找targetNode的右子树的最小值;

④将targetNode的右子树最小值替换掉targetNode的值;

⑤删除targetNode右子树的最小值.

代码实现:

if(targetNode!=null&&targetNode.rChild!=null){ int min=findRightTreeMin(targetNode.rChild); targetNode.data=min; }

3.删除只有一个子节点的节点

实现思路:

①找到要删除的节点targetNode；

②找到targetNode的父节点parentNode（判断是否存在）；

③确定当前targetNode是parentNode的左子树和右子树；

④判断targetNode的子节点是其左子树还是右子树:

分为四种情况:

如果targetNode是parentNode左子树

Ⅰ targetNode有左子节点

parentNode.lChild=targetNode.lChild;

Ⅱ targetNode有右子节点

parentNode.lChild=targetNode.rChild;

如果targetNode是parentNode右子树

Ⅲ targetNode有左子节点

parentNode.rChild=targetNode.lChild;

Ⅳ targetNode有右子节点

parentNode.rChild=targetNode.rChild;

代码实现:

if(parentNode.lChild!=null && parentNode.lChild.data == target){ //确定targetNode是parentNode的左子树 if(targetNode.lChild != null){ //targetNode有左子结点 parentNode.lChild = targetNode.lChild; }else { //targetNode有右子结点 parentNode.lChild = targetNode.rChild; } }else if(parentNode.rChild!=null && parentNode.rChild.data == target){ //确定targetNode是parentNode的右子树 if(targetNode.lChild != null){ //targetNode有左子结点 parentNode.rChild = targetNode.lChild; }else { //targetNode有右子结点 parentNode.rChild = targetNode.rChild; }

4.需要注意的点

此外我们要注意一个点，万一要删除的点仅有一个节点，我们就要：

if(root.lChild == null && root.rChild == null){ root = null; return; }

5.需要添加的额外方法

分别是

①找到要删除的节点

// 找到要删除的节点 TreeNode findTarget(TreeNode root,Integer target){ if(root == null){ return null; } //去找这个值 if(root.data == target){ return root; }else if(target < root.data){ //判断是否有左子树 if(root.lChild == null){ return null; } return findTarget(root.lChild,target); }else { //判断是否有右子树 if (root.rChild == null) { return null; } return findTarget(root.rChild, target); } }

②找要删除节点的父节点

//去找要删除节点的父节点 TreeNode findParent(TreeNode root,Integer target){ if(root == null){ return null; } if((root.lChild!=null) && (root.lChild.data == target) || (root.rChild!=null) && (root.rChild.data == target)){ return root; }else { if(root.lChild!=null && target < root.data){ return findParent(root.lChild,target); }else if(root.rChild!=null && target > root.data){ return findParent(root.rChild,target); }else { return null; } } }

③找右子树的最小值

public int findRightTreeMin(TreeNode node){ while (node.lChild !=null){ node = node.lChild; } int min = node.data; delete(root, min); return min; }

三、完整代码的运行和运行结果

完整代码：

TreeNode findTarget(TreeNode root,Integer target){ if(root == null){ return null; } //去找这个值 if(root.data == target){ return root; }else if(target < root.data){ //判断是否有左子树 if(root.lChild == null){ return null; } return findTarget(root.lChild,target); }else { //判断是否有右子树 if (root.rChild == null) { return null; } return findTarget(root.rChild, target); } } //去找要删除节点的父节点 TreeNode findParent(TreeNode root,Integer target){ if(root == null){ return null; } if((root.lChild!=null) && (root.lChild.data == target) || (root.rChild!=null) && (root.rChild.data == target)){ return root; }else { if(root.lChild!=null && target < root.data){ return findParent(root.lChild,target); }else if(root.rChild!=null && target > root.data){ return findParent(root.rChild,target); }else { return null; } } } /** * 去找右子树的最小值 * @param node * @return */ public int findRightTreeMin(TreeNode node){ while (node.lChild !=null){ node = node.lChild; } int min = node.data; delete(root, min); return min; } public void delete(TreeNode root,Integer target){ if(root == null){ return; } //2.万一要删的节点只有一个节点 if(root.lChild == null && root.rChild == null){ root = null; return; } //1.去找被删除的节点 TreeNode targetNode = findTarget(root,target); if(targetNode == null){ //找不到 return; } //3.找到父节点 TreeNode parentNode = findParent(root,target); //分情况进行删除 if(targetNode.lChild == null && targetNode.rChild == null){ //叶子节点 //确定targetNode是parentNode的左子树还是右子树 if(parentNode.lChild != null && parentNode.lChild.data == target){ parentNode.lChild = null; }else if(parentNode.rChild != null && parentNode.rChild.data == target){ parentNode.rChild = null; } }else if(targetNode.lChild != null && targetNode.rChild != null){ //有两个子节点的节点 int min = findRightTreeMin(targetNode.rChild); targetNode.data = min; }else { //targetNode 只有一个子节点的节点 //确定targetNode是parentNode的左子树还是右子树 if(parentNode.lChild!=null && parentNode.lChild.data == target){ //确定targetNode是parentNode的左子树 if(targetNode.lChild != null){ //targetNode有左子结点 parentNode.lChild = targetNode.lChild; }else { //targetNode有右子结点 parentNode.lChild = targetNode.rChild; } }else if(parentNode.rChild!=null && parentNode.rChild.data == target){ //确定targetNode是parentNode的右子树 if(targetNode.lChild != null){ //targetNode有左子结点 parentNode.rChild = targetNode.lChild; }else { //targetNode有右子结点 parentNode.rChild = targetNode.rChild; } } } }

测试类：构建相应的树然后指出删除节点

运行结果：

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/5/8 2:02:35

GB/T 34399器械冷链温控验证新标准：质量保障的科技防线

新标准扩展了验证范围&#xff0c;新增温控柜、冷藏箱等设备验证要求&#xff0c;细化了温度分布测试布点规则。明确要求验证数据采集间隔不超过2分钟&#xff0c;冷藏设备温度偏差、均匀度、波动度不超过3℃&#xff0c;大幅提升数据精确性。对医疗器械企业而言&#xff0c;标…

作者头像 李华
网站建设 2026/5/1 5:34:50

【完整源码+数据集+部署教程】天线检测与目标识别系统源码分享[一条龙教学YOLOV8标注好的数据集一键训练_70+全套改进创新点发刊_Web前端展示]

一、背景意义 随着无线通信技术的迅猛发展&#xff0c;天线作为无线信号传输和接收的关键组件&#xff0c;其检测与识别的重要性日益凸显。传统的天线检测方法多依赖于人工巡检和经验判断&#xff0c;效率低下且容易受到人为因素的影响&#xff0c;难以满足现代通信网络对高效、…

作者头像 李华
网站建设 2026/5/6 1:43:37

拉普拉斯特征图-目标函数化简推导（手写详细）

学到了很多算法和公式&#xff0c;老师们总是一带而过&#xff0c;这里按照老师课件中推导了一次&#xff0c;并补充了比较困惑的内容&#xff1a;tr&#xff08;迹&#xff09;是怎么被引入公式的这里发现还有两个地方需要补充一下&#xff1a;1.矩阵求导法则/迹求导法则2.广义…

作者头像 李华
网站建设 2026/5/2 21:33:37

Windows GUI 逆向分析题（CrackMe）

首先下载文件在detect it easy中进行查壳&#xff0c;从 DIE 结果可以知道&#xff1a;PE32&#xff0c;32 位 GUI 程序&#xff08;Windows GUI&#xff09;编译器&#xff1a;Microsoft Visual C/C (12.00.9782)调试信息&#xff1a;包含 PDB 路径&#xff08;说明可能有符号…

作者头像 李华