有序二叉树节点的删除

一、细节思考和分类

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

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; } } } }

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

运行结果：