? ? ? ? }
? ? }
? ?
? ?
? ? /*
? ? * 删除结点
? ? */
? ? public void delete(int data){? ?
? ? ? ? Node node;
? ? ? ? if((node=searchNode(new Node(data)))==null){//注意！这里不能new结点！你必须从树中找该结点！new就是初始化了
? ? ? ? ? ? System.out.println("二叉树中不存在此结点！");
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? deleteNode(node);
? ? ? ? System.out.println("删除结点"+data+"后：");
? ? ? ? this.midOrderTraverse();
? ? }
? ?
? ?
? ? private void deleteNode(Node node){
? ? ? ? if(node==null){
? ? ? ? ? ? System.out.println("删除结点不能为空！");
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? replacedNode(node);
? ? }
? ?
? ? private void replacedNode(Node node) {? ? //替换结点
? ? ? ? if(node.leftChild!=null
? ? ? ? ? ? ? ? &&node.rightChild!=null){? ? //当有左右孩子时，用后继结点替换
? ? ? ? ? ? replacedNodeOfPost(node);
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? if(node.leftChild!=null){? ? //当只有左孩子时，直接用左子树替换
? ? ? ? ? ? ? ? node=node.leftChild;
? ? ? ? ? ? }else if(node.rightChild!=null){? ? //只有右孩子时，直接有子树替换
? ? ? ? ? ? ? ? node=node.rightChild;
? ? ? ? ? ? }else{? ? ? ? ? ? //当没有左右孩子时，就直接释放了这个结点
? ? ? ? ? ? ? ? freeNode(node);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ?
? ?
? ? private void freeNode(Node node) {? ? //释放该结点，断掉其与父结点的链接
? ? ? ? if(node==node.parent.leftChild){
? ? ? ? ? ? node.parent.leftChild=null;
? ? ? ? }else{
? ? ? ? ? ? node.parent.rightChild=null;
? ? ? ? }
? ? }
? ?
? ? private void replacedNodeOfPost(Node node) {? ?
? ? ? ? Node y=this.getPostNode(node);? ? //找后继结点
? ? ? ? node.key=y.key;
? ? ? ? replacedNode(y);? ? //替换了key之后，再一次递归把现在这个结点给替换了！
? ? }
? ?
}
最后是测试结果：
------------------分割线-------------------------
先序遍历：
-12--4--3--2--5--4--7--6--8--9-
中序遍历：
-2--3--4--4--5--6--7--8--9--12-
后序遍历：
-12--4--3--2--5--4--7--6--8--9-
插入结点：15
中序遍历：
-2--3--4--4--5--6--7--8--9--12--15-
您要查找的是：7
查找7成功！
您要查找的是：100
树中没有该结点！
最大的结点是：15
最小的结点是：2
7的前驱结点：
7的前驱结点为：6
2的前驱结点：
该结点不存在或无前驱结点！
7的后继结点：
7的后继结点为：8
15的后继结点：
该结点不存在或无后继结点！
删除结点5后：
中序遍历：
-2--3--4--4--6--7--8--9--12--15-
二叉树中不存在此结点！