首先定义结点类 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();
}
}