数据结构与算法-2

非线性结构

六、哈希表（HashTable）

• 在计算机世界中，哈希表如同一位聪慧的图书管理员。他知道如何计算索书号，从而可以快速找到目标图书

6.1 哈希表

• 哈希表，又称散列表，它通过建立键key 与值value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键key ，则可以在𝑂(1) 时间内获取对应的值value 。
• 给定𝑛 个学生，每个学生都有“姓名”和“学号”两项数据。假如我们希望实现“输入一个学号，返回对应的姓名”的查询功能，则可以采用如图所示的哈希表来实现。

‧ 添加元素：仅需将元素添加至数组（链表）的尾部即可，使用𝑂(1) 时间。
‧ 查询元素：由于数组（链表）是乱序的，因此需要遍历其中的所有元素，使用𝑂(𝑛) 时间。
‧ 删除元素：需要先查询到元素，再从数组（链表）中删除，使用𝑂(𝑛) 时间。

​ 数组 链表 哈希表
查找元素 𝑂(𝑛) 𝑂(𝑛) 𝑂(1)
添加元素 𝑂(1) 𝑂(1) 𝑂(1)
删除元素 𝑂(𝑛) 𝑂(𝑛) 𝑂(1)

6.1.1 哈希表的常用操作

==Map<Integer, String> map = new HashMap<>();==：初始化

==.get(key)==：查询操作，得到值 value

==.put(key, value)==：添加键值对

==.remove(key)==：删除键值对

==size()== ：获取键值对的数量，O(1)

==containsKey(Object key)== ：判断是否包含指定的键，平均 O(1)，最坏 O(n)

==keySet()== ：获取==所有键的集合==，O(n)

==values()== ：获取==所有值的集合==，O(n)

/* 初始化哈希表 */
Map<Integer, String> map = new HashMap<>();

/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map.put(12836, "小哈");
map.put(15937, "小啰");
map.put(16750, "小算");
map.put(13276, "小法");
map.put(10583, "小鸭");

/* 查询操作 */
// 向哈希表中输入键 key ，得到值 value
String name = map.get(15937);

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.remove(10583);

哈希表有三种常用的遍历方式：遍历键值对、遍历键和遍历值。示例代码如下：

/* 遍历哈希表 */
// 遍历键值对 key->value
for (Map.Entry <Integer, String> kv: map.entrySet()) {
    System.out.println(kv.getKey() + " -> " + kv.getValue());
}
// 单独遍历键 key
for (int key: map.keySet()) {
    System.out.println(key);
}
// 单独遍历值 value
for (String val: map.values()) {
    System.out.println(val);
}

6.1.2 哈希表简单实现

• 键值对：每个抽屉都用来存放一对东西，分别是钥匙（键）和对应的物品（值）。比如在一个学生成绩管理系统里，学生的学号就是键，学生的成绩就是值。

• 哈希函数：这就像是一把神奇的 “定位魔法棒”。当你拿着一把钥匙（键）想要找对应的抽屉时，哈希函数会根据这把钥匙计算出一个数字，这个数字就代表抽屉的编号（在哈希表中的存储位置） 。

• 哈希冲突：有时候，不同的钥匙（键）经过哈希函数计算后，可能得到相同的抽屉编号，这种情况就叫哈希冲突。比如，有两个不同学号的同学，经过哈希函数计算后，都对应到了同一个 “抽屉” 位置。

• 哈希表的基本组成：
  用一个数组来实现哈希表，数组中的每个空位被称作桶（bucket） ，每个桶可以存储一个键值对。比如把哈希表想象成一排柜子，每个柜子就是一个桶，每个柜子里可以放一对东西，分别是钥匙（key）和对应的物品（value）。查询操作就是根据钥匙（key）找到对应的柜子（桶），从柜子里拿出物品（value）

• 哈希函数的作用：
  哈希函数的作用是把范围很大的所有可能的键（key），映射到一个相对较小的范围，也就是数组的索引（所有桶的位置）。简单来说，哈希函数就像一把特殊的 “钥匙”，能根据你给的普通钥匙（key），算出应该打开哪个柜子（对应数组中的哪个位置）。这样就能快速定位到存储某个键值对的地方。

• 哈希函数的计算过程：

  输入一个键（key）后，计算过程分两步：

1. 计算哈希值：通过某种哈希算法 hash() 对输入的 key 进行计算，得到一个哈希值。哈希算法有很多种，不同的算法计算规则不一样，但目的都是把 key 转化成一个数值。
2. 获取数组索引：得到哈希值后，用这个哈希值对桶的数量（也就是数组的长度 capacity）进行取模运算（%），得到的结果就是该 key 对应的数组索引 index。例如，如果 capacity 是 100，某个 key 通过哈希算法得到的哈希值是 123，那么 123 % 100 的结果是 23，这个 23 就是该 key 对应的数组索引

• 以下代码实现了一个简单哈希表。其中，我们将 key 和 value 封装成一个类 Pair ，以表示键值对。
• 使用数组作为底层存储结构。哈希表是一种用于存储==键值对==的数据结构，通过哈希函数将==键映射到数组的特定位置==，从而实现快速的插入、查询和删除操作。
• buckets.add(null);
  • 表示桶为空：在哈希表中，每个桶代表数组的一个位置，用来存储键值对。初始化时，所有桶都是空的，使用 null 来表示该位置还没有存储任何键值对。后续添加键值对时，若发现某个位置是 null，就知道可以直接将新的键值对存储在这个位置。
  • 方便后续操作：在进行查询、添加和删除操作时，通过检查桶是否为 null 可以快速判断该位置是否有键值对。

/* 键值对 */
class Pair {
    public int key;
    public String val;

    public Pair(int key, String val) {
        this.key = key;
        this.val = val;
    }
}

/* 基于数组实现的哈希表 */
class ArrayHashMap {
    private List<Pair> buckets;

    public ArrayHashMap() {
        // 初始化数组，包含 100 个桶
        buckets = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            buckets.add(null);
        }
    }

    /* 哈希函数 */
    private int hashFunc(int key) {
        int index = key % 100;
        return index;
    }

    /* 查询操作 */
    public String get(int key) {
        int index = hashFunc(key);
        Pair pair = buckets.get(index);
        if (pair == null)
            return null;
        return pair.val;
    }

    /* 添加操作 */
    public void put(int key, String val) {
        Pair pair = new Pair(key, val);
        int index = hashFunc(key);
        buckets.set(index, pair);
    }

    /* 删除操作 */
    public void remove(int key) {
        int index = hashFunc(key);
        // 置为 null ，代表删除
        buckets.set(index, null);
    }

    /* 获取所有键值对 */
    public List<Pair> pairSet() {
        List<Pair> pairSet = new ArrayList<>();
        for (Pair pair : buckets) {
            if (pair != null)
                pairSet.add(pair);
        }
        return pairSet;
    }

    /* 获取所有键 */
    public List<Integer> keySet() {
        List<Integer> keySet = new ArrayList<>();
        for (Pair pair : buckets) {
            if (pair != null)
                keySet.add(pair.key);
        }
        return keySet;
    }

    /* 获取所有值 */
    public List<String> valueSet() {
        List<String> valueSet = new ArrayList<>();
        for (Pair pair : buckets) {
            if (pair != null)
                valueSet.add(pair.val);
        }
        return valueSet;
    }

    /* 打印哈希表 */
    public void print() {
        for (Pair kv : pairSet()) {
            System.out.println(kv.key + " -> " + kv.val);
        }
    }
}

6.1.3 哈希冲突与扩容

• 哈希表容量 n 越大，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。因此，我们可以通过扩容哈希表来减少哈希冲突。

扩容前键值对 (136, A) 和 (236, D) 发生冲突，扩容后冲突消失。

类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时；并且由于哈希表容量 capacity 改变，我们需要通过哈希函数来重新计算所有键值对的存储位置，这进一步增加了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。

==负载因子（load factor）==是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为==哈希表扩容的触发条件==。例如在 Java 中，当负载因子超过 0.75 时，系统会将哈希表扩容至原先的 2 倍。

6.2 哈希冲突

哈希冲突会导致查询结果错误，严重影响哈希表的可用性。为了解决该问题，每当遇到哈希冲突时，我们就进行哈希表扩容，直至冲突消失为止。此方法简单粗暴且有效，但效率太低，因为哈希表扩容需要进行大量的数据搬运与哈希值计算。为了提升效率，我们可以采用以下策略。

1. 改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。
2. 仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。

哈希表的结构改良方法主要包括==“链式地址”==和==“开放寻址”==。

6.2.1 链式地址

在原始哈希表中，每个桶仅能存储一个键值对。链式地址（separate chaining）将单个元素转换为链表，将**==键值对==作为==链表节点==，将所有发生冲突的键值对都存储在同一链表中。

如图展示了一个链式地址哈希表的例子。

基于链式地址实现的哈希表的操作方法发生了以下变化。

• 查询元素：输入 key ，经过哈希函数得到桶索引，即可访问链表头节点，然后遍历链表并对比 key 以查找目标键值对。
• 添加元素：首先通过哈希函数访问链表头节点，然后将节点（键值对）添加到链表中。
• 删除元素：根据哈希函数的结果访问链表头部，接着遍历链表以查找目标节点并将其删除。

链式地址存在以下局限性。

• 占用空间增大：链表包含节点指针，它相比数组更加耗费内存空间。
• 查询效率降低：因为需要线性遍历链表来查找对应元素。

值得注意的是，当==链表很长时，查询效率 O(n) 很差==。此时可以将链表转换为“AVL 树”或“红黑树”，从而将查询操作的时间复杂度优化至 O(log⁡n) 。

6.2.2 开放寻址

开放寻址（open addressing）不引入额外的数据结构，而是通过“多次探测”来处理哈希冲突，探测方式主要包括线性探测、平方探测和多次哈希等。

开放寻址（线性探测、平方探测和多次哈希）哈希表都存在“不能直接删除元素”的问题。

6.2.2.1 线性探测

线性探测采用==固定步长的线性搜索==来进行探测，其操作方法与普通哈希表有所不同。

• 插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为 1 ），直至找到空桶，将元素插入其中。

• 查找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回 None 。

• 然而，线性探测容易产生“聚集现象”。具体来说，数组中连续被占用的位置越长，这些连续位置发生哈希冲突的可能性越大，从而进一步促使该位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化。

• 我们不能在开放寻址哈希表中直接删除元素。这是因为删除元素会在数组内产生一个空桶 None ，而当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，程序可能误判这些元素不存在。如图。

• 为了解决该问题，我们可以采用==懒删除（lazy deletion）机制==：它不直接从哈希表中移除元素，而是利用一个常量 TOMBSTONE 来标记这个桶。在该机制下，None 和 TOMBSTONE 都代表空桶，都可以放置键值对。但不同的是，线性探测到 TOMBSTONE 时应该继续遍历，因为其之下可能还存在键值对。

• 然而，懒删除可能会加速哈希表的性能退化。这是因为每次删除操作都会产生一个删除标记，随着 TOMBSTONE 的增加，搜索时间也会增加，因为线性探测可能需要跳过多个 TOMBSTONE 才能找到目标元素。

• 为此，考虑在线性探测中记录遇到的首个 TOMBSTONE 的索引，并将搜索到的目标元素与该 TOMBSTONE 交换位置。这样做的好处是当每次查询或添加元素时，元素会被移动至距离理想位置（探测起始点）更近的桶，从而优化查询效率。

6.2.2.2 平方探测

平方探测与线性探测类似，都是开放寻址的常见策略之一。当发生冲突时，平方探测不是简单地跳过一个固定的步数，而是跳过“探测次数的平方”的步数，即 1,4,9,… 步。

• 平方探测主要具有以下优势。
  • 平方探测通过跳过探测次数平方的距离，试图缓解线性探测的聚集效应。
  • 平方探测会跳过更大的距离来寻找空位置，有助于数据分布得更加均匀。
• 然而，平方探测并不是完美的。
  • 仍然存在聚集现象，即某些位置比其他位置更容易被占用。
  • 由于平方的增长，平方探测可能不会探测整个哈希表，这意味着即使哈希表中有空桶，平方探测也可能无法访问到它。

6.2.2.3 多次哈希

• 多次哈希方法使用多个哈希函数 f1(x)、f2(x)、f3(x)、… 进行探测。
  • 插入元素：若哈希函数 f1(x) 出现冲突，则尝试 f2(x) ，以此类推，直到找到空位后插入元素。
  • 查找元素：在相同的哈希函数顺序下进行查找，直到找到目标元素时返回；若遇到空位或已尝试所有哈希函数，说明哈希表中不存在该元素，则返回 None 。

与线性探测相比，多次哈希方法不易产生聚集，但多个哈希函数会带来额外的计算量。

6.2.3 哈希算法

• 哈希表的工作原理和哈希冲突的处理方法。然而无论是开放寻址还是链式地址，它们只能保证哈希表可以在发生冲突时正常工作，而无法减少哈希冲突的发生。
• 如果哈希冲突过于频繁，哈希表的性能则会急剧劣化。如图所示，对于链式地址哈希表，理想情况下键值对均匀分布在各个桶中，达到最佳查询效率；最差情况下所有键值对都存储到同一个桶中，时间复杂度退化至 O(n)

键值对的分布情况由哈希函数决定。index = hash(key) % capacity

当哈希表容量 capacity 固定时，哈希算法 hash() 决定了输出值，进而决定了键值对在哈希表中分布情况

这意味着，为了降低哈希冲突的发生概率，我们应当将注意力集中在哈希算法 hash() 的设计上。

• 在实际中，我们通常会用一些标准哈希算法，例如 MD5、SHA-1、SHA-2 和 SHA-3 等。它们可以将任意长度的输入数据映射到恒定长度的哈希值。

七、树（Tree）

参天大树充满生命力，根深叶茂，分枝扶疏。它为我们展现了数据分治的生动形态。

7.1 二叉树

二叉树（binary tree）是非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑

与链表类似，二叉树的基本单元是==节点==，每个节点包含==值==、==左子节点引用==和==右子节点引用==。

/* 二叉树节点类 */
class TreeNode {
    int val;         // 节点值
    TreeNode left;   // 左子节点引用
    TreeNode right;  // 右子节点引用
    TreeNode(int x) { val = x; }
}

每个节点都有两个引用（指针），分别指向左子节点（left-child node）和右子节点（right-child node），该节点被称为这两个子节点的父节点（parent node）。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的左子树（left subtree），同理可得右子树（right subtree）。

==在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树==。如左边图所示，如果将“节点 2”视为父节点，则其左子节点和右子节点分别是“节点 4”和“节点 5”，左子树是“节点 4 及其以下节点形成的树”，右子树是“节点 5 及其以下节点形成的树”。

7.1.1 二叉树常见术语

二叉树的常用术语如右边图所示。

• 根节点（root node）：位于二叉树顶层的节点，没有父节点。
• 叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None 。
• 边（edge）：连接两个节点的线段，即节点引用（指针）。
• 节点所在的层（level）：从顶至底递增，根节点所在层为 1 。
• ==节点的度==（degree）：==节点的子节点的数量==。在二叉树中，度的取值范围是 0、1、2 。
• 二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。
• 节点的深度（depth）：从根节点到该节点所经过的边的数量。
• 节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。

7.1.2 二叉树基本操作

1. 初始化二叉树

与链表类似，首先初始化节点，然后构建引用（指针）。

// 初始化节点
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
// 构建节点之间的引用（指针）
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

2. 插入与删除节点

与链表类似，在二叉树中插入与删除节点可以通过修改指针来实现。图 给出了一个示例。

TreeNode P = new TreeNode(0);
// 在 n1 -> n2 中间插入节点 P
n1.left = P;
P.left = n2;
// 删除节点 P
n1.left = n2;

7.1.3 常见二叉树类型

1. 完美二叉树

如图所示，完美二叉树（perfect binary tree）==所有层的节点都被完全填满==。在完美二叉树中，叶节点的度为 0 ，其余所有节点的度都为 2 ；==若树的高度为 h ，则节点总数为 $2^{h+1}−1$== ，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。

2. 完全二叉树

如图所示，完全二叉树（complete binary tree）只有最底层的节点未被填满，且最底层节点尽量靠左填充。请注意，完美二叉树也是一棵完全二叉树。

3. 完满二叉树

如图所示，完满二叉树（full binary tree）==除了叶节点之外，其余所有节点都有两个子节点==。

4. 平衡二叉树

如图所示，平衡二叉树（balanced binary tree）中==任意节点的左子树和右子树的高度之差的绝对值不超过 1== 。

7.1.4 二叉树的退化

图展示了二叉树的理想结构与退化结构。当二叉树的每层节点都被填满时，达到“完美二叉树”；而当所有节点都偏向一侧时，二叉树退化为“链表”。

• 完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。
• 链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至 O(n) 。

7.2 二叉树遍历

从物理结构的角度来看，树是一种基于链表的数据结构，因此其遍历方式是通过指针逐个访问节点。然而，树是一种非线性数据结构，这使得遍历树比遍历链表更加复杂，需要借助搜索算法来实现。

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。

7.2.1 层序遍历

层序遍历（level-order traversal）从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。

层序遍历本质上属于广度优先遍历（breadth-first traversal），也称**==广度优先搜索（breadth-first search, BFS）==**，它体现了一种“==一圈一圈向外扩展==”的逐层遍历方式。

广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。实现代码如下：

/* 层序遍历 */
List<Integer> levelOrder(TreeNode root) {
    // 初始化队列，加入根节点
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    // 初始化一个列表，用于保存遍历序列
    List<Integer> list = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // 队列出队
        list.add(node.val);           // 保存节点值
        if (node.left != null)
            queue.offer(node.left);   // 左子节点入队
        if (node.right != null)
            queue.offer(node.right);  // 右子节点入队
    }
    return list;
}

• 时间复杂度为 O(n) 。空间复杂度为 O(n) 。

7.2.2 前序、中序、后序遍历

相应地，前序、中序和后序遍历都属于深度优先遍历（depth-first traversal），也称==深度优先搜索（depth-first search, DFS）==，它体现了一种==“先走到尽头，再回溯继续”==的遍历方式。

图展示了对二叉树进行深度优先遍历的工作原理。深度优先遍历就像是绕着整棵二叉树的外围“走”一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历。

/* 前序遍历 */
void preOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    list.add(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

/* 中序遍历 */
void inOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root.left);
    list.add(root.val);
    inOrder(root.right);
}

/* 后序遍历 */
void postOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root.left);
    postOrder(root.right);
    list.add(root.val);
}

7.3 二叉树数组表示

在链表表示下，==二叉树的存储单元为节点 TreeNode== ，==节点之间通过指针相连接==。上一节介绍了链表表示下的二叉树的各项基本操作。

也可以==用数组来表示二叉树==。

7.3.1 表示完美二叉树

先分析一个简单案例。给定一棵完美二叉树，我们将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引。

根据层序遍历的特性，我们可以推导出父节点索引与子节点索引之间的“映射公式”：==若某节点的索引为 i ，则该节点的左子节点索引为 2i+1 ，右子节点索引为 2i+2== 。图 7-12 展示了各个节点索引之间的映射关系。

==映射公式的角色相当于链表中的节点引用（指针）==。给定数组中的任意一个节点，我们都可以通过映射公式来访问它的左（右）子节点。

7.3.2 表示任意二叉树

完美二叉树是一个特例，在二叉树的中间层通常存在许多 None 。由于层序遍历序列并不包含这些 None ，因此我们无法仅凭该序列来推测 None 的数量和分布位置。这意味着存在多种二叉树结构都符合该层序遍历序列。

如图 所示，给定一棵非完美二叉树，上述数组表示方法已经失效。

为了解决此问题，我们可以考虑在层序遍历序列中显式地写出所有 None 。如图所示，这样处理后，层序遍历序列就可以唯一表示二叉树了。示例代码如下：

/* 二叉树的数组表示 */
// 使用 int 的包装类 Integer ，就可以使用 null 来标记空位
Integer[] tree = { 1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15 };

完全二叉树非常适合使用数组来表示。回顾完全二叉树的定义，None 只出现在最底层且靠右的位置，因此所有 None 一定出现在层序遍历序列的末尾。

这意味着使用数组表示完全二叉树时，可以省略存储所有 None ，非常方便。

以下代码实现了一棵基于数组表示的二叉树，包括以下几种操作。

• 给定某节点，获取它的值、左（右）子节点、父节点。
• 获取前序遍历、中序遍历、后序遍历、层序遍历序列。

/* 数组表示下的二叉树类 */
class ArrayBinaryTree {
    private List<Integer> tree;

    /* 构造方法 */
    public ArrayBinaryTree(List<Integer> arr) {
        tree = new ArrayList<>(arr);
    }

    /* 列表容量 */
    public int size() {
        return tree.size();
    }

    /* 获取索引为 i 节点的值 */
    public Integer val(int i) {
        // 若索引越界，则返回 null ，代表空位
        if (i < 0 || i >= size())
            return null;
        return tree.get(i);
    }

    /* 获取索引为 i 节点的左子节点的索引 */
    public Integer left(int i) {
        return 2 * i + 1;
    }

    /* 获取索引为 i 节点的右子节点的索引 */
    public Integer right(int i) {
        return 2 * i + 2;
    }

    /* 获取索引为 i 节点的父节点的索引 */
    public Integer parent(int i) {
        return (i - 1) / 2;
    }

    /* 层序遍历 */
    public List<Integer> levelOrder() {
        List<Integer> res = new ArrayList<>();
        // 直接遍历数组
        for (int i = 0; i < size(); i++) {
            if (val(i) != null)
                res.add(val(i));
        }
        return res;
    }

    /* 深度优先遍历 */
    private void dfs(Integer i, String order, List<Integer> res) {
        // 若为空位，则返回
        if (val(i) == null)
            return;
        // 前序遍历
        if ("pre".equals(order))
            res.add(val(i));
        dfs(left(i), order, res);
        // 中序遍历
        if ("in".equals(order))
            res.add(val(i));
        dfs(right(i), order, res);
        // 后序遍历
        if ("post".equals(order))
            res.add(val(i));
    }

    /* 前序遍历 */
    public List<Integer> preOrder() {
        List<Integer> res = new ArrayList<>();
        dfs(0, "pre", res);
        return res;
    }

    /* 中序遍历 */
    public List<Integer> inOrder() {
        List<Integer> res = new ArrayList<>();
        dfs(0, "in", res);
        return res;
    }

    /* 后序遍历 */
    public List<Integer> postOrder() {
        List<Integer> res = new ArrayList<>();
        dfs(0, "post", res);
        return res;
    }
}

7.3.3 优点与局限性

二叉树的数组表示主要有以下优点。

• 数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快。
• 不需要存储指针，比较节省空间。
• 允许随机访问节点。

然而，数组表示也存在一些局限性。

• 数组存储需要连续内存空间，因此不适合存储数据量过大的树。
• 增删节点需要通过数组插入与删除操作实现，效率较低。
• 当二叉树中存在大量 None 时，数组中包含的节点数据比重较低，空间利用率较低。

7.4 二叉搜索树

如图所示，二叉搜索树（binary search tree）满足以下条件。

1. 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。
2. 任意节点的左、右子树也是二叉搜索树，即同样满足条件 1. 。

7.4.1 二叉搜索树的操作

我们将二叉搜索树封装为一个类 BinarySearchTree ，并声明一个成员变量 root ，指向树的根节点。

1. 查找节点

给定目标节点值 num ，可以根据二叉搜索树的性质来查找。如图 7-17 所示，我们声明一个节点 cur ，从二叉树的根节点 root 出发，循环比较节点值 cur.val 和 num 之间的大小关系。

• 若 cur.val < num ，说明目标节点在 cur 的右子树中，因此执行 cur = cur.right 。
• 若 cur.val > num ，说明目标节点在 cur 的左子树中，因此执行 cur = cur.left 。
• 若 cur.val = num ，说明找到目标节点，跳出循环并返回该节点。

二叉搜索树的查找操作与二分查找算法的工作原理一致，都是每轮排除一半情况。循环次数最多为二叉树的高度，当二叉树平衡时，使用 O(log⁡n) 时间。示例代码如下：

/* 查找节点 */
TreeNode search(int num) {
    TreeNode cur = root;
    // 循环查找，越过叶节点后跳出
    while (cur != null) {
        // 目标节点在 cur 的右子树中
        if (cur.val < num)
            cur = cur.right;
        // 目标节点在 cur 的左子树中
        else if (cur.val > num)
            cur = cur.left;
        // 找到目标节点，跳出循环
        else
            break;
    }
    // 返回目标节点
    return cur;
}

2. 插入节点

给定一个待插入元素 num ，为了保持二叉搜索树“左子树 < 根节点 < 右子树”的性质，插入操作流程如图所示

1. 查找插入位置：与查找操作相似，从根节点出发，根据当前节点值和 num 的大小关系循环向下搜索，直到越过叶节点（遍历至 None ）时跳出循环。
2. 在该位置插入节点：初始化节点 num ，将该节点置于 None 的位置。

在代码实现中，需要注意以下两点。

• 二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。
• 为了实现插入节点，我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 None 时，我们可以获取到其父节点，从而完成节点插入操作。

/* 插入节点 */
void insert(int num) {
    // 若树为空，则初始化根节点
    if (root == null) {
        root = new TreeNode(num);
        return;
    }
    TreeNode cur = root, pre = null;
    // 循环查找，越过叶节点后跳出
    while (cur != null) {
        // 找到重复节点，直接返回
        if (cur.val == num)
            return;
        pre = cur;
        // 插入位置在 cur 的右子树中
        if (cur.val < num)
            cur = cur.right;
        // 插入位置在 cur 的左子树中
        else
            cur = cur.left;
    }
    // 插入节点
    TreeNode node = new TreeNode(num);
    if (pre.val < num)
        pre.right = node;
    else
        pre.left = node;
}

与查找节点相同，插入节点使用 O(log⁡n) 时间。

3. 删除节点

先在二叉树中查找到目标节点，再将其删除。与插入节点类似，我们需要保证在删除操作完成后，二叉搜索树的“左子树 < 根节点 < 右子树”的性质仍然满足。因此，我们根据目标节点的子节点数量，分 0、1 和 2 三种情况，执行对应的删除节点操作。

如图所示，当待删除节点的度为 0 时，表示该节点是叶节点，可以直接删除。

如图 所示，当待删除节点的度为 1 时，将待删除节点替换为其子节点即可。

当待删除节点的度为 2 时，我们无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树“左子树 < 根节点 < 右子树”的性质，因此这个节点可以是右子树的最小节点或左子树的最大节点。

假设我们选择右子树的最小节点（中序遍历的下一个节点），则删除操作流程如图 7-21 所示。

1. 找到待删除节点在“中序遍历序列”中的下一个节点，记为 tmp 。
2. 用 tmp 的值覆盖待删除节点的值，并在树中递归删除节点 tmp 。

删除节点操作同样使用 O(log⁡n) 时间，其中查找待删除节点需要 O(log⁡n) 时间，获取中序遍历后继节点需要 O(log⁡n) 时间。示例代码如下：

/* 删除节点 */
void remove(int num) {
    // 若树为空，直接提前返回
    if (root == null)
        return;
    TreeNode cur = root, pre = null;
    // 循环查找，越过叶节点后跳出
    while (cur != null) {
        // 找到待删除节点，跳出循环
        if (cur.val == num)
            break;
        pre = cur;
        // 待删除节点在 cur 的右子树中
        if (cur.val < num)
            cur = cur.right;
        // 待删除节点在 cur 的左子树中
        else
            cur = cur.left;
    }
    // 若无待删除节点，则直接返回
    if (cur == null)
        return;
    // 子节点数量 = 0 or 1
    if (cur.left == null || cur.right == null) {
        // 当子节点数量 = 0 / 1 时， child = null / 该子节点
        TreeNode child = cur.left != null ? cur.left : cur.right;
        // 删除节点 cur
        if (cur != root) {
            if (pre.left == cur)
                pre.left = child;
            else
                pre.right = child;
        } else {
            // 若删除节点为根节点，则重新指定根节点
            root = child;
        }
    }
    // 子节点数量 = 2
    else {
        // 获取中序遍历中 cur 的下一个节点
        TreeNode tmp = cur.right;
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        // 递归删除节点 tmp
        remove(tmp.val);
        // 用 tmp 覆盖 cur
        cur.val = tmp.val;
    }
}

4. 中序遍历有序

如图所示，二叉树的中序遍历遵循“左 → 根 → 右”的遍历顺序，而二叉搜索树满足“左子节点 < 根节点 < 右子节点”的大小关系。

这意味着在二叉搜索树中进行中序遍历时，总是会优先遍历下一个最小节点，从而得出一个重要性质：二叉搜索树的中序遍历序列是升序的。

利用中序遍历升序的性质，在二叉搜索树中获取有序数据仅需 O(n) 时间，无须进行额外的排序操作，非常高效

7.4.2 二叉搜索树的效率

给定一组数据，我们考虑使用数组或二叉搜索树存储。观察表 7-2 ，二叉搜索树的各项操作的时间复杂度都是对数阶，具有稳定且高效的性能。只有在高频添加、低频查找删除数据的场景下，数组比二叉搜索树的效率更高。

在理想情况下，二叉搜索树是“平衡”的，这样就可以在 log⁡n 轮循环内查找任意节点。

然而，如果我们在二叉搜索树中不断地插入和删除节点，可能导致二叉树退化为图 7-23 所示的链表，这时各种操作的时间复杂度也会退化为 O(n) 。