二叉搜索树（Binary Search Tree），（又：二叉查找树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

1、类结构定义

类的初始定义包含下面两个部分

1、BST 为 Binary Search Tree 三个单词的英文缩写，提供常用的对外接口和自己内部需要的工具方法
2、Node 为定义的节点类，提供基本的记录属性和工具方法
3、size 为存储的节点个数，方便外面读取
4、root 存储该树的根节点

public class BST<E> {

    private int size;
    private Node<E> root;

    public int size() {
        return size;
    }

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

    public void clear() {
        root = null;
        size = 0;
    }

    public void add(E e) {
        //待实现
    }

    public void remove(E e) {
        //待实现
    }

    public boolean contains(E e) {
        //待实现
        return false;
    }

    private static class Node<E> {
        E e;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

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

        /**
         * 是否是叶子节点
         */
        boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 是否拥有两个子节点
         */
        boolean hasTwoChildren() {
            return left != null && right != null;
        }

        /**
         * 是否是父节点的左子树
         */
        boolean isLeftChildren() {
            if (parent == null) { return false; }
            return this == parent.left;
        }

        /**
         * 是否是父节点的右子树
         */
        boolean isRightChildren() {
            if (parent == null) { return false; }
            return this == parent.right;
        }
    }
}

2、添加

二叉搜索树里面的元素都具有可比较性，所以如果想要实现添加、查找或删除，必须先要实现元素的可比较性逻辑，这个是前提。

2.1 元素比较方法（私有工具方法）

二叉搜索树里面存储的元素都是具有可比较性，但是不能强制要求调用者将存储元素类实现比较接口，所以这里设计了一个灵活的比较方案，调用者可以传入比较器（参考 JDK 提供的java.util.Comparator），或者让存储元素实现可比较接口（参考 JDK 官方提供的java.lang.Comparable）

1、首先申明一个comparator成员变量，用来记录传进来的比较器
2、重写构造方法，分别提供有参构造和无参构造两种方案
3、实现比较方法，申明为私有即可，主要是内部调用

private Comparator<E> comparator;

public BST() {
    this(null);
}

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

private int compare(E e1, E e2) {
    if (this.comparator != null) {
        return this.compare(e1, e2);
    } else {
        return ((Comparable<E>)e1).compareTo(e2);
    }
}

2.2 添加元素（对外方法）

二叉树的性质：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

1、如果树本来是空的，直接创建节点然后赋值给根节点
2、循环比较插入元素的大小，找到他的父节点（如果有相等的直接覆盖）
3、创建节点插入对应的位置

public void add(E e) {
    if (e == null) {
        throw new IllegalArgumentException("参数不能为空");
    }

    if (root == null) {
        size ++;
        root = new Node<>(e, null);
        return;
    }

    Node<E> parent = null;
    Node<E> node = root;
    int cmp = 0;

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

    size ++;
    Node<E> newNode = new Node<>(e, parent);
    if (cmp > 0) {
        parent.right = newNode;
    } else if (cmp < 0) {
        parent.left = newNode;
    }
}

3、判断是否包含

3.1 根据传入的元素，找到存储该值的节点（私有工具方法）

循环比较元素的大小，找到存储他的节点

private Node<E> node(E e) {
    Node<E> node = root;
    while (node != null) {
        int cmp = compare(e, node.e);
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        } else {
            break;
        }
    }
    return node;
}

3.2 判断是否包含某个元素（对外方法）

这个就比较简单了，直接调用上面提供的查找节点方法，看看是否能找到对应的节点

public boolean contains(E e) {
    return node(e) != null;
}

3、删除

3.1 找前驱节点（私有工具方法）

前驱节点的值小于该节点的值并且值最大的节点（中序遍历时，该节点的前一个节点）

对着下面的一个二叉搜索树案例进行分析

1、像2、4、5、8这样有左子树的节点，前驱节点一定在左子树中，顺着左子树往右找，所以他们的前驱节点应该是node.left.right.right...，终止条件就是right为null
2、像1、3、6、7、9这样的没有左子树的节点，但是父节点不为空，那么他们的前驱节点一定是顺着其父节点往上找，所以他们的前驱节点应该是node.parent.parent.parent...，终止条件就是node为parent的右子树
3、没有左子树，同时父节点又是空时没有前驱节点

private Node<E> predecessor(Node<E> node) {
    if (node == null) { return null; }

    if (node.left != null) {
        node = node.left;
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    while (node.parent != null && !node.isRightChildren()) {
        node = node.parent;
    }
    return node.parent;
}

3.2 找后继节点（私有工具方法）

后继节点的值大于该节点的值并且值最小的节点（中序遍历时，该节点的后一个节点）

还是对着图 1 进行分析

1、像2、5、6、8这样有右子树的节点，后继节点一定在右子树中，顺着右子树往左找，所以他们的后继及诶单应该是node.right.left.left...，终止条件是left为null
2、像1、3、4、7、9这样有没有右子树的节点，但其父节点不为空，那么他们的后继及节点一定是顺着其父节点往上找，所以他们的后继节点应该是node.parent.parent.parent...，终止条件就是node为parent的左子树
3、没有右子树，同时父节点又是空时没有后继节点

private Node<E> successor(Node<E> node) {
    if (node == null) { return null; }

    if (node.right != null) {
        node = node.right;
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    while (node.parent != null && !node.isLeftChildren()) {
        node = node.parent;
    }
    return node.parent;
}

3.3 删除元素（对外方法）

删除可以分为以下三种情况，接着对比该二叉搜索树

1、删除叶子节点（度为 0 的节点），直接删除即可，例如图中的1、3、7、9，删完结果如下

2、删除度为 1 的节点，找到其叶子节点，直接替换即可，例如图中的4、6，删完结果如下，4、6直接被3、7替代

3、删除度为 2 的节点，找到其前驱或后继节点，直接提换掉，然后再删除替换的前驱或后继节点（度为 2 的节点，其前驱或后继一定在左子树或右子树中，由上面的结论可以得出，度为 2 的前驱或后继节点的度要么是 0，要么是 1），例如图中2（前驱为1，后继为3）、5（前驱为4，后继为6）、8（前驱为7，后继为9），这里模拟删除2，这里会找到他的前驱节点1做替换，然后再删除原先的1所在的节点

public void remove(E e) {
    //找到对应的节点
    Node<E> node = node(e);

    if (node == null) {
        return;
    }

    size --;

    //度为2的节点
    if (node.hasTwoChildren()) {
        Node<E> pNode = predecessor(node);
        node.e = pNode.e;
        node = pNode;
    }

    //接下来要删除的节点要么度为1，要么度为0
    Node<E> replaceNode = node.left != null ? node.left : node.right;
    if (node.parent == null) {
        root = replaceNode;
    } else {
        if (node.isLeftChildren()) {
            node.parent.left = replaceNode;
        } else {
            node.parent.right = replaceNode;
        }
    }

    if (replaceNode != null) {
        //度为1的节点删除，不要忘记替换节点的parent变更
        replaceNode.parent = node.parent;
    }
}

4、遍历

根据根节点访问顺序的不同，二叉搜索树的遍历可以分为以下四种，前序遍历、中序遍历、后续遍历、层序遍历

遍历方法需要把值传出去，所以这里采用构建匿名内部类的方案，所以接下来可以声明一个抽象类，因为我们同时需要一个记录调用者是否停止遍历的属性，所以不能使用接口，而必须使用抽象类，代码如下

public static abstract class Visitor<E> {
    boolean stop;
    public abstract boolean visit(E e);
}

4.1 前序遍历（Preorder Traversal）

访问顺序：根节点 -> 左子树 -> 右子树

如下图，虚线便是访问顺序

前序遍历.png

public void preorderTraversal(Visitor<E> visitor) {
    if (visitor == null) { return; }
    preorderTraversal(root, visitor);
}
private void preorderTraversal(Node<E> node, Visitor<E> visitor) {
    if (node == null || visitor.stop) { return; }

    visitor.stop = visitor.visit(node.e);
    preorderTraversal(node.left, visitor);
    preorderTraversal(node.right, visitor);
}

4.2 中序遍历（Inorder Traversal）

访问顺序：左子树 -> 根节点 -> 右子树

中序遍历很重要，遍历出来的结果要么是升序，要么是降序（降序访问顺序：右子树 -> 根节点 -> 左子树）

如下图，虚线便是访问顺序

中序遍历.png

public void inorderTraversal(Visitor<E> visitor) {
    if (visitor == null) { return; }
    inorderTraversal(root, visitor);
}
private void inorderTraversal(Node<E> node, Visitor<E> visitor) {
    if (node == null || visitor.stop) { return; }

    inorderTraversal(node.left, visitor);
    if (visitor.stop) { return; }
    visitor.stop = visitor.visit(node.e);
    inorderTraversal(node.right, visitor);
}

4.3 后续遍历（Postorder Traversal）

访问顺序：左子树 -> 右子树 -> 跟节点

如下图，虚线便是访问顺序

后续遍历.png

public void postorderTraversal(Visitor<E> visitor) {
    if (visitor == null) { return; }
    postorderTraversal(root, visitor);
}
private void postorderTraversal(Node<E> node, Visitor<E> visitor) {
    if (node == null || visitor.stop) { return; }
    postorderTraversal(node.left, visitor);
    postorderTraversal(node.right, visitor);
    if (visitor.stop) { return; }
    visitor.stop = visitor.visit(node.e);
}

4.4 层序遍历（Level Order Traversal）

访问顺序：从上到下，从左到右一次访问每一个节点

层序遍历也很重要，只有层序遍历才是唯一能还原树的一种遍历，其他遍历都需要两两结合（前中、后中）。同时利用层序遍历还可以用来算树高、判断一棵树是否是完全二叉树等，这个后面有展示。

如下图，虚线便是访问顺序

层序遍历.png

实现思路：首先使用队列来装要遍历的节点（队列有先进先出的特性），首先将根节点放入队列（入队），再从队列中取出节点（出队）进行遍历访问，同时将访问元素的左右子节点入队。按此循环下去，一层层访问树的所有节点，直到队列为空（遍历完全部节点），退出循环。

队列这里就使用 JDK 系统自带的java.util.LinkedList

public void levelOrderTraversal(Visitor<E> visitor) {
    if (root == null || visitor == null) { return; }

    LinkedList<Node<E>> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();

        visitor.stop = visitor.visit(node.e);
        if (visitor.stop) { return; }

        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

5、树的其他一些重要操作

首先我们来区分几个概念：

真二叉树：所有节点的度数要么是 0，要么是 2，参考百度百科
满二叉树：真二叉树的基础上，加上度为 0 的节点（叶子节点都在最后一层），参考百度百科满二叉树
完全二叉树：叶子节点只会出现在最后两层，且最后一层的叶子节点都靠左对齐，也可以参考百度百科完全二叉树

5.1 获取树的高度

通过递归的方式

节点的高度就是左右子树中高最大的一个树的高度然后加一。先从叶子节点开始算起（高度为 1），一直递归到根节点。

public int heightForRecursive() {
    return height(root);
}

private int height(Node<E> node) {
    if (node == null) { return 0; }
    return Math.max(height(node.left), height(node.right)) + 1;
}

通过层序遍历的方式

利用层序遍历，每遍历完一层（队列里面的元素个数恰好是下一层元素个数）高度加一，这种方式省去了递归需要大量开辟堆栈的操作。

public int height() {
    if (root == null) { return 0; }

    int levelSize = 1;
    int height = 0;
    LinkedList<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();

        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }

        levelSize --;
        if (levelSize == 0) {
            levelSize = queue.size();
            height ++;
        }
    }
    return height;
}

5.2 判断一棵树是否是完全二叉树

实现思路：层序遍历，取出队列里面的节点进行判断

1、如果note.left != null && note.right != null，将note.left、node.right按顺序入队
2、如果note.left == null && note.right != null，返回false
3、如果note.left != null && note.right == null，将note.left入队，并且后面都是叶子节点，否则返回false
4、如果note.left == null && note.right == null，后面节点必须是叶子节点，否则返回false

public boolean isComplete() {
    if (root == null) { return false; }

    boolean leaf = false;
    LinkedList<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        if (leaf && !node.isLeaf()) {
            return false;
        }

        if (node.hasTwoChildren()) {
            queue.offer(node.left);
            queue.offer(node.right);
        } else if (node.left == null && node.right != null) {
            return false;
        } else  {
            if (node.left != null) {
                queue.offer(node.left);
            }
            leaf = true;
        }
    }
    return true;
}

上面的方式里面有很多重复判断，所以最下简单的优化（判断条件合并），具体优化代码如下

public boolean isComplete() {
    if (root == null) { return false; }

    boolean leaf = false;
    LinkedList<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        if (leaf && !node.isLeaf()) {
            return false;
        }

        if (node.left != null) {
            queue.offer(node.left);
        } else if (node.right != null) {
            return false;
        }

        if (node.right != null) {
            queue.offer(node.right);
        } else if (node.left != null) {
            leaf = true;
        }
    }
    return true;
}

5.3 二叉树的时间复杂度

复杂度表示可以参考百度百科算法复杂度

这里简单算下二叉搜索树的时间复杂度，按最坏的打算，要删除的元素在树的最后一层，要添加的元素也在树的最后一层，所以需要对比树的高度那么多次，所以现在树的高度就是删除或查找的复杂度。按最坏打算，我们假设该树是一个满二叉搜索树，一共有 n 个元素，高度为 h，那么他的第一层有 $2^0$ 个元素，第二层有 $2^1$ 个元素，第三层有 $2^2$ 个元素……第 h 层有 $2^{h-1}$ 个元素，可以看出他就是一个公比为 2，常数项为 1 的等比数列，所以得出元素总个数为

①：$n = 2^0 + 2^1 + 2^2 + … + 2^{h-1}$

根据等比数列求和公式 $S_n = \frac {a_1(1-q^n)}{1-q}$，可以得出 $n = 2^h - 1$

平时记不住公式也没关系，推导起来也很简单，将上面的公式 ① 左右乘一个公比（① * 2）得出

②：$2n = 2^1 + 2^2 + 2^3 + … + 2^h$

① - ② 得到 $n = 2^h - 1$ => $2^h = n + 1$ => $h = log_2n+1$

根据时间复杂度的表示规则，可以省略常数项，所以得出 $h = log_2n$

所以得出二叉搜索树的添加或删除的时间复杂度为 $O(log_2n)$

根据对数函数换底公式可知 $log_aN$ = $log_ab$ * $log_bN$，复杂度估算时省略常数项，得出 $log_aN$ 和 $log_bN$ 复杂度是一样的，所以凡是涉及到对数函数表示的复杂度，都可以统一称为 $logn$

所以得出二叉搜索树的添加或删除的时间复杂度为 $O(logn)$

参考资料：

数据结构代码实现二叉搜索树

代码实现二叉搜索树

1、类结构定义

2、添加

2.1 元素比较方法（私有工具方法）

2.2 添加元素（对外方法）

3、判断是否包含

3.1 根据传入的元素，找到存储该值的节点（私有工具方法）

3.2 判断是否包含某个元素（对外方法）

3、删除

3.1 找前驱节点（私有工具方法）

3.2 找后继节点（私有工具方法）

3.3 删除元素（对外方法）

4、遍历

4.1 前序遍历（Preorder Traversal）

4.2 中序遍历（Inorder Traversal）

4.3 后续遍历（Postorder Traversal）

4.4 层序遍历（Level Order Traversal）

5、树的其他一些重要操作

5.1 获取树的高度

通过递归的方式

通过层序遍历的方式

5.2 判断一棵树是否是完全二叉树

5.3 二叉树的时间复杂度