用Java语言实现二叉树删除结点

时间:2021-08-08 21:57:34
首先定义结点类  class Node :

public  class Node {

public Node  leftchild=null;

public Node  rightchild=null;

public Node  parent=null;

}

然后再定义二叉树类 class  Btree

public  class Btree{

// 删除值为val的节点
 public void delete(Integer val) {

//先找到值为val的结点,调用函数Search(val)
  Node p = this.Search(val);

//找到节点后进行删除

//如果右孩子不为空,那么找到右孩子树中最小的值的结点,与节点的值进行交换,然后后继结点结点的父亲的孩子指向他的右孩子。在此用到了中序后继函数successor

     //(val),下面有定义。
  if (p.rightchild != null) {
   Node succ = this.successor(val);
   Integer i = p.value;
   p.value = succ.value;
   succ.value = i;
   //既然找到后继结点即最小值的结点,那么他就没有左孩子。
   if (succ == succ.parent.leftchild)
    succ.parent.leftchild = succ.rightchild;
   if (succ == succ.parent.rightchild)
    succ.parent.rightchild = succ.rightchild;

  }

//如果右孩子为空,找其父亲,

//如果是父亲的左孩子,那么直接让父亲的左孩子指向此节点的左孩子即直接将此节点删除

//如果是父亲的右孩子,那么直接让父亲的右孩子指向此节点的左孩子即直接将节点删除

//最后孩子的父亲指向此节点的父亲,实现双向指向
  else {
   if ( p.parent.leftchild==p)
    p.parent.leftchild = p.leftchild;
   if ( p.parent.rightchild==p)
    p.parent.rightchild = p.leftchild;
   p.leftchild.parent = p.parent;
  }

 }

 

 // 找到此节点,用到递归
 public Node Search(Integer val) {
  return this.search(this.root, val);
 }

 public Node search(Node p, Integer val) {
  if (p == null)
   return null;
  else {
   if (p.value == val) {

    return p;
   } 
   else {
    if (p.value < val) {
     return search(p.rightchild, val);
    } else {
     return search(p.leftchild, val);
    }

   }
  }
 }

 

 

 // 找到此节点的中序后继,中序后继:就是比此节点大的最小值,在此处用到了min(p.rightchild),下面有定义。顺便说一句:前驱:比此节点小的最大值,其操作和min函数

//类似
 public Node successor(Integer val) {
  Node p = this.Search(val);
  if (p.rightchild != null) {
   return this.min(p.rightchild);
  } 

else {
   while (p.parent != null) {
    if (p == p.parent.leftchild)
     break;
    p = p.parent;
   }
   return p.parent;
  }
 }

 // 找到后继树中最小的节点
 public Node min(Node r) {
  if (r == null)
   return null;
  else {
   while (r.leftchild != null) {
    r = r.leftchild;
   }
   return r;
  }
 }

}

 

 

最后是主函数类  class Main

public class Main {

 public static void main(String[] args) {
  Btree b =new Btree();
  Integer[] data={3,2,5,4,8,7,9};
  for(Integer i=0;i<data.length;i++){
   b.insert(data[i]);//insert(val)函数详见链接点击打开链接
  }
  b.preTravel();//二叉树的三种遍历,详见链接点击打开链接
  b.inTravel();
  b.postTravel();
  
  b.delete(8);
  
  b.preTravel();
  b.inTravel();
  b.postTravel();

  

 }

}