5.1 树的基本概念

• 结点的度：该结点的子树数。
• 叶子结点：度为 0 的结点。
• 树的度：树中结点度的最大值。
• 结点的层次：根为第 1 层，依次向下。
• 树的高度：树的最大层次数。
• 森林：m 棵互不相交的树的集合。

5.2 树的存储结构

1. 双亲表示法

每个结点存储一个指向其双亲的指针（或下标）。适合从孩子找双亲的场景，但找孩子需遍历。

2. 孩子表示法

每个结点存储指向其所有孩子的指针链表。适合从双亲找孩子。

3. 孩子双亲表示法

结合以上两种，同时存储孩子链表和双亲指针。

4. 二叉链表表示法

每个结点含两个指针：firstchild（第一个孩子）和 nextsibling（下一个兄弟）。这种表示法自然地将树转换为二叉树。

5.3 二叉树

二叉树的性质

• 第 i 层最多 2ⁱ⁻¹ 个结点 (i≥1)。
• 高度 k 的二叉树最多 2ᵏ−1 个结点。
• n₀ = n₂ + 1（叶子数 = 度为 2 的结点数 + 1）。
• 具有 n 个结点的完全二叉树高度为 ⌊log₂n⌋ + 1（或等价写为 ⌈log₂(n+1)⌉）。

特殊二叉树

• 满二叉树：每一层结点数都达到最大（2ᵏ−1 个结点）。
• 完全二叉树：除最后一层外其余各层均满，最后一层结点都靠左。
• 二叉排序树 (BST)：左子树所有值 < 根值 < 右子树所有值。
• 平衡二叉树 (AVL)：左右子树高度差 ≤ 1。

二叉树的存储

• 顺序存储：用数组，i 号位的左孩子在 2i，右孩子在 2i+1。适合完全二叉树。
• 链式存储：每个结点含 lchild 和 rchild 两个指针。

5.4 二叉树的遍历

按根结点访问顺序分为四种遍历：

• 前序遍历：根 → 左 → 右
• 中序遍历：左 → 根 → 右（BST 中序遍历得到有序序列）
• 后序遍历：左 → 右 → 根
• 层序遍历：从上到下、从左到右（借助队列）

void PreOrder(BTNode *t){
  if(t){ visit(t); PreOrder(t->lchild); PreOrder(t->rchild); }
}
void InOrder(BTNode *t){
  if(t){ InOrder(t->lchild); visit(t); InOrder(t->rchild); }
}
void PostOrder(BTNode *t){
  if(t){ PostOrder(t->lchild); PostOrder(t->rchild); visit(t); }
}

5.5 线索二叉树

n 个结点的二叉链表中有 n+1 个空指针域，利用这些空指针域指向遍历序列中的前驱和后继，称为 线索。

• ltag=0 表示 lchild 指向左孩子，ltag=1 表示指向前驱。
• rtag=0 表示 rchild 指向右孩子，rtag=1 表示指向后继。
• 中序线索二叉树中，头结点的 lchild 指向根结点，rchild 指向中序序列最后一个结点。

5.6 树与二叉树的转换

转换步骤：

1. 将每棵树转换为二叉树（左孩子右兄弟）。
2. 将各棵二叉树的根结点相连作为兄弟。
3. 连接后的整体即为森林对应的二叉树。

5.7 哈夫曼树

哈夫曼树的构造步骤

1. 将 n 个带权结点看作 n 棵只有一个结点的二叉树，构成森林 F。
2. 在 F 中选取两棵权值最小的树作为左右子树构造新二叉树，新树根权值为两子树根权之和。
3. 将新树加入 F，删除原两棵树。
4. 重复步骤 2-3 直到 F 中只剩一棵树。

哈夫曼编码

从根到每个叶子的路径上的左"0"右"1"序列即为该字符的哈夫曼编码。哈夫曼编码是前缀编码，任一字符的编码不是其他字符编码的前缀。

• 编码长度 = 该字符在哈夫曼树中的路径长度。
• 平均编码长度 = Σ(频率 × 码长)，等于 WPL / 总频率。

5.8 并查集 (Disjoint Set Union)

实现方式

• 双亲数组表示：parent[i] 表示元素 i 的双亲。
• 查找：沿 parent 指针向上直到找到根（parent[i]==i）。
• 合并优化：按秩合并（小树挂到大树）或按高度合并。
• 路径压缩：查找时将路径上所有结点直接指向根。

int Find(int x){
  if(parent[x] != x) parent[x] = Find(parent[x]);  // 路径压缩
  return parent[x];
}
void Union(int x, int y){
  x = Find(x); y = Find(y);
  if(rank[x] < rank[y]) parent[x] = y;
  else if(rank[x] > rank[y]) parent[y] = x;
  else { parent[y] = x; rank[x]++; }
}

5.9 线索二叉树动画演示

利用 n+1 个空指针域存放中序前驱/后继。ltag=0指向左孩子, ltag=1指向前驱; rtag同理。

5.10 树/森林与二叉树转换

左孩子右兄弟表示法: 第一个孩子->左孩子, 下一个兄弟->右孩子。左侧为原树(A有3个孩子B,C,D; B有2个孩子E,F; D有1个孩子G), 右侧为转换后的二叉树。

5.11 红黑树插入动画演示

红黑树是自平衡二叉搜索树，通过5条颜色性质保证O(log n)操作。插入时新节点默认为红色，若违反性质则需调整：Case1叔父红→颜色翻转，Case2/3叔父黑→旋转+重着色。

5.12 堆与优先队列 [25新增]

堆的核心特性：根结点是整个堆中的最大值（大根堆）或最小值（小根堆）。堆本身是一棵完全二叉树，但不要求左右子树有序（与二叉搜索树不同）。

堆的存储结构

由于堆是一棵完全二叉树，自然使用数组进行顺序存储：

• 根结点下标为 0。
• 结点 i 的左孩子：2i + 1
• 结点 i 的右孩子：2i + 2
• 结点 i 的父结点：⌊(i − 1) / 2⌋
• 最后一个非叶子结点下标：⌊n/2⌋ − 1

堆的基本操作

1. 上滤 (Percolate Up / Sift Up)

当新元素插入到堆的末尾时，需要向上调整以维护堆的性质：将新结点与其父结点比较，若违反堆序则交换，重复此过程直到堆序恢复。

void PercolateUp(int heap[], int i){
  while(i > 0 && heap[i] > heap[(i-1)/2]){  // 大根堆
    swap(heap[i], heap[(i-1)/2]);
    i = (i-1)/2;
  }
}

2. 下滤 (Percolate Down / Sift Down)

当堆顶元素被替换（或删除）后，新的堆顶需要向下调整：将当前结点与其较大（大根堆）或较小（小根堆）的孩子比较，若违反堆序则交换，重复此过程。

void PercolateDown(int heap[], int n, int i){
  int largest = i;
  int l = 2*i + 1, r = 2*i + 2;  // 左右孩子
  if(l < n && heap[l] > heap[largest]) largest = l;
  if(r < n && heap[r] > heap[largest]) largest = r;
  if(largest != i){
    swap(heap[i], heap[largest]);
    PercolateDown(heap, n, largest);
  }
}

3. 插入 (Insert) — O(log n)

将新元素放在堆的末尾，然后执行上滤操作使其恢复到正确位置。最坏情况下需要上滤到根，比较次数为树高 O(log n)。

4. 删除堆顶 (Delete) — O(log n)

用堆的最后一个元素替换堆顶，堆大小减 1，然后对新的堆顶执行下滤操作。最坏情况下需要下滤到叶子，比较次数为 O(log n)。

建堆 (Build Heap)

给定一个无序数组，可以通过自底向上的方法在 O(n) 时间内建成堆：

1. 从最后一个非叶子结点 ⌊n/2⌋ − 1（0 下标）开始，向前遍历每个结点。
2. 对每个结点执行下滤操作，使其成为以该结点为根的合法堆。

void BuildHeap(int heap[], int n){
  for(int i = n/2 - 1; i >= 0; i--)
    PercolateDown(heap, n, i);
}

时间复杂度推导：为什么建堆是 O(n)？

初看每个结点都执行下滤，似乎是 O(n log n)，但经过更精确的分析可以得到 O(n)：

• 第 h 层（从底向上编号，底层 h=1）最多有 2ʰ⁻¹ 个结点。
• 每个第 h 层的结点下滤最多 h−1 次。
• 总比较次数：Σ(h−1) × 2ʰ⁻¹ = 2ⁿ⁺¹ − n − 2 = O(n)（令 n 为总结点数，H 为树高）。
• 直观理解：大部分结点都在底层，它们下滤的深度很小；真正下滤较深的只有少量顶层结点。

堆的应用

• 堆排序：先建堆 O(n)，然后反复交换堆顶与末尾元素并下滤，共 n−1 轮，每轮 O(log n)，总 O(n log n)。空间 O(1)，不稳定。
• 优先队列 (Priority Queue)：堆是最常用的优先队列实现。小根堆实现最小优先队列（每次取最小值），大根堆实现最大优先队列。
• Top-K 问题：求最大的 K 个元素 → 用大小为 K 的小根堆，遍历数组，堆顶即当前第 K 大阈值。时间复杂度 O(n log K)。
• 堆优化 Dijkstra / Prim：用堆维护候选边/结点，将朴素 O(V²) 优化至 O((V+E) log V)。
• 哈夫曼树构建：每次选权值最小的两棵树合并，用最小堆维护森林。

堆 vs 二叉搜索树 (BST)