CS61B 课程笔记（Disc 10 Heaps, Traversals & Trees)

堆（Heaps）

1. 堆的乐趣

1.1 二叉最小堆操作

二叉最小堆是一种完全二叉树，根节点的值是最小的。以下操作展示了如何在插入和删除过程中保持堆的性质：

  1. 初始化：

    1
    Heap h = new Heap();
    • 堆（数组表示）初始化后为：[]

  2. 插入操作：

    • 插入5：
      • 堆：[5]
    • 插入7：
      • 堆：[5, 7]
    • 插入3：
      • 堆：[3, 7, 5]（3移动到根节点）
    • 插入1：
      • 堆：[1, 3, 5, 7]（1移动到根节点）
    • 插入2：
      • 堆：[1, 2, 5, 7, 3]（2作为1的子节点添加）

  3. 删除最小值操作：

    • 删除最小值（1）：
      • 删除后堆：[2, 3, 5, 7]
    • 删除最小值（2）：
      • 删除后堆：[3, 7, 5]

1.2 使用最小堆实现最大堆

你可以通过使用最小堆来实现最大堆，方法是对值进行取反：

  • 对于插入操作：
    • 取反整数并插入到最小堆中。
  • 对于删除最大值操作：
    • 调用最小堆的removeMin方法，并对返回值进行取反。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MaxHeap {
    private MinHeap minHeap;

    public MaxHeap() {
        minHeap = new MinHeap();
    }

    public void insert(int value) {
        minHeap.insert(-value);
    }

    public int removeMax() {
        return -minHeap.removeMin();
    }
}

树遍历

2. 二叉搜索树遍历

给定以下二叉搜索树：

1
2
3
4
5
6
7
    10
   /  \
  3    12
 / \   / \
1   7 11  14
            / \
           13 15

遍历类型：

  1. 前序遍历（根，左，右）：
    • 结果：10 3 1 7 12 11 14 13 15
  2. 中序遍历（左，根，右）：
    • 结果：1 3 7 10 11 12 13 14 15
  3. 后序遍历（左，右，根）：
    • 结果：1 7 3 11 13 15 14 12 10
  4. 层序遍历（广度优先搜索，BFS）：
    • 结果：10 3 12 1 7 11 14 13 15