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