二叉排序树删除某个结点保持排序树特性的Java算法实现

一、二叉排序树的定义
二叉排序树是一棵空树；或者是具有下列性质的二叉树：
1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）它的左右子树也分别为二叉排序树
图

二、二叉排序树删除一个结点的情况讨论
待删除的结点记为 p，父结点为f，且p为f的左子树
1）若p结点为叶子结点，可直接删除，如删除“24”。
2）若p结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其父结点f的左子树即可，如删除“61”，令“90”结点为“100”结点的左子树
3）若p结点的左子树或右子树均不空，（如删除“12”结点，在删除之前，中序遍历该二叉树为“3 12 24 37 45 53 61 78 90 100”）在删去p之后，为保持其他元素之间的相对位置不变，可以有两种做法：
a 令p的左子树为f的左子树，而p的右子树为s（直接前驱）的右子树。
b 令p的直接前驱（或直接后继）替代p，然后再从二叉排序树中删去它的直接前驱（或直接后继）

代码：

/*
 * 树结点
 */
public class TreeEle {

    public int data;//元素数据
    public TreeEle lcd;//左孩子
    public TreeEle rcd;//右孩子
}

import java.util.Scanner;

import com.hgldp.web.pojo.TreeEle;

public class DeleteEle {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        TreeEle t = new TreeEle();
        /*
        * 依次输入：45 12 53 3 37 24 100 61 90 78
        */
        for(int i = 0;i < 10;i++){
            System.out.println("输入一个元素：");
            int e = sc.nextInt();
            init(t,e);
        }
        printTree(t);
        boolean flag = deleteBst(t, 12);
        if(!flag){
           System.out.println("删除失败");
           return;
        }
        System.out.println("\n删除12之后");
        printTree(t);
    }

    /*
     * 中序遍历二叉树
     */
    public static void printTree(TreeEle e){
        if(e == null){
            return;
        }else{
            printTree(e.lcd);
            System.out.print(e.data+" ");
            printTree(e.rcd);
        }
    }

    /*
     * 初始化二叉排序树
     */
    public static void init(TreeEle t,int em){
        if(t.data ==  0){//根结点
            t.data = em;
            return;
        }else if(t.data == em){
            System.out.println("不能插入重复数据");
            return;
        }else if(t.data < em){
            if(t.rcd == null) t.rcd = new TreeEle();
            init(t.rcd,em);
        }else if(t.data > em){
            if(t.lcd == null) t.lcd = new TreeEle();
            init(t.lcd,em);
        }
    }

    /*
     * 删除树的结点
     */
    public static boolean deleteBst(TreeEle e,int key){ 
        if(e == null)
        {
            return false;
        }else{
            if(e.data == key){
                return delete(e);
            }else if(e.data < key){
                return deleteBst(e.rcd,key);
            }else{
                return deleteBst(e.lcd,key);
            }
        }
    }

    /*
     * 删除
     */
    public static boolean delete(TreeEle e){
        boolean flag=false;
        if(e.rcd == null){//右子树为空，则只需要重接它的左子树
            e.data = e.lcd.data;
            e.lcd = e.lcd.lcd;
            e.rcd = e.rcd;
            flag = true;
        }else if(e.lcd == null){//左子树为空，重接它的右子树
            e.data = e.rcd.data;
            e.lcd = e.rcd.lcd;
            e.rcd = e.rcd.rcd;
            flag = true;
        }else{//左右子树均不为空
            /*
             * 令p的直接前驱替代p，然后再从二叉排序树中删去它的直接前驱（覆盖）
            */
            TreeEle s = e.lcd;
            TreeEle q = e;
            while(s.rcd!=null){//转左，然后向右转到尽头,找到被删结点的前驱
                q = s;
                s = s.rcd;
            }
            e.data = s.data;//s指向被删结点的前驱
            if(q != e){ //地址比较
                q.rcd = s.lcd;//重接q的右子树
            }else{
                q.lcd = s.lcd;//重接q的左子树
            }
            flag = true;
        }
        return flag;
    }
}