二叉排序树的删除节点

首页 » 算法 » 二叉排序树的删除节点

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

思路:

  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的左子节点

       perent.left=targetNode.left

(5.2)如果targetNode是parent的右子节点

      parent.right=targetNode.left

6、如果tergetNode有右子节点

(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、targrtNode.value=temp
package tree.sort;

public class 二叉排序树 {
public static void main(String[] args) {
 int []arr= {7,3,10,12,5,1,9};
 treesort tree=new treesort();
 //添加
 for(int i=0;i<arr.length;i++)
  tree.add(new Node(arr[i]));
 System.out.println("删除前:");
 tree.show();
 tree.delNode(2);
 tree.delNode(5);
 tree.delNode(9);
 tree.delNode(12);
 tree.delNode(7);
 tree.delNode(3);
 tree.delNode(10);
 
 System.out.println("删除后:");
 tree.show();
}
}
//二叉树创建
class treesort{
 private Node root;
 public void add(Node node) {
  if(root==null) {
   root=node;
  }else {
   root.add(node);
  }
 }
 public void show() {
  if(root != null) {
   root.show();
  }else {
   System.out.println("空");
  }
 }
 //查找要删除的节点
 public Node find(int value) {
  if(root==null)
   return null;
  else {
   return root.find(value);
  }
 }
 //查找父节点
 public Node findParent(int value) {
  if(root==null)
   return null;
  else {
   return root.findParent(value);
  }
 }
 //删除节点****************************************
 /*
  * 二叉排序树的删除情况
  * 1、删除叶子节点
  * 2、删除只有一颗子树的节点
  * 3、删除有两颗子树的节点
  */
 
 
 /*
  * node传入的节点(当作二叉排序树的根节点)
  * 返回 以node为根节点的二叉排序树的最小节点的值
  * 删除node 为根节点的二叉排序树的最小节点
  */
 public int delRightMin(Node node) {
  Node target=node;
  //循环的查找左节点,就会找到最小值
  while(target.left != null) {
   target=target.left;
  }
  //这时 target已经指向了最小节点
  //删除最小节点
  delNode(target.value);
  return target.value;
 }
 
 //删除节点
 public void delNode(int value) {
  if(root == null)
   return;
  else {
   //找到要删除的节点
   Node targerNode=find(value);
   
   //如果targerNode=null
   if(targerNode==null) {
    return;
   }
   //如果发现当前这颗二叉树只有一个节点
   if(root.left==null&& root.right==null)
   {
    root=null;
    return;
   }
   //去找到targetNode的父节点
   Node parent=findParent(value);
   
   //如果删除的节点是叶子节点********************
   if(targerNode.left==null && targerNode.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(targerNode.left != null && targerNode.right != null) {
    //删除有两颗子树的节点********************
    int min=delRightMin(targerNode.right);
    targerNode.value=min;
   }else {//删除只有一颗子树的节点********************
    //如果要删除的节点有左子节点
    if(targerNode.left != null) {
     if(parent != null) {
     //如果targetNode是parent的左子节点
     if(parent.left.value == value) {
      parent.left=targerNode.left;
     }else {
      parent.right=targerNode.left;
     }
     }else {
      root=targerNode.left;
     }
    }else {
     if(parent != null) {
     //要删除的节点有右子节点;
     //如果targetNode 是parent的左子节点
     if(parent.left.value==value) {
      parent.left=targerNode.right;
     }else {
      //如果targetNode 是parent的右子节点
      parent.right=targerNode.right;
     }
     }else {
      root=targerNode.right;
     }
    }
   }
  }
 }
}

//节点
class Node{
 int value;
 Node left;
 Node right;
 public Node(int value) {
  this.value=value;
 }
 
 @Override
 public String toString() {
  return "Node [value=" + value + "]";
 }

 //递归的形式添加节点
 public void add(Node node) {
  if(node==null){
   return;
  }else {
   //判断传入的节点的值和当前子树的根节点的关系
   if(node.value<this.value) {
    if(this.left==null) {
     //如果当前节点左子节点为null
     this.left=node;
    }else {
     //递归的向左子树添加
     this.left.add(node);
    }
   }else {//添加的节点的值大于等于当前节点的值
    if(this.right==null) {
     this.right=node;
    }else {
     this.right.add(node);
    }
   }
  }
 }
 //中序遍历
 public void show() {
  if(this.left != null) {
   this.left.show();
  }
  System.out.println(this);
  if(this.right != null) {
   this.right.show();
  }
  
 }
 

 
 /*
  * 查找要删除的节点
  * value是要删除的节点
  * 如果找到返回该节点,否则返回null
  */
 public Node find(int value) {
  if(value==this.value) {
   return this;
  }else if(value<this.value){//如果查找的值小于当前节点,向左子树递归查找
   if(this.left!=null) {
    return this.left.find(value);
   }else {
    return null;
   }
  }else {
   //查找的值不小于当前的值
   if(this.right!=null) {
    return this.right.find(value);
   }else {
    return null;
   }
  }
 }
 /*
  * 查找要删除的节点的父节点
  * 返回的是要删除的节点的父节点
  */
 public Node findParent(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.findParent(value);
   }else if(value >= this.value && this.right!=null) {
    return this.right.findParent(value);
   }else {
    return null;
   }
  }
 }
 
 
}
分享到:
赞(0) 打赏

评论 4

评论前必须登录!

 

  1. #1

    靓仔6个月前 (03-28)
  2. #2

    挺明白的

    渣渣混6个月前 (03-28)
  3. #3

    最好再详细点

    小白6个月前 (03-28)
  4. #4

    记住这个网站了

    小白6个月前 (03-29)

觉得文章有用就打赏一下弟弟吧

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
正在播放:

作者想对您说:

累了就停下来听首歌吧

听完后会给您一个好心情

最后

等到您不容易

还希望您能多待一会儿

      00:00/00:00