Java写一个二叉查找树

简介

二叉树成为二叉查找树的性质是，对于树中的每个节点X,它的左子树中所有项的值小于X中的项，而它的右子树中所有项的值大于X中的项。

要求

• 要有节点类、实现比较器，使得节点可以compareTo，使用泛型表节点数据
• 成员变量：一个根节点
• 成员方法：BinarySearchTree、contains、findMin、findMax、insert、remove

代码

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {

    private BinaryNode<AnyType> root;

    public BinarySearchTree() {
        this.root = null;
    }


    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(AnyType x) {
        return contains(x, root);
    }

    public AnyType findMin() {
        if (isEmpty()) {
            return null;
        }
        return findMin(root).element;
    }

    public AnyType findMax() {
        if (isEmpty()) {
            return null;
        }
        return findMax(root).element;
    }

    public void insert(AnyType x) {
        root = insert(x, root);
    }

    public void remove(AnyType x) {
        root = remove(x, root);
    }

    public void printTree() {

    }

    /**
     * 内部方法查找子树中的项。
     *
     * @param x 搜索项目
     * @param t 子树的根节点
     * @return 如果项目被发现，则为真;否则为假
     */
    private boolean contains(AnyType x, BinaryNode<AnyType> t) {

        if (t == null) {
            return false;
        }
        int compareResult = x.compareTo(t.element);

        if (compareResult < 0) {
            return contains(x, t.left);
        } else if (compareResult > 0) {
            return contains(x, t.right);
        } else {
            return true;
        }
    }

    /**
     * 递归查找
     *
     * @param t 子树的根节点
     * @return 找到的值
     */
    private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
        if (t == null) {
            return null;
        } else if (t.left == null) {
            return t;
        }
        return findMin(t.left);
    }

    private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
        if (t != null) {
            while (t.right != null) {
                t = t.right;
            }
        }
        return t;
    }

    /**
     * 内部方法插入到子树中
     *
     * @param x 要插入的项
     * @param t 子树的根节点
     * @return the new root of the subtree
     */
    private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) {
            return new BinaryNode<>(x, null, null);
        }

        // 对比，-1小于，0相等，1大于
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0) {
            t.left = insert(x, t.left);
        } else if (compareResult > 0) {
            t.right = insert(x, t.right);
        } else { // Duplicate; do nothing

        }
        return t;
    }

    /**
     * 从一颗子树移除
     *
     * @param x 被移除的项
     * @param t 子树的根节点
     * @return 新的值
     */
    private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) {
            return t;
        }
        int compareResult = x.compareTo(t.element);

        if (compareResult < 0) {
            t.left = remove(x, t.left);
        } else if (compareResult > 0) {
            t.right = remove(x, t.right);
        } else if (t.left != null && t.right != null) {
            t.element = findMin(t.right).element;
            t.right = remove(t.element, t.right);
        } else {
            t = (t.left != null) ? t.left : t.right;
        }
        return t;
    }

    private void printTree(BinaryNode<AnyType> t) {

    }


    private static class BinaryNode<AnyType> {
        AnyType element;
        BinaryNode<AnyType> left;
        BinaryNode<AnyType> right;

        public BinaryNode(AnyType element) {
            this.element = element;
        }

        public BinaryNode(AnyType element, BinaryNode<AnyType> left, BinaryNode<AnyType> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }
}