二叉排序树

　

二叉排序树

二叉排序树，也称二叉查找树。它或者是一个空树，或者具有以下性质：

左子树不为空，则左子树的所有结点的值小于它根节点的值

右子树不为空，则右子树的所有结点的值大于它根节点的值

它的左右子树也分别为二叉排序树

实现：

public class binarySortTree {

    /**
     *           30
     *        10     50
     *       5    20     60
     *      3  6
     *
     * @param args
     */
    public static void main(String[] args) {
        BinaryTree node = new BinaryTree();
        node.setData(30);
        BinaryTree node1 = new BinaryTree();
        node1.setData(10);
        BinaryTree node2 = new BinaryTree();
        node2.setData(5);
        BinaryTree node3 = new BinaryTree();
        node3.setData(20);
        BinaryTree node4 = new BinaryTree();
        node4.setData(50);
        BinaryTree node5 = new BinaryTree();
        node5.setData(60);
        BinaryTree node6 = new BinaryTree();
        node6.setData(3);
        BinaryTree node7 = new BinaryTree();
        node7.setData(6);


        node.setLchild(node1);
        node.setRchild(node4);
        node1.setLchild(node2);
        node1.setRchild(node3);
        node4.setRchild(node5);
        node2.setLchild(node6);
        node2.setRchild(node7);

//        searchBST(node, 6, null);
//        System.out.println(p.getData());
//        insertBST(node, 6);
//        System.out.println("插入成功");

        BinaryTree t = deleteBST(node, 60);
    }

    private static BinaryTree p;
    private static boolean result = false;
    private static BinaryTree q;

    /**
     * 二叉排序树   查找操作
     * 查找成功 返回当前结点
     * 查找失败 返回比较的 最后一个结点
     * f  用于记录上一个结点。查询失败，f记录的是最后一个不为空的结点 然后通过 变量传出来
     *
     * @param t
     * @param key
     */
    private static void searchBST(BinaryTree t, int key, BinaryTree f) {

        if (t != null) {
            if (t.getData() == key) {
                p = t;      //用于插入和删除
                q = f;   //存放 p的双亲结点   用于删除操作
                System.out.println("查找成功");
                result = true;
            } else if (t.getData() > key) {
                searchBST(t.getLchild(), key, t);
            } else {
                searchBST(t.getRchild(), key, t);
            }

        } else {
            p = f;
        }


}

    /**
     * 二叉排序树  插入操作   插入在查询结果的末尾
     * 关键：通过静态变量  将查询中最后一次递归的结果  传递出来
     *
     * @param t
     * @param key
     * @return
     */
    private static BinaryTree insertBST(BinaryTree t, int key) {
        searchBST(t, key, null);

        BinaryTree node = new BinaryTree();
        node.setData(key);
        if (p == null) {
            t = node;
        } else if (p.getData() > key) {
            p.setLchild(node);
        } else {
            p.setRchild(node);
        }

        return t;
    }

    /**
     * 二叉排序树  删除操作
     * 找到就删除，没找到不做处理
     * 删除方式： 1）用左子树最大的那个结点替代  也就是最右边那个  2）用右子树最小的那个结点替代   也就是最左边那个
     *
     * @param t
     * @param key
     */
    private static  BinaryTree deleteBST(BinaryTree t, int key) {

        searchBST(t, key, null);
        if(result == true){   // p肯定是匹配的那个结点

            if(p.getLchild() == null && p.getRchild() == null){  //左右子树都为空
                if(q.getLchild() == p){
                    q.setLchild(null);
                }
                if(q.getRchild() == p){
                    q.setRchild(null);
                }
            }else if(p.getLchild() == null && p.getRchild() != null){  //左子树为空

                BinaryTree node = p.getRchild();
                p.setData(node.getData());
                p.setLchild(node.getLchild());
                p.setRchild(node.getRchild());
            }else if(p.getLchild() != null && p.getRchild() == null){  //右子树为空

                BinaryTree node = p.getLchild();
                p.setData(node.getData());
                p.setLchild(node.getLchild());
                p.setRchild(node.getRchild());
            }else{                     //左右子树都不为空  取左子树最大的结点替代

                BinaryTree s = p.getLchild();
                if(s.getRchild() == null){
                    p.setData(s.getData());
                    p.setLchild(s.getLchild());
                }else {
                    BinaryTree pre = null;
                    while(s.getRchild() != null){
                        pre = s;
                        s = s.getRchild();
                    }
                    p.setData(s.getData());
                    pre.setRchild(s.getLchild());
                }

            }
        }

        return t;
    }


}



class BinaryTree{
    private int data;
    private BinaryTree lchild;
    private BinaryTree rchild;

   //省略set,get方法
}

注意：递归函数如果有返回值，始终只返回最外层的值

相关阅读