一、二叉搜索树

• 任意一个节点的值都大于其左子树所有节点的值
• 任意一个节点的值都小于其右子树所有节点的值
• BST 存储的元素必须具备可比较性（如 int、double 等）
• BST 存储自定义类型，需要指定比较方式
• BST 存储的元素不能为 null

左边的都比我小，右边的都比我大。

二、BST 接口设计

public class BinarySearchTree<E> {

    public int size() {
        return 0;
    }

    public boolean isEmpty() {
        return true;
    }

    public void clear() {

    }

    public void add(E element) {

    }

    public void remove(E element) {

    }

    public boolean contains(E element) {
        return true;
    }

}

• BST 的元素没有索引的概念

三、实现（add）

• 二叉搜索树（BinarySearchTree）中会维护一个节点类
• BST 内部会维护根节点

public class BinarySearchTree<E> {  

    /**
     * 二叉搜索树的节点类
     */
    private static class Node<E> {
        // 节点上存储的元素
        E element;
        // 左子节点
        Node<E> left;
        // 右子节点
        Node<E> right;
        // 父节点
        Node<E> parent;

        /**
         * 节点类构造方法
         *
         * @param element 节点上存储的元素
         * @param parent  每个节点（除根节点）都有父节点, 不是每个节点都有子节点
         */
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }

}

• 元素非空检测

    /**
     * 元素非空检测
     */
    private void elementNotNullCheck(E element) {
        if (element == null)
            throw new IllegalArgumentException("Element must not be null!");
    }

添加节点步骤（☆☆☆☆☆）

• 找到父节点（parent）
• 创建新节点（node）
• parent.left = node 或 parent.right = node
• 遇到值相等？新值覆盖旧值

## 添加进 BST 里面的元素必须具有可比较性
### (1) BST 限制泛型必须具有可比较性
BinarySearchTree 限制，能够放进 BinarySearchTree 泛型的元素必须实现 Comparable 接口。Comparable 接口中要求实现它的类必须实现 compareTo 方法，进而提供比较逻辑。

public class BinarySearchTree<E extends Comparable<E>> {
    // 记录二叉搜索树的元素个数
    private int size;
    private Node<E> root; // 根节点

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {

    }

    public void add(E element) {
        elementNotNullCheck(element);

        // BST 中存储的第一个节点（根节点）
        if (size == 0 && root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }

        // 假设 node 是父节点
        Node<E> node = root;
        Node<E> parent = root;
        int cmp = 0;

        while (node != null) {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                return;
            }
        }

        // 创建新节点
        Node<E> newNode = new Node<>(element, parent);

        if (cmp > 0) {
            parent.right = newNode;
        } else if (cmp < 0) {
            parent.left = newNode;
        }
        size++;

    }

    public void remove(E element) {

    }

    public boolean contains(E element) {
        return true;
    }

    /**
     * 比较大小
     * 返回值为0：e1 等于 e2
     * 返回值【大于0】：e1 大于 e2
     * 返回值【小于0】：e1 小于 e2
     */
    private int compare(E e1, E e2) {
        return e1.compareTo(e2);
    }

    /**
     * 元素非空检测
     */
    private void elementNotNullCheck(E element) {
        if (element == null)
            throw new IllegalArgumentException("Element must not be null.");
    }

    /**
     * 二叉搜索树的节点类
     */
    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }

}

/**
 * 实现该接口的类型具有可比较性
 */
public interface Comparable<E> {

    int compareTo(E e);

}

public class Student implements Comparable<Student> {
    private int score;

    public int getScore() {
        return score;
    }

    public Student(int score) {
        this.score = score;
    }

    @Override
    public int compareTo(Student student) {
        return score - student.getScore();
    }
}

public class Main {

    public static void main(String[] args) {

        BinarySearchTree<Student> bst = new BinarySearchTree<>();
        bst.add(new Student(100));
        bst.add(new Student(66));
        bst.add(new Student(78));

    }

}

Student 类的比较逻辑写死了

(2) 传比较器给 BST

public class BinarySearchTree<E> {
    // 记录二叉搜索树的元素个数
    private int size;
    private Node<E> root; // 根节点

    private Comparator<E> comparator;

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {

    }

    public void add(E element) {
        elementNotNullCheck(element);

        // BST 中存储的第一个节点（根节点）
        if (size == 0 && root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }

        // 假设 node 是父节点
        Node<E> node = root;
        Node<E> parent = root;
        int cmp = 0;

        while (node != null) {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                return;
            }
        }

        // 创建新节点
        Node<E> newNode = new Node<>(element, parent);

        if (cmp > 0) {
            parent.right = newNode;
        } else if (cmp < 0) {
            parent.left = newNode;
        }
        size++;

    }

    public void remove(E element) {

    }

    public boolean contains(E element) {
        return true;
    }

    /**
     * 比较大小
     * 返回值为0：e1 等于 e2
     * 返回值【大于0】：e1 大于 e2
     * 返回值【小于0】：e1 小于 e2
     */
    private int compare(E e1, E e2) {
        return comparator.compare(e1, e2);
    }

    /**
     * 元素非空检测
     */
    private void elementNotNullCheck(E element) {
        if (element == null)
            throw new IllegalArgumentException("Element must not be null.");
    }

    /**
     * 二叉搜索树的节点类
     */
    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }

}

/**
 * 该接口提供比较的功能（比较器）
 * 实现该接口提供比较逻辑
 */
public interface Comparator<E> {

    int compare(E e1, E e2);

}

public class Student {
    private int score;

    public int getScore() {
        return score;
    }

    public Student(int score) {
        this.score = score;
    }

}

public class Main2 {

    private static class StudentComparator1 implements Comparator<Student> {
        @Override
        public int compare(Student e1, Student e2) {
            return e1.getScore() - e2.getScore();
        }
    }

    private static class StudentComparator2 implements Comparator<Student> {
        @Override
        public int compare(Student e1, Student e2) {
            return e2.getScore() - e1.getScore();
        }
    }

    public static void main(String[] args) {
        BinarySearchTree<Student> bst1 = new BinarySearchTree<>(new StudentComparator1());
        BinarySearchTree<Student> bst2 = new BinarySearchTree<>(new StudentComparator2());

    }

}

强制限制 BST 必须提供比较器了

(3) 结合 (1) 和 (2)

public class BinarySearchTree3<E> {
    // 记录二叉搜索树的元素个数
    private int size;
    private Node<E> root; // 根节点

    private Comparator<E> comparator;

    public BinarySearchTree3(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public BinarySearchTree3() {
        this.comparator = null;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {

    }

    public void add(E element) {
        elementNotNullCheck(element);

        // BST 中存储的第一个节点（根节点）
        if (size == 0 && root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }

        // 假设 node 是父节点
        Node<E> node = root;
        Node<E> parent = root;
        int cmp = 0;

        while (node != null) {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                return;
            }
        }

        // 创建新节点
        Node<E> newNode = new Node<>(element, parent);

        if (cmp > 0) {
            parent.right = newNode;
        } else if (cmp < 0) {
            parent.left = newNode;
        }
        size++;

    }

    public void remove(E element) {

    }

    public boolean contains(E element) {
        return true;
    }

    /**
     * 比较大小
     * 返回值为0：e1 等于 e2
     * 返回值【大于0】：e1 大于 e2
     * 返回值【小于0】：e1 小于 e2
     */
    private int compare(E e1, E e2) {
        if (comparator != null) return comparator.compare(e1, e2);
        return ((Comparable<E>)e1).compareTo(e2);
    }

    /**
     * 元素非空检测
     */
    private void elementNotNullCheck(E element) {
        if (element == null)
            throw new IllegalArgumentException("Element must not be null.");
    }

    /**
     * 二叉搜索树的节点类
     */
    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }

} 

/**
 * 实现该接口的类型具有可比较性
 */
public interface Comparable<E> {

    int compareTo(E e);

}

/**
 * 该接口提供比较的功能（比较器）
 * 实现该接口提供比较逻辑
 */
public interface Comparator<E> {

    int compare(E e1, E e2);

}

public class Student {
    private int score;

    public int getScore() {
        return score;
    }

    public Student(int score) {
        this.score = score;
    }

}

public class Main3 {

    private static class StudentComparator1 implements Comparator<Student> {
        @Override
        public int compare(Student e1, Student e2) {
            return e1.getScore() - e2.getScore();
        }
    }

    private static class StudentComparator2 implements Comparator<Student> {
        @Override
        public int compare(Student e1, Student e2) {
            return e2.getScore() - e1.getScore();
        }
    }

    public static void main(String[] args) {
        BinarySearchTree3<Student> bst1 = new BinarySearchTree3<>(new StudentComparator1());
        BinarySearchTree3<Student> bst2 = new BinarySearchTree3<>(new StudentComparator2());
        BinarySearchTree3<Student> bst3 = new BinarySearchTree3<>();

    }

}

Comparable 和 Comparator 在 jdk 的 util 包中都有的

匿名内部类和 Lambda 表达式：

public class Main4 {

    /**
     * 可通过匿名内部类简化
     */
    private static class StudentComparator1 implements Comparator<Student> {
        @Override
        public int compare(Student e1, Student e2) {
            return e1.getScore() - e2.getScore();
        }
    }

    /**
     * 可通过匿名内部类简化
     */
    private static class StudentComparator2 implements Comparator<Student> {
        @Override
        public int compare(Student e1, Student e2) {
            return e2.getScore() - e1.getScore();
        }
    }

    public static void main(String[] args) {
        BinarySearchTree4<Student> bst1 = new BinarySearchTree4<>(new StudentComparator1());
        BinarySearchTree4<Student> bst2 = new BinarySearchTree4<>(new StudentComparator2());
        BinarySearchTree4<Student> bst3 = new BinarySearchTree4<>();

        // 匿名内部类
        BinarySearchTree4<Student> bst4 = new BinarySearchTree4<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getScore() - o2.getScore();
            }
        });

        // Lambda 表达式
        BinarySearchTree4<Student> bst5 = new BinarySearchTree4<>((o1, o2) -> o2.getScore() - o1.getScore());
    }

}

四、二叉树网址和打印器的使用

https://520it.com/binarytrees/
① BinarySearchTree 实现 BinaryTreeInfo 接口
② 实现四个方法

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        return ((Node<E>) node).element;
    }

③ BinaryTrees.pringln(bst) 打印