Java实现二叉排序树

public class SearchBST {

    //二叉树类
    private static class BinaryTree{
        int data;
        BinaryTree lchild;
        BinaryTree rchild;
    }
    static BinaryTree newTree = new BinaryTree(); //树的根结点

    //全局变量:存放查找到的关键字所在的父结点
    static BinaryTree parentNode = new BinaryTree();
    /*
    * @desc: 二叉排序树(二叉查找树)
    * @param bt：待查询的二叉排序树
    * @param key：查找关键字
    * @param parent: 指向bt的双亲,其初始化值为null
    * @return: boolean  查找成功,返回true，并把树结点赋给全局变量parentNode，查找失败，返回false
    */
    public static boolean searchBST(BinaryTree bt,int key,BinaryTree parent){
        if (null == bt || 0 == bt.data){ //树结点不存在,返回
            parentNode = parent;
            return false;
        }else if (key == bt.data){ //查找成功
            parentNode = bt;
            return true;
        }else if (key < bt.data){ //关键字小于根结点则查找左子树
            return searchBST(bt.lchild,key,bt);
        }else{ //关键字大于根结点则查找右子树
            return searchBST(bt.rchild,key,bt);
        }
    }
    /*
    * @desc: 向二叉树中插入关键字key(如果不存在)
    * @param bt：二叉排序树
    * @param key: 插入的关键字
    * @return: boolean 插入成功返回true,插入失败返回false
    */
    public static boolean insertBST(BinaryTree bt,int key){
        BinaryTree s;
        if (!searchBST(bt,key,null)){
            s = new BinaryTree();
            s.data = key;
            s.lchild = s.rchild = null;
            if (null == parentNode){ //不存在，则表明时父结点,将s指向bt成为新的根结点
                bt = s;
            }else if (key < parentNode.data){//当key小于根结点,则插入为左孩子
                parentNode.lchild = s;
            }else{ //当key大于根结点,则插入为右孩子
                parentNode.rchild = s;
            }
            preOrderTraverse(bt); //中序遍历二叉树
        }else{
            System.out.println("该结点已经存在!");
        }
        return false;
    }

    /*
    * @desc: 中序遍历
    * @param t: 二叉树
    * @return: void
    */
    static void preOrderTraverse(BinaryTree t){
        if (null == t || 0 == t.data){
            return;
        }
        if (null != t.lchild){
            preOrderTraverse(t.lchild); //中序遍历左子树
        }
        if (0 != t.data){
            System.out.println("[" + t.data + "]");//显示当前结点数据
        }
        if (null != t.rchild){
            preOrderTraverse(t.rchild);//中序遍历右子树
        }
    }
    /*
    * @desc: 生成二叉排序树
    * @param key: 插入的关键字
    * @return: boolean
    */
    public static boolean generateBST(int key){
        if (!searchBST(newTree,key,null)){
            BinaryTree s = new BinaryTree();
            s.data = key;
            s.lchild = s.rchild = null;
            if (null == parentNode){ //不存在,则表明是父结点,将s指向bt成为新的根结点
                newTree = s;
            }else if (key < parentNode.data){//当key小于根结点,则插入为左孩子
                parentNode.lchild = s;
            }else{ //当key大于根结点,则插入为右孩子
                parentNode.rchild = s;
            }
            preOrderTraverse(newTree);
            return true;
        }else{
            System.out.println("该结点已经存在!");
        }
        return false;
    }

    /*
    * @desc: 从二叉排序树种删除结点p,并重接它的左或右子树
    * @param bt: 二叉排序树
    * @return: boolean
    */
    public static boolean delete(BinaryTree bt){
        BinaryTree q,s;
        if (null == bt.rchild){ //右子树为空则只需要接左子树
            bt = bt.lchild;
        }else if (null == bt.lchild){ //左子树为空则只需要接右子树
            bt = bt.rchild;
        }else{
            q = bt;
            s = bt.lchild;
            while (null != s.rchild){ //转左，然后向右到尽头(找到待删除结点的前驱)
                q = s;
                s = s.rchild;
            }
            bt.data = s.data; //s指向被删除结点的直接前驱
            if ( q != bt){
                q.rchild = s.lchild; //重接q的右子树
            }else{ //q.data == bt.data，则说明s.rchild == null
                q.lchild = s.lchild; //重接q的左子树
            }
        }
        return true;
    }

    /*
    * @desc: 二叉排序树的删除
    * @param bt：二叉排序树
    * @param key: 待删除的关键字
    * @return: boolean
    */
    public static boolean deleteBST(BinaryTree bt,int key){
        if (!searchBST(bt,key,null)){ //不存在关键字等于key的元素
            return false;
        }else{
            if (bt.data == key){
                return delete(bt);
            }else if (key < bt.data){
                return deleteBST(bt.lchild,key);
            }else{
                return deleteBST(bt.rchild,key);
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {62,88,58,47,35,73,51,99,37,93};

        long start = System.currentTimeMillis(); //算法的开始时间
        for (int i = 0; i < a.length; i++) {
            generateBST(a[i]);
            System.out.println();
        }
        System.out.println(searchBST(newTree,99,null));
        long end = System.currentTimeMillis(); //算法的结束时间
        System.out.println("耗时："+(end-start)+"ms");
    }
}