• 树：基本概念、满 $k$ 叉树性质、树的表示、存储结构
  • 二叉树：
    • 基本概念、表达式树
    • 满二叉树和完全二叉树的性质
    • 存储方式（顺序存储、链式存储）
    • 二叉树的遍历（先序、中序、后序）的（递归、非递归）实现
    • 通过遍历序列来恢复二叉树，及其非递归实现
    • 线索二叉树
    • 哈夫曼树
  • 堆：定义、性质、堆调整算法、插入、删除

易混概念

  • 树的度：树中各结点度的最大值
  • 双亲结点：父结点
  • 层次：即"结点深度"，根结点层次为 $1$，其余结点的层次为父结点层次 $+1$
  • 堂兄弟结点：同层次结点
  • 有序树/无序树：子树有先后顺序/无先后顺序
  • 满二叉树：所有非叶子结点度数为 $2$，且所有叶子结点都在同一层
  • 完全二叉树：满二叉树删去右侧连续一段叶子结点形成的树，叶子结点只在最下层和次下层

需要注意的结论

  • 二叉树中若叶子结点数为 $n_0$，度为 $2$ 的结点数为 $n_2$，则 $n_0 = n_2 + 1$

    快速证明：$n = n_0 + n_1 + n_2,\ n-1 = n_1 + 2n_2 \Rightarrow n_0 = n_2 + 1$

    形式理解：每个二度点相当于会合并两个结点，最终只剩一个为根结点

树形态点数与深度关系0度点数 $n_0$（叶子）1度点 $n_1$2度点数 $n_2$非叶结点数 $n_{\text{非叶}}$
满二叉树$n = 2^h - 1$
$h = \log_2 (n + 1)$		$n_0 = 2^{h-1}$$n_1 = 0$$n_2 = 2^{h-1}-1$$n_{\text{非叶}} = 2^{h-1}-1$
完全二叉树$2^{h-1} \le n \le 2^h - 1$
$h = \lfloor \log_2 n + 1\rfloor$		$n_0 = \lceil n/2 \rceil$$n_1 \in {0,1}$ 且 $n_1 = (n+1)\bmod 2$$n_2 = n_0 - 1$$n_{\text{非叶}} = \lfloor n/2 \rfloor$

对于满 $k$ 叉树，若层次从 $0$ 开始，编号从 $0$ 开始：

  • 第 $i$ 层有 $k^i$ 个结点，总共有 $(k^{h + 1} - 1) / (k - 1)$ 个结点。
  • 编号为 $i$ 的结点的儿子编号为 $[ik + 1, ik + k]$，父结点为 $\lfloor (i - 1) / k\rfloor$.
  • 编号为 $i$ 的结点所在层次为 $\lfloor log_k (i(k - 1) + 1) \rfloor$.

二叉树遍历的非递归实现

记录 p 表示当前所在的结点，一开始为根结点，并开一个栈记录待访问元素。

  • 先序遍历：
    • 若 p 非空，先访问 p，再入栈，p = p->lchild
    • 若 p 空，弹栈顶为 p，再令 p = p->rchild
  • 中序遍历：
    • 若 p 非空，入栈，p = p->lchild
    • 若 p 空，弹栈顶为 p，先访问 p，再令 p = p->rchild
  • 后序遍历：
    • （方法一：pre 指针法）需要一个辅助指针 pre 表示刚刚访问过的结点
    • 若 p 非空，再入栈，p = p->lchild
    • 若 p 空，取栈顶为 p（不弹栈）
      • 若 p->rchild == pre 则左右子树已访问，访问 p，出栈，令 pre = p; p = null
      • 否则右子树未访问，p = p->rchild
    • （方法二：tag 法）栈中对于每个结点记录 L/R 位，表示对应右子树是否已处理
    • 若 p 非空，入栈 (p, L)，p = p->lchild
    • 若 p 空，取栈顶为 (p, *)（不弹栈）
      • 若标记为 R，则左右子树已访问，访问 p，出栈，仍 p = null
      • 若标记为 L，则右子树未访问，改栈顶为 (p, R)，并 p = p->rchild

通过遍历序列复原二叉树

通过先序序列和中序序列，可以复原二叉树。

通过后序序列和中序序列，可以复原二叉树。

通过先序序列和后序序列，无法复原二叉树。

线索二叉树

线索二叉树中，每个结点为 (val, lchild, rchild, ltag, rtag)

对于线索二叉树的每个结点，

  • 若 lchild == null，则令左指针为遍历序列的前序结点，并令 ltag = 1。
  • 若 rchild == null，则令右指针为遍历序列的后继结点，并令 rtag = 1。

构建时仍需递归或栈辅助，而线索化完成后可在无需栈和递归的情况下进行遍历。

构建线索二叉树总体流程： 当访问（指将结点输出到序列）当前结点 p 时：

  • 若 p->lchild == NULL：
    • p->lchild = pre
    • p->ltag = 1
  • 若 pre != NULL 且 pre->rchild == NULL：
    • pre->rchild = p
    • pre->rtag = 1
  • 然后：pre = p

中序线索二叉树的完整访问流程：

  1. 找到第一个结点。从根结点开始一直向左走到尽头。
  2. 开始访问，并重复找后继。先访问该结点 p，然后判断
    • rtag = 1：则可以取到后继，p = p->rchild
    • rtag = 0：则有真正右子树，那么仍然令 p = p->rchild，然后一直向左走直至 p->ltag = 1 停止。
  3. 当 p = null 停止。

前序线索二叉树的完整访问流程：

  1. 从根开始。p = root.
  2. 开始访问，并重复找后继。先访问该结点 p，然后判断
    • ltag = 0：则有真正左儿子，p = p -> lchild
    • ltag = 1, rtag = 0：则有真正右儿子，p = p -> rchild
    • rtag = 1：则可以取到后继，p = p->rchild
  3. 当 p = null 停止。

后序线索二叉树的完整访问流程：每个结点需要记录自己的父亲结点 father.

  1. 找到第一个结点。从根结点开始一直先向左走，没有左儿子就向右走直至不能走为止。
  2. 开始访问，并重复找后继。先访问该结点 p，然后判断
    • rtag = 1：则可以取到后继，p = p->rchild
    • rtag = 0 且为根结点：遍历结束
    • rtag = 0 且不为根结点：令 q = p->father
      • 若 p == q->rchild 或 q->rtag = 1：那么 p = q
      • 否则 p = q->father 再一直先向左走或向右走，找到第一个后序结点。

堆建立的调整算法

对于直接建立的完全二叉树，叶子结点范围为 $i > \lfloor n / 2 \rfloor$，我们需要对所有 $i$ 从 $\lfloor n / 2 \rfloor$ 到 $1$ 做一次向下调整（heapify / sify-down）。

下面假设要建立大根堆，假设要向下调整 $i$ 号叶子结点，此时左右子树都已经是大根堆。

  • 我们记录 temp = A[i], k = i
  • 每次比较 temp 和 i 的左右儿子（如果有）较大的那个，记作 child
  • 若 temp < A[child]，则需要让这个儿子上移 A[i] = A[child]，然后继续向下找位置 k = child.
  • 当无法向下时就停止。

对于弹堆顶操作，我们将 A[1]（被删除） 和 A[n] 交换，然后对 1 向下调整。

对于插入新元素操作，我们放在 A[n + 1]，然后向上调整：如果大于父结点就交换。

每次向上调整/向下调整的时间复杂度都是 $O(\log n)$.

孩子兄弟表示法

树转换为二叉树：每个节点，左儿子是第一个儿子，右儿子是下一个兄弟。

二叉树转换为树：每个节点的左儿子一直向右走的所有后代都是该结点的所有儿子。

森林转换为二叉树：首先给所有树转成二叉树，然后第 $i$ 个树的根节点的右儿子是第 $(i+ 1)$ 个树的根节点。

二叉树转换为森林：首先将根节点向右走的所有边断开，恢复为若干个二叉树树，然后每个二叉树转换为树。