封面画师：ツチヤ封面ID：79939619

本文参考视频：小马哥教育(SEEMYGO) 2019 年恋上数据结构与算法（第一季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化

由于本文涉及代码较多，已默认关闭代码块的展开。

0. 前言

前面学习的动态数组、链表、栈和队列都属于线性结构，从此刻开始，将学习树形结构。

树形结构是相当重要的，许多实际问题抽象出来的数据结构都是树形结构，其中，又以二叉树作为其代表。

鲁迅先生曾经说过：「 ~~我家门前有两棵树，一棵叫 AVL 树，一棵叫红黑树。~~ 」，足以见得二叉树其重要性。😂

依稀记得在学校学过二叉树的知识，但并没有使用编码实现过，如今既是复习，也是重新开始学习。

网址推荐

1. 二叉树

1.1 树

树（Tree），基本概念有：节点、根节点、父节点、子节点、兄弟节点。

树的结构图：

节点：每个圈圈就是一个节点
根节点：上图根节点就是指包含 1 的圈
父节点：节点 2、3、4、5、6 的父节点是节点 1
子节点：节点 1 的子节点有节点 2、3、4、5、6
兄弟节点：节点 2、3、4、5、6 互为兄弟节点（兄弟节点的父节点相同）

一棵树可以没有任何节点，称之为空树。（空数？空树）

一棵树可以只有一个节点，也就是只有根节点。

子树、左子树、右子树：一棵树中任意节点下的子节点及其后裔节点可以称之为一棵子树
节点的度（degree）：子树的个数。比如：根节点 1 的度为 5，节点 2 的度为 2，节点 6 的度为 1，节点 27 的度为 0
树的度：所有节点度中的最大值。很明显，上图给出的树的度为 5，因为节点最大的度是根节点 1 的度
叶子节点（leaf）：度为 0 的节点。比如：节点 4、22、66、77、88、24、25、26、27 都属于叶子节点
非叶子节点：度不为 0 的节点
层数（level）：根节点在第一层，根节点的子节点在第二层，以此列推（部分书籍资料可能从第 0 层开始计算）
节点的深度（deep）：从根节点到当前节点的唯一路径上的节点总数。比如：节点 2 的深度为 2，节点 24 的深度为 3
节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数。比如：节点 2 的高度为 3
树的深度：所有节点深度中的最大值。上图所示的树的深度为 4
树的高度：所有节点高度中的最大值。上图所示的树的高度为 4

一般来说， 树的深度等于树的高度 。

有序树：树中任意节点的子节点之间有顺序关系，学习中遇到的树基本都是有序树
无序树：树中任意节点的子节点之间没有顺序关系，也称为「自由树」
森林：由 $m$ （ $m \ge n$ ）棵互不相交的树组成的集合

1.2 二叉树

含义

二叉树（Binary Tree），相比于普通的树，二叉树有以下特点：

每个节点的度最大为 2（最多拥有 2 棵子树）
左子树和右子树是有顺序的，且要求严格。（左右子树交换，就是两棵不同的二叉树，因此 二叉树属于有序树 ）
即使某节点只有一课子树，也要区分左右子树

二叉树结构图：

特殊的二叉树「们」：

性质

非空二叉树的第 $i$ 层，最多有 $2^i-1$ 个节点，其中 $i \ge 1$
在高度为 $h$ 的二叉树上最多有 $2^h - 1$ 个节点，其中 $h \ge 1$
对于任何一棵非空二叉树，如果叶子节点个数为 $n_0$ $n_{0}$ ，度为 $2$ $2$ 的节点个数为 $n_2$ $n_{2}$ ，则有： $\textcolor{red}{n_0 = n_2 + 1}$ $n_{0} = n_{2} + 1$
- 假设度为 $1$ 的节点个数为 $n_1$ ，那么二叉树的节点总数为 $n = n_0 + n_1 + n_2$
- 二叉树的边数 $T = n_1 + 2 * n_2 = n - 1 = n_0 + n_1 + n_2 - 1$ 。（边数等于单个节点度之和；除根节点外，每个节点都有一条边）

1.3 真二叉树与满二叉树

真二叉树

真二叉树（Proper Binary Tree），所有节点的度要么为 0 要么为 2。

真二叉树与非真二叉树结构图：

满二叉树

满二叉树（Full Binary Tree），所有节点的度要么为 0，要么为 2，且所有的 叶子节点都在最后一层 。

满二叉树结构图：

在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多。

满二叉树是特殊的真二叉树，即：满二叉树一定是真二叉树，但是真二叉树不一定是满二叉树。

假设满二叉树的高度为 $h$ ，满足 $h \ge 1$ ，那么：

第 i 层的节点数量为： $2^{i-1}$
叶子节点数量为： $2^{h-1}$
总节点数量为： $2^h - 1$ ，那么 $h = log_2 (n + 1)$

1.4 完全二叉树

完全二叉树（Complete Binary Tree），叶子节点 只会出现 在最后两层 ，且 最后一层的叶子节点全部靠左对齐 。

完全二叉树结构图：

满二叉树还是一种特殊的完全二叉树，但完全二叉树不一定是一棵满二叉树。

完全二叉树从根节点至倒数第二层是一棵满二叉树。

1.5 完全二叉树的性质

度为 $1$ 的节点只有左子树
度为 $1$ 的节点要么是 $1$ 个，要么是 $0$ 个
同样节点数量的二叉树，完全二叉树的高度最小
假设完全二叉树的高度为 $h$ $h$ ，满足 $h \ge 1$ $h \geq 1$ ，那么：
- 至少有 $2^{h-1}$ 个节点（ $2^0 + 2^1 + 2^2 + ··· + 2^{h-2} + 1$ ）
- 最多有 $2^h - 1$ 个节点（ $2^0 + 2^1 + 2^2 + ... + 2^{h-1}$ ，满二叉树）
- 总节点数量为 $n$ ，那么 $2^{h-1} \le n \lt 2^h$ ，左右分别取对数： $h - 1 <= log_2 n < h$
$\textcolor{red}{假设完全二叉树的高度为 \ h，满足 \ h \ge 1，总节点数量为 \ n， h = floor( log_2 n ) + 1}$
一棵有 $n$ $n$ 个节点的完全二叉树， $n \gt 0$ $n > 0$ ，从上到下、从左到右对节点从 $0$ $0$ 开始进行编号，对任意第 $i$ $i$ 个节点：
- 如果 $i = 0$ ，它是根节点
- 如果 $i \gt 0$ ，它的 父节点 编号为 $floor((i - 1) / 2)$
- 如果 $2i + 1 \le n - 1$ ，它的左子节点编号为 $2i + 1$
- 如果 $2i + 1 \gt n - 1$ ，它无左子节点
- 如果 $2i + 2 \le n - 1$ ，它的右子节点编号为 $2i + 2$
- 如果 $2i + 2 \gt n - 1$ ，它无右子节点

floor （向下取整）：只取前面的整数，比如 $floor(4.6) = 4$

ceiling（向上取整）：如果小数不为 0，取前面的整数加 1，否则只取前面的整数，比如 $ceiling(4.6) = 5$ ， $ceiling(4.0) = 4$ 。

floor 和 ceiling 都是不管四舍五入原则的。

在平时代码编写中，int h = 5 / 2 可以得到 2，是 默认向下取整 的。

1.6 完全二叉树公式总结

假设总节点数量为 $n$ $n$ ，叶子节点个数为 $n_0$ $n_{0}$ ：
- 如果 $n$ 为偶数，那么 $n_0 = n / 2$
- 如果 $n$ 为奇数，那么 $n_0 = (n + 1) / 2$

根据以上的公式，可以将其整合在一起： $n_0 = floor((n + 1) / 2)$ 或者 $n_0 = ceiling(n / 2)$

在代码中，非整除预算会默认向下取整，因此只需要书写 n0 = (n + 1) / 2 或者 n0 = (n + 1) >> 1 即可。

推导出叶子节点个数后，同样可以推导出非叶子节点个数：

\begin{aligned} n - n_0 &= n_1 + n_2 \\ &= floor(n / 2) \\ &= ceiling((n - 1) / 2) \end{aligned}

1.7 国内外差异

在国外：

Full Binary Tree：完满二叉树，所有的非叶子节点的度都是 2，相当于前面说的「真二叉树」

Perfect Binary Tree：完美二叉树，所有非叶子节点的度都为 2，且所有的叶子节点都在最后一层，相当于前面说的「满二叉树」

Complete Binary Tree：完全二叉树，国内外一致

2. 二叉搜索树

图形化界面：BinaryTreeGraph

2.1 需求分析

现在需要在 n 个动态的整数数组中搜索某个整数（查询其是否存在）

假设使用动态数组存放元素，从第 0 个位置开始遍历搜索，那么平均时间复杂度为： $O(n)$

如果这个动态数组是有序的（正序或倒序），可以使用二分查找来搜索数，最坏时间复杂度为： $O(logn)$ ，但是添加、删除的平均时间复杂度还是 $O(n)$

似乎「鱼和熊掌不可兼得」？

并不是！这时，一个「天降猛男」 —— 「二叉搜索树」登场了 😎，二叉搜索树的添加、删除、搜索的最坏时间复杂度均可优化至： $O(logn)$

2.2 概念与接口

二叉搜索树（Binary Search Tree），又叫二叉查找树、二叉排序树，是二叉树的一种，是最广泛的一种二叉树，英文简称 BST 。

二叉搜索树结构图：

二叉搜索树的性质

二叉搜索树除了拥有二叉树的性质外，还有哪些特性呢？

任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树也是一棵二叉搜索树

二叉搜索树可以大大提高搜索数据的效率，同时 二叉搜索树存储的元素必须具备可比较性 ，比如：

比如 int、double 等
如果是自定义类型，需要指定比较方式
不允许为 null

二叉搜索树的接口设计

元素的数量： int size();

是否为空： boolean isEmpty();

清空所有元素： void clear();

添加元素： void add(E element);

删除元素： void remove(E element);

是否包含某个元素： boolean contains(E element);

需要注意的是，现在使用的二叉搜索树（二叉树）来说，它的元素是没有索引的概念的。

为什么？很简单，用不上！根据二叉搜索树的性质，插入元素位置是不确定的，无法确定插入元素位置，因此索引也就用不上了。

2.3 添加节点

静态嵌套类

在编写「添加节点」的代码之前，依然需要进行大量的准备工作。

首先，需要一个节点类 Node<E>，这个类用来表示 BST 中每个节点的信息。

节点中主要包含以下信息：

节点值：E element
当前节点的左右节点：Node<E> left 和 Node<E> right
父节点： Node<E> parent

节点值的需要是毋庸置疑的。操作 BST（比如：插入节点）时，需要确定是操作左节点还是右节点，因此左右节点也是需要的；遍历 BST 时，是从根节点开始遍历，根节点是 BST 中其他节点的「祖宗节点」，因此还需要确定某一节点的父节点，有了父节点才可以进行遍历操作。

综上，不难得出这个内部类为：

1234567891011// 一个节点就是一个Node
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;
    }
}

成员变量

基于静态嵌套类的创建，可以确定 BinarySearchTree 类中的成员变量。首先需要一个表示节点个数的 size，然后还需要整个树的根节点 root，有了 root 就可以对一棵 BST 进行更多操作，比如：遍历、编辑等。

在基于 size 成员变量确定的条件下，可以确定 int size(); 和 boolean isEmpty(); 的实现逻辑：

1234567891011121314public class BinarySearchTree<E> {
    private int size;   // 节点个数
    private Node<E> root; //根节点

    public int size(){
        return size;
    }

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

代码实现

由于二叉搜索树的性质：任意一个节点的值都大于其左子树所有节点的值，任意一个节点的值都小于其右子树所有节点的值，因此添加节点时一般需要判断插入节点与所遍历节点的大小关系。这句话不仅体现在需要判断大小，还要求二叉搜索树的节点值不能为 null，必须具有可比性。

先写一个判断 null 值的方法：

123456// 节点空值检查
private void elementNotNullCheck(E element){
    if (element == null){
        throw new IllegalArgumentException("element must not be null");
    }
}

还需要编写一个判断插入节点与当前遍历节点大小关系的方法：

12345678/**
* @return 返回值等于0，表示e1和e2相等；返回值大于0，表示e1大于e2；返回值小于0，表示e1小于e2
*/
private int compare(E e1, E e2){
    // 先不实现
    
    return 0;
}

接下来需要理一下添加节点的逻辑：

添加节点的第一步就是判断添加的节点是否为 null。

然后是明确插入节点时所包含的情况：包含的情况有两种，一是当前树为空树，需要插入一个根节点；二是当前树已有根节点，插入的节点是子节点。

当添加的节点是 根节点 时（即：root == null）：直接令 root 等于节点，然后 size 自增一，最后返回即可。

当添加的节点 不是根节点 时：

先确认插入节点位置的父节点：采取遍历并比较的方式。遍历需要一个循环，循环结束条件就是当前的节点为 null，因为插入的节点只能是原 BST 的叶子结点的子节点
确定好父节点后，根据前一步获取的比较方法的返回值，确定插入节点的位置（父节点的左节点还是右节点）

代码实现：

12345678910111213141516171819202122232425262728293031323334public void add(E element) {
    elementNotNullCheck(element);
    // 添加第一个节点 （根节点）
    if (root == null) {
        root = new Node<>(element, null);
        size++;
        return;
    }
    // 添加的不是第一个节点
    // 找到插入节点的父节点
    Node<E> parent = root;
    Node<E> node = 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 { // 相等
            node.element = element;	// 相等时覆盖
            return;
        }
    }
    // 看看插入到父节点的哪个位置
    Node<E> newNode = new Node<>(element,parent);
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    size++;
}

等值处理

当插入的值在原 BST 中已经存在时，进行的操作是：覆盖。所谓覆盖，就是使用新值覆盖旧值，但是又有一个问题，既然插入的值在原 BST 中已经存在了，还进行覆盖岂不是多此一举？

假设插入的是 Person 对象，该对象中有两个成员变量：age 和 name。定义的比较规则是按照 age 进行比较的，比如先插入 new Person("mofan",18)，再插入 new Person("默烦",18)，这两个对象是相等的。

如果不做任何处理，直接返回，那么 BST 中的数据还是 Person("mofan",18)，既然想做的是添加节点，就表明需要更新节点，要保证 BST 进行了更新，因此应该执行覆盖，使用 new Person("默烦",18) 覆盖 new Person("mofan",18)。

2.4 比较逻辑

在 2.3 添加节点 中已经编写好添加节点的逻辑，但并没实现节点大小的比较逻辑。

如果数据类型是 int、double，直接比较数值大小就可以了，但实际环境下可能不是基本数据类型，因此需要对不同的类型制定比较规则，也可以将规则的制定交给使用者。

设计一——可比较接口

创建可比较接口 Comparable，并在其中添加比较方法。然后让 BinarySearchTree 中的范型实现（继承）这个接口，同时要求添加到 BST 中的节点所对应的类也要实现这个接口。

123public interface Comparable<E> {
    int compareTo(E e);
}

123public class BinarySearchTree<E extends Comparable> {
    // --snip--
}

而 BinarySearchTree 中的 int compare(E e1, E e2); 方法可以这么书写：

123456/**
 * @return 返回值等于0，表示e1和e2相等；返回值大于0，表示e1大于e2；返回值小于0，表示e1小于e2
 */
private int compare(E e1, E e2){
    return e1.compareTo(e2);
}

当添加到 BST 中的对象是复杂对象时，要求该对象对应的类必须实现 Comparable 接口，重写 compareTo() 方法，自定义实体类比较方式，例如：

123456789101112public class Person implements Comparable<Person>{
    private int age;

    public Person(int age) {
        this.age = age;
    }

    @Override
    public int compareTo(Person person) {
        return age - person.age;
    }
}

比较方法主要逻辑是：年龄大的 Person 对象比年龄小的 Person 对象要大。（年龄大指的是 age 成员变量数值大，最后一个「要大」指的是在 BST 中，年龄大的 Person 放在右节点）

但是这样会带来一个问题，比如先创建了一棵 BST，插入节点的类型是 Person，根据定义的比较规则，年龄大的 Person 对象会放在右节点。然后又创建了一棵 BST，插入节点类型也是 Person，但此时想要将年龄小的 Person 对象放在右节点，也就是说，此时年龄小的 Person 对象比年龄大的 Person 对象要大。😕

由于已经在 Person 类中写死了比较方法，显然无法实现上述需求。 😟

可以编写一个比较器接口 Comparator，让用户自己编写比较器来实现比较器接口，从而达到高自定义比较方法。☺️

设计二——比较器

创建比较器接口 Comparator，添加比较器的比较方法：

1234// 比较器
public interface Comparator<E> {
    int compare(E e1, E e2);
}

在 BinarySearchTree 中定义比较器的成员变量，让 int compare(E e1, E e2); 方法可以使用比较器进行比较：

123456789101112131415161718public class BinarySearchTree<E> {
    private int size;   // 节点个数
    private Node<E> root; //根节点
    private Comparator<E> comparator;

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }
    
    /**
     * @return 返回值等于0，表示e1和e2相等；返回值大于0，表示e1大于e2；返回值小于0，表示e1小于e2
     */
    private int compare(E e1, E e2){
        return comparator.compare(e1,e2);
    }

    // --snip--
}

用户在使用 BinarySearchTree 时，需要创建一个比较器：

12345678910111213141516171819202122232425public class Main {

    public static class PersonComparator implements Comparator<Person>{
        @Override
        public int compare(Person e1, Person e2) {
            return e1.getAge() - e2.getAge();
        }
    }

    public static class PersonComparator2 implements Comparator<Person>{
        @Override
        public int compare(Person e1, Person e2) {
            return e2.getAge() - e1.getAge();
        }
    }

    public static void main(String[] args) {
        BinarySearchTree<Person> bst1 = new BinarySearchTree<>(new PersonComparator());
        bst1.add(new Person(12));
        bst1.add(new Person(15));
        BinarySearchTree<Person> bst2= new BinarySearchTree<>(new PersonComparator2());
        bst2.add(new Person(12));
        bst2.add(new Person(15));
    }
}

注意：因为 Person 类中成员变量 age 是私有的，外部无法直接访问，需要在 Person 类中添加 get/set 方法来获取 age。

使用比较器时，除了可以创建一个类来实现 Comparator 接口外，还可以直接使用匿名类：

1234567// Java中的匿名类，类似于iOS中的Block、JS中的闭包
BinarySearchTree<Person> binarySearchTree = new BinarySearchTree<>(new Comparator<Person>() {
    @Override
    public int compare(Person o1, Person o2) {
        return 0;
    }
});

但是！这样使用比较器的方法会强制让用户在使用 BinarySearchTree 时需要构建比较器，而且上述说的需求也不一定是每次都需要的，比较器的构建就变得不是必要的。😵

那么有没有什么方法可以让这两种情况结合一下呢？让用户需要构建比较器时可以构建，不需要构建时不被强制要求构建。👇

设计三——二者结合

将二者结合的总结目标就是：让用户需要构建比较器时可以构建，不需要构建时不被强制要求构建。但是还有一点必须满足，那就是插入的节点必须要具备可比较性，构建比较器后，就相当于给节点创造了比较性，如果不构建比较性就要要求节点自身拥有比较性。

要想将二者结合，需要再增加一个构造方法：

123public BinarySearchTree() {
    this(null);
}

有了这个构造方法，在创建 BinarySearchTree 对象时就可以不用构建比较器了。

但还需要考虑没有比较器时，强制用户使用的节点拥有比较性。

可以改写 int compare(E e1, E e2) 方法：

12345678910/**
 * @return 返回值等于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);
}

这样就将两者结合在一起了。当 想要创建比较器 时，可以传递创建的比较器至 BinarySearchTree 对象，然后节点的比较就会按照创建的比较器规则；如果 没有创建比较器，那么 强制要求节点拥有可比较性 ，即：实体类实现实现 Comparable 接口，重写 compareTo() 方法。

JDK 中也提供了可比较接口 Comparable 和比较器 Comparator，可以删除前文的自定义接口，使用 JDK 官方的接口。

Java 中内置的类型，比如：Integer、Double、String 等类都实现了 Comparable 接口，它们默认是可比较的，BinarySearchTree 的范型指定为内置数据类型时，无需创建比较器，直接使用就行。

1234public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence { ...... }

public final class Integer extends Number implements Comparable<Integer> { ...... }

PS：比较器 Comparator 位于 java.util 包中，使用时需要使用 import；可比较接口 Comparable 位于 java.lang 包中，实体类实现时无需使用 import （Java 语法）。

2.5 遍历二叉树

线性数据结构的遍历比较简单，只有正序遍历和逆序遍历，但二叉树就不一样了，根据 节点访问顺序 的不同，二叉树常见的遍历方式有 4 种：

前序遍历（Preorder Traversal）
中序遍历（Inorder Traversal）
后序遍历（Postorder Traversal）
层序遍历（Level Order Traversal）

注意：这里是遍历二叉树，只要是二叉树，都有这些遍历方式。

前序遍历

访问顺序：根节点、前序遍历左子树、前序遍历右子树

则有遍历顺序为： 7、4、2、1、3、5、9、8、11、10、12

123456789101112// 前序遍历
public void preorderTraversal(){
    // root 是二叉搜索树的根节点(一个成员变量)
    preorderTraversal(root);
}

private void preorderTraversal(Node<E> node){
    if (node == null) return;
    System.out.println(node.element);
    preorderTraversal(node.left);
    preorderTraversal(node.right);
}

中序遍历

访问顺序：中序遍历左子树、根节点、中序遍历右子树

则有遍历顺序为： 1、2、3、4、5、7、8、9、10、11、12

从上面的遍历顺序可以看出，如果对 二叉搜索树 使用中序遍历，得到的遍历结果是升序的；如果将访问顺序修改为：中序遍历右子树、根节点、中序遍历左子树，那么得到的遍历结果是降序的。

BST 的中序遍历结果是升序或者降序的。

1234567891011// 中序遍历
public void inorderTraversal(){
    // root 是二叉搜索树的根节点(一个成员变量)
    inorderTraversal(root);
}
private void inorderTraversal(Node<E> node){
    if (node == null) return;
    inorderTraversal(node.left);
    System.out.println(node.element);
    inorderTraversal(node.right);
}

后序遍历

访问顺序：后续遍历左子树、后序遍历右子树、根节点

则有遍历顺序为： 1、3、2、5、4、8、10、12、11、9、7

1234567891011// 后序遍历
public void postorderTraversal(){
    // root 是二叉搜索树的根节点(一个成员变量)
    postorderTraversal(root);
}
private void postorderTraversal(Node<E> node){
    if (node == null) return;
    postorderTraversal(node.left);
    postorderTraversal(node.right);
    System.out.println(node.element);
}

层序遍历（重点）

层序遍历所有内容要达到能够默写的程度！

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

则有遍历顺序为： 7、4、9、2、5、8、11、1、3、10、12 （不同的颜色区分不同的层次）

根据层序遍历的规则，不难发现无法简单地使用递归来实现。

可以借用队列来实现层序遍历：

将根节点入队
循环执行一下操作，知道队列为空
- 将队头节点 A 出队，进行访问
- 将 A 的左子节点入队
- 将 A 的右子节点入队

12345678910111213141516171819// 层序遍历
public void levelOrderTraversal() {
    if (root == null) return;
    Queue<Node<E>> queue = new LinkedList<>();
    // 根节点入队
    queue.offer(root);
    while (!queue.isEmpty()){
        // 头结点出队
        Node<E> node = queue.poll();
        System.out.println(node.element);

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

2.6 遍历接口

在上述遍历代码中，只是简单地将 BST 中的节点值打印出来，但如果用户在使用时，不想直接打印出 BST 中的节点值，而是有其他的操作（比如遍历打印出原 BST 中节点值加一后的结果），那么使用上述的方法是无法做到的（只能修改源码）。

虽然可以修改源码，但是需求变，源码也要跟着变，况且用户也有没修改源码的权限，因此需要提供一个接口，让用户可以自定义遍历方式。

在 BinarySearchTree 类中编写一个内部接口 Visitor<E>，这个接口中的方法就是用户可自定义的遍历方法：

123public interface Visitor<E> {
    void visit(E element);
}

然后需要对上述四种遍历方法的代码实现进行改写，将单纯的打印元素改写成用户可自定义的遍历方法：

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455// 前序
public void preorder(Visitor<E> visitor) {
    preorder(root, visitor);
}

private void preorder(Node<E> node, Visitor<E> visitor) {
    if (node == null || visitor == null) return;
    visitor.visit(node.element);
    preorder(node.left, visitor);
    preorder(node.right, visitor);
}

// 中序
public void inorder(Visitor<E> visitor) {
    inorder(root, visitor);
}

private void inorder(Node<E> node, Visitor<E> visitor) {
    if (node == null || visitor == null) return;
    inorder(node.left, visitor);
    visitor.visit(node.element);
    inorder(node.right, visitor);
}

// 后序
public void postorder(Visitor<E> visitor) {
    postorder(root, visitor);
}

private void postorder(Node<E> node, Visitor<E> visitor) {
    if (node == null || visitor == null) return;
    postorder(node.left, visitor);
    postorder(node.right, visitor);
    visitor.visit(node.element);
}

public void levelOrder(Visitor<E> visitor) {
    if (root == null || visitor == null) return;
    Queue<Node<E>> queue = new LinkedList<>();
    // 根节点入队
    queue.offer(root);
    while (!queue.isEmpty()) {
        // 头结点出队
        Node<E> node = queue.poll();
        // 访问逻辑
        visitor.visit(node.element);

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

测试方法：

123456789101112131415161718192021222324252627282930313233343536static void test3() {
    Integer[] data = new Integer[]{
        7, 4, 2, 1, 3, 5, 9, 8, 11, 10, 12
    };
    BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
    for (int i = 0; i < data.length; i++) {
        binarySearchTree.add(data[i]);
    }
    binarySearchTree.levelOrder(new BinarySearchTree.Visitor<Integer>() {
        @Override
        public void visit(Integer element) {
            System.out.print(element + "_ ");
        }
    });
    System.out.println("");
    binarySearchTree.preorder(new BinarySearchTree.Visitor<Integer>() {
        @Override
        public void visit(Integer element) {
            System.out.print(element + "_ ");
        }
    });
    System.out.println("");
    binarySearchTree.inorder(new BinarySearchTree.Visitor<Integer>() {
        @Override
        public void visit(Integer element) {
            System.out.print(element + "_ ");
        }
    });
    System.out.println("");
    binarySearchTree.postorder(new BinarySearchTree.Visitor<Integer>() {
        @Override
        public void visit(Integer element) {
            System.out.print(element + "_ ");
        }
    });
}

2.7 遍历增强

现在已经可以控制遍历的方式了，但是并不全，为什么怎么说？

如果二叉树有 1K+ 个节点，甚至更多，难道遍历的时候要将他们全都打印出来吗？

这时就会出现一个需求：希望可以控制遍历的节点数量，能够在一定条件下停止遍历。

可以将 Visitor 接口中的 visit(E element) 方法设置一个 boolean 类型的返回值，如果返回为 true 时，就让遍历终止，反之则一直遍历，直到返回值为 true 或将整个二叉树遍历完。

12345678910111213141516171819public void levelOrder(Visitor<E> visitor) {
    if (root == null || visitor == null) return;
    Queue<Node<E>> queue = new LinkedList<>();
    // 根节点入队
    queue.offer(root);
    while (!queue.isEmpty()) {
        // 头结点出队
        Node<E> node = queue.poll();
        // 访问逻辑 （已修改） 返回值为true，停止遍历
        if (visitor.visit(node.element)) return;

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

但又出现了一个问题，前序、中序、后序遍历都是递归，不好直接停止。

需要一个标志，这个标志可以用来控制遍历的停止。 首先想到的就是添加成员变量，但如果添加成员的话需要三个成员变量，因为前序、中序、后序三种遍历方式肯定是不能共用同一个的，而且还有一个问题，使用成员变量控制遍历的停止，在 多线程环境下会出问题，因此需要每次遍历都是一个新的标志。

1234567891011// 前序遍历
public void preorder(Visitor<E> visitor) {
    preorder(root, visitor);
}

private void preorder(Node<E> node, Visitor<E> visitor) {
    if (node == null || visitor == null) return;
    visitor.visit(node.element);
    preorder(node.left, visitor);
    preorder(node.right, visitor);
}

前序遍历是调用的 preorder(Visitor<E> visitor) 方法，在这个方法中又调用了一个方法 preorder(Node<E> node, Visitor<E> visitor)。这两个方法都有一个共同的参数 visitor。在使用方法进行遍历时也会传入这个参数，在遍历过程中这个参数会一直存在，而且针对同一棵树进行两次前序遍历，都需要重新传递参数 visitor，可以在 Visitor 接口中下文章。

首先想到的就是在 Visitor 接口中添加表示遍历终止标志的变量，但接口中不能定义变量。可以将接口改成抽象类，这样就可以保证方法能被重写的前提下还能有终止遍历标志了。

注意：此处所有代码都在同一个包内，因此该抽象类的抽象方法没写访问修饰符 public，其他类也可以访问。如果代码在不同的包，注意使用对应的访问修饰符，否则无法访问。

123456public static abstract class Visitor<E> {
    // 遍历终止标志 true：终止 false：全遍历
    boolean stop;
    // 如果返回true，表示停止遍历
    abstract boolean visit(E element);
}

PS：抽象类中的抽象方法（其前有 abstract 修饰）不能用 private、static、synchronized、native 访问修饰符修饰。参考链接：java中抽象类与接口中方法访问修饰符问题

将前序、中序、后序方法 进行最终的改写 ：

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647// 前序
public void preorder(Visitor<E> visitor) {
    if (visitor == null) return;
    preorder(root, visitor);
}

private void preorder(Node<E> node, Visitor<E> visitor) {
    // 判断停止递归 并且 也可以判断停止打印
    if (node == null || visitor.stop) return;
    visitor.stop = visitor.visit(node.element);
    preorder(node.left, visitor);
    preorder(node.right, visitor);
}

// 中序
public void inorder(Visitor<E> visitor) {
    if (visitor == null) return;
    inorder(root, visitor);
}

private void inorder(Node<E> node, Visitor<E> visitor) {
    // 判断停止递归
    if (node == null || visitor.stop) return;
    inorder(node.left, visitor);
    // 如果上一步执行完后，visitor恰好为true，应该也不打印
    // 判断停止打印
    if (visitor.stop) return;
    visitor.stop = visitor.visit(node.element);
    inorder(node.right, visitor);
}

// 后序
public void postorder(Visitor<E> visitor) {
    if (visitor == null) return;
    postorder(root, visitor);
}

private void postorder(Node<E> node, Visitor<E> visitor) {
    // 判断停止递归
    if (node == null || visitor.stop) return;
    postorder(node.left, visitor);
    postorder(node.right, visitor);
    // 如果上一步执行完后，visitor恰好为true，应该也不打印
    // 判断停止打印
    if (visitor.stop) return;
    visitor.stop = visitor.visit(node.element);
}

要点：分析方法中判断 visitor.stop 的次数以及位置。

测试方法（以层序和前序为例）：

12345678910111213141516171819202122232425static void test3() {
    Integer[] data = new Integer[]{
            7, 4, 2, 1, 3, 5, 9, 8, 11, 10, 12
    };
    BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
    for (int i = 0; i < data.length; i++) {
        binarySearchTree.add(data[i]);
    }
    binarySearchTree.levelOrder(new BinarySearchTree.Visitor<Integer>() {
        @Override
        public boolean visit(Integer element) {
            System.out.print(element + "_ ");
            return element == 8;    // 节点值为8时停止遍历
        }
    });
    System.out.println("");
    binarySearchTree.preorder(new BinarySearchTree.Visitor<Integer>() {
        @Override
        public boolean visit(Integer element) {
            System.out.print(element + "_ ");
            return element == 5;    // 节点值为8时停止遍历
        }
    });
    System.out.println("");
}

2.8 遍历应用

前序遍历：树状结构展示（注意左右子树的顺序）

中序遍历：BST 的中序遍历可以按升序或降序处理节点

后序遍历：适用于一些先子后父的操作。

层序遍历：计算二叉树的高度、判断一棵树是否为完全二叉树。

前序遍历的应用：树状结构展示

在 BinarySearchTree 中重写 toString() 方法：

123456789101112public String toString() {
    StringBuilder sb = new StringBuilder();
    toString(root, sb, "");
    return sb.toString();
}

private void toString(Node<E> node, StringBuilder sb, String prefix){
    if (node == null) return;
    sb.append(prefix).append(node.element).append("\n");
    toString(node.left,sb,prefix + "【L】--");
    toString(node.right,sb,prefix + "【R】--");
}

测试代码：

12345678910static void test4() {
    Integer[] data = new Integer[]{
        7, 4, 2, 1, 3, 5, 9, 8, 11, 10, 12
    };
    BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
    for (int i = 0; i < data.length; i++) {
        binarySearchTree.add(data[i]);
    }
    System.out.println(binarySearchTree);
}

层序遍历的应用：计算二叉树的高度

递归实现： 在 BinarySearchTree 中添加以下代码：

12345678910// 获取整棵树的高度
public int height(){
    return height(root);
}

// 获取某一节点的高度
private int height(Node<E> node){
    if (node == null) return 0;
    return 1 + Math.max(height(node.left),height(node.right));
}

迭代实现： 在 BinarySearchTree 中添加以下代码：

123456789101112131415161718192021222324252627public int height(){
    if (root == null) return 0;
    // 树的高度
    int height = 0;
    // 存储每一层的元素数量 根节点一定会访问
    int levelSize = 1;
    Queue<Node<E>> queue = new LinkedList<>();
    // 根节点入队
    queue.offer(root);
    while (!queue.isEmpty()) {
        // 头结点出队
        Node<E> node = queue.poll();
        levelSize--;
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
        // 意味着即将访问下一层
        if (levelSize ==0){
            levelSize = queue.size();
            height++;
        }
    }
    return height;
}

测试代码：

12345678910static void test4() {
    Integer[] data = new Integer[]{
        7, 4, 2, 5, 9, 8, 11
    };
    BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
    for (int i = 0; i < data.length; i++) {
        binarySearchTree.add(data[i]);
    }
    System.out.println(binarySearchTree.height());	// 3层
}

层序遍历的应用：完全二叉树的判断

如果树为空，返回 false
如果树不为空，开始层序遍历二叉树（使用队列）
- 如果当前节点的左右节点都不为空，则将它们按左右顺序入队
- 如果当前节点的左节点为空，但右节点不为空，返回 false
- 如果当前节点的左节点不为空，但右节点为空或者左右节点都为空
  - 那么后边遍历的节点都应该为叶子节点，才是完全二叉树
  - 否则返回 false

为了便于判断，可以对 BinarySearchTree 中的静态嵌套类 Node<E> 添加一些方法：

1234567891011121314151617181920// 一个节点就是一个Node
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 boolean isLeaf() {
        return left == null && right == null;
    }

    public boolean hasTwoChildren() {
        return left != null && right != null;
    }
}

然后在 BinarySearchTree 中添加以下代码：

123456789101112131415161718192021222324public boolean isComplete() {
    if (root == null) return false;
    Queue<Node<E>> queue = new LinkedList<>();
    // 根节点入队
    queue.offer(root);
    boolean leaf = false;
    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 { // 后面遍历的节点都是
            leaf = true;
            if (node.left!=null){
                queue.offer(node.left);
            }
        }
    }
    return true;
}

测试代码：

12345678910static void test5() {
    Integer[] data = new Integer[]{
        7, 4, 9, 2, 1
    };
    BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
    for (int i = 0; i < data.length; i++) {
        binarySearchTree.add(data[i]);
    }
    System.out.println(binarySearchTree.isComplete()); // false
}

isComplete() 的升级版，可以减少重复判断：

123456789101112131415161718192021222324public boolean isComplete() {
    if (root == null) return false;
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    boolean leaf = false;
    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) {
            // node.left == null && node.right != null
            return false;
        }

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

2.9 重构二叉树

可以根据遍历结果来重构二叉树，以下结果可以保证重构出 唯一的一棵二叉树 ：

前序遍历 + 中序遍历
后序遍历 + 中序遍历

如果给的是前序遍历 + 后序遍历的结果：

如果它是一棵真二叉树（Proper Binary Tree），结果是唯一的
不然结果不唯一，因为左子树或右子树可能为空

重构方式

确定整棵树的根节点
确定左子树或右子树的父节点
根据遍历方式完成重构

2.1 0 前驱结点

前驱结点（Predecessor）：中序遍历时的前一个节点。

现有一二叉树，并给出其中序遍历结果：

因此，根节点 8 的前驱结点为节点 7。

设计思路

如果是 BST，某一节点的前驱结点就是前一个比它小的节点。针对一般情况：

当选中节点的左子树不为空（node.left != null）时（上述二叉树中的 6、13、8）：

predecessor = node.left.right.right.right.right…
终止条件是： right 为 null

当选中节点的左子树为空，但其父节点不为空（node.left == null && node.parent != null）时（上述二叉树中的 7、11、9、1）：

predecessor = node.parent.parent.parent…
终止条件： node 在 parent 的右子树中

当选中节点的左子树和父节点都为空（node.left == null && node.parent == null）时：

选中节点无前驱节点

代码实现

123456789101112131415161718private Node<E> predecessor(Node<E> node) {
    if (node == null) return null;
    // 前驱节点在左子树中
    Node<E> p = node.left;
    if (p != null) {
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }
    // 从“祖宗节点”中寻找前驱节点
    while (node.parent != null && node == node.parent.left) {
        node = node.parent;
    }

    // node.parent == null || node == node.parent.right
    return node.parent;
}

2.1 1 后继节点

后继结点（Successor）：中序遍历时的后一个节点。

现有一二叉树，并给出其中序遍历结果：

因此，根节点 4 的后继节点为节点 5。

设计思路

如果是 BST，某一节点的后继结点就是后一个比它大的节点。针对一般情况：

当选中节点的右节点不为空（node.right != null）时（上述二叉树中的 1、8、4）：

successor = node.right.left.left.left…
终止条件是： left 为 null

当选中节点的右节点为空，但其父节点不为空（node.right == null && node.parent != null）时（上述二叉树中的 7、6、3、11）：

successor = node.parent.parent.parent…
终止条件是： node 在 parent 的左子树中

当选中节点的右节点和父节点都为空（node.right == null && node.parent == null）时（上述二叉树中没有右子树的根节点）：

选中节点无后继节点

代码实现

寻找后继节点的代码和寻找前驱节点代码是对称的。

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

    Node<E> p = node.right;
    if (p != null) {
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }

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

    return node.parent;
}

2.1 2 节点删除

删除度为 0 的节点

方法： 直接删除即可！

假设 node 表示需要被删除的叶子节点：

如果 node == node.parent.left（删除的节点是其父节点的左节点）：
- 直接 node.parent.left = null 即可
如果 node == node.parent.right（删除的节点是其父节点的右节点）：
- 直接 node.parent.right = null 即可
如果 node.parent == null（删除的节点是当前二叉树的根节点，且树只有一个节点）：
- 直接 root == null 即可

删除度为 1 的节点

方法： 用子节点替代原节点的位置。

在上图中，就相当于要删除节点 4 或节点 9。

假设 node 表示需要被删除的 度为1 的节点，child 表示删除节点的左子节点或右子节点，那么使用 child 代替 node 的位置即可。

如果 node 是其父节点的左子节点：
- child.parent = node.parent 维护 child 的父节点
- node.parent.left = child 删除 node 节点
如果 node 是其父节点的右子节点：
- child.parent = node.parent 维护 child 的父节点
- node.parent.right = child 删除 node 节点
如果 node 是根节点：
- root = child 删除根节点
- child.parent = null 设置当前根节点的父节点为 null

删除度为 2 的节点

假设先删除节点 5、再删除节点 4：

如果直接删除节点 5，会破坏 BST 的结构，需要保证在删除节点后不会破坏 BST 的结构，还要满足 BST 的性质。

通过前面前驱节点和后继节点的说明，不难想到使用前驱节点或后继节点来代替被删除的度为 2 的节点：

先用前驱节点或后继节点的值覆盖需要被删除节点的值
然后删除相应的前驱结点或后继节点

删除节点 5 后 BST 的结构：

删除节点 4 时，可以使用相同的方法。

通过上面的删除操作，不难发现：

如果一个节点的度为 2，那么它的前驱、后继节点的度只可能是 1 或 0。

删除度为 2 的节点时，真正被销毁内存的节点并不是这个节点，而是它的前驱或后继节点。

代码实现

由于提供的接口是根据元素来删除的，而不是根据节点，但是前面的分析是根据节点删除，因此需要编写一个根据节点删除的方法（同时还需要一个根据元素查找节点的方法）：

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354// 删除某一元素
public void remove(E element) {
    remove(node(element));
}
// 删除某一节点
private void remove(Node<E> node) {
    if (node == null) return;
    size--;
    if (node.hasTwoChildren()) { // 度为2的节点
        // 找到后继节点
        Node<E> s = successor(node);
        // 用后继节点的值覆盖被删除节点的值
        node.element = s.element;
        // 变量node指向其后继节点，等待后续删除
        node = s;
    }
    // 删除node节点（node的度必然为1或0）
    Node<E> replacement = node.left != null ? node.left : node.right;
    if (replacement != null) {   // node度为1
        // 更改parent
        replacement.parent = node.parent;
        // 更改noded的parent的left、right的指向
        if (node.parent == null) { // node度为1，且为根节点
            root = replacement;
        } else if (node == node.parent.left) {
            node.parent.left = replacement;
        } else { // node == node.parent.right
            node.parent.right = replacement;
        }
    } else if (node.parent == null) {     // node度为0，是叶子节点，并且是根节点
        root = null;
    } else { // node是叶子节点，但不是根节点
        if (node == node.parent.left) {
            node.parent.left = null;
        } else {
            node.parent.right = null;
        }
    }
}

// 根据元素找寻节点
private Node<E> node(E element) {
    Node<E> node = root;
    while (node != null) {
        int cmp = compare(element, node.element);
        if (cmp == 0) return node;
        if (cmp > 0) {
            node = node.right;
        } else { // cmp < 0
            node = node.left;
        }
    }
    return null;
}

完善接口

还剩 clear() 和 contains(E element) 未实现，简单完成下：

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

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

数据结构之二叉搜索树

文章目录

0. 前言

1. 二叉树

1.1 树

1.2 二叉树

1.3 真二叉树与满二叉树

1.4 完全二叉树

1.5 完全二叉树的性质

1.6 完全二叉树公式总结

1.7 国内外差异

2. 二叉搜索树

2.1 需求分析

2.2 概念与接口

2.3 添加节点

2.4 比较逻辑

2.5 遍历二叉树

2.6 遍历接口

2.7 遍历增强

2.8 遍历应用

2.9 重构二叉树

2.1 0 前驱结点

2.1 1 后继节点

2.1 2 节点删除