Java-二叉排序树的删除

考虑情况

二叉排序树的删除情况比较复杂，有下面三种情况要考虑 1.删除叶子节点 2.删除只有一颗子树的节点 3.删除有两颗子树的节点

思路分析

第一种情况：删除叶子节点

思路： 1.需求先去找到要删除的节点targetNode 2.找到targetNode的父节点parent 3.确定targetNode是parent的左子节点还是右子节点 4.根据情况对应删除

第二种情况：删除只有一颗子树的节点

思路： 1.需求先去找到要删除的节点targetNode 2.找到targetNode的父节点parent 3.确定targetNode的子节点是左子节点还是右子节点 4.确定targetNode是parent的左子节点还是右子节点 5.如果targetNode有左子节点 5.1如果targetNode是parent的左子节点，parent.left=targetNode.left。 5.2如果targetNode是parent的右子节点，parent.right=targetNode.left。 6.如果targeyNode有右子节点 6.1如果targetNode是parent的左子节点，parent.left=targetNode.right. 6.2如果targetNode是parent的右子节点，parent.right=targetNode.right

第三种情况：删除有两颗子树的节点

思路： 1.需求先去找到要删除的节点targetNode 2.找到targetNode的父节点parent 3.从targetNode的右子树找到最小的节点 4.用一个临时变量，将最小节点的值保存 5.删除该最小节点 6.targetNode.value=temp

代码实现

//查找要删除的节点 public Nodes search(int value) { if(value==this.value) { return this; }else if(value<this.value) {//如果查找值小于当前节点，则向左子树递归查找 //如果左子节点为空 if(this.left==null) { return null; } return this.left.search(value); }else { if(this.right==null) { return null; } return this.right.search(value); } } //查找要删除节点的父节点 public Nodes searchParent(int value) { //如果当前节点就是要删除节点的父节点，就返回 if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)) { return this; }else { //如果查找的值小于当前节点的值，并且当前节点的左子节点不为空 if(value<this.value&&this.left!=null) { return this.left.searchParent(value); }else if(value>=this.value&&this.right!=null){ return this.right.searchParent(value); }else { return null;//没有找到父节点 } } } public Nodes search(int value) { if(root==null) { return null; }else { return root.search(value); } } //查找父节点 public Nodes searchParent(int value) { if(root==null) { return null; }else { return root.searchParent(value); } } //删除节点 public void delNode(int value) { if(root==null) { return; }else { //先找到要删除的节点 Nodes targetNode=search(value); //如果没有找到要删除的节点 if(targetNode==null) { return; } //如果我们发现当前的二叉树只有一个节点 if(root.left==null&&root.right==null) { root=null; return; } //去找到targetNode的父节点 Nodes parent=searchParent(value); //如果要删除的是叶子节点 if(targetNode.left==null&&targetNode.right==null) { //判断targetNode是父节点的左子节点还是右子节点 if(parent.left!=null&&parent.left.value==value) { parent.left=null; }else if(parent.right==null&&parent.right.value==value) { parent.right=null; } }else if(targetNode.left!=null&&targetNode.right!=null) {//删除有两颗子树的节点 int minValue=delRightTreeMin(targetNode.right); targetNode.value=minValue; }else {//删除只有一颗子树的节点 //如果要删除的节点有左子节点 if(targetNode.left!=null) { //如果targetNode是parent的左子节点 if(parent.left.value==value) { parent.left=targetNode.left; }else { parent.right=targetNode.left; } }else {//要删除的节点有右子节点 if(parent.left.value==value) { parent.left=targetNode.right; }else { parent.right=targetNode.right; } } } } } //查找最小节点 public int delRightTreeMin(Nodes node) { Nodes target=node; while(target.left!=null) { target=target.left; } delNode(target.value); return target.value; }