408数据结构-树

1. 树

1.1 基本概念

树是 $n$ 个结点的有限集。可以为空树 $n=0$。

树是一种逻辑结构。

树适用于表示具有层次结构的数据。最多只和上一层的一个结点有直接关系。

祖先：从根结点到结点 $K$ 的唯一路径上的所有除 $K$ 以外的结点，称为 $K$ 的祖先。

子孙：如果 $A$ 是 $K$ 的祖先，那么 $K$ 就是 $A$ 的子孙。

双亲/前驱：最接近 $K$ 结点的祖先，就是 $K$ 的双亲。

孩子/后继：如果 $E$ 为 $K$ 的双亲，那么 $K$ 就是 $E$ 的孩子。

兄弟：有相同双亲的结点互为各自的兄弟。

堂兄弟：双亲在同一层的结点互为堂兄弟。

结点的度：树中一个结点的孩子个数称为该结点的度。

树的度：树中结点的最大度数称为树的度。

分支结点/非终端结点：度大于 $0$ 的结点。

叶结点/终端结点：度为 $0$ 的结点。

结点的层次/深度：从树根开始定义，根结点为第 $1$ 层，其孩子为第 $2$ 层......以此类推。

结点的高度：以该结点为根的子树的高度。

树的高度/深度：树中结点的最大层数。

有序树：树中结点的各子树从左到右是有次序的。

无序树：不是有序树。

路径：两结点之间所经过的结点序列。

路径长度：路径上所经过的边的个数。

注意，树中的分支是有向的，从双亲指向孩子，所以树中的路径是从上向下的。同一双亲的两个孩子之间不存在路径。

森林：$m$ 棵互不相交的树的集合（$m$ 可以为 $0$）。

正则 $k$ 叉树：树中每个分支结点都有 $k$ 个孩子。即树中只有度为 $k$ 或 $0$ 的结点。

1.2 树的性质

• 树的结点数 $n$ 等于所有结点的度数之和再加 $1$。

• 度为 $m$ 的树中第 $i$ 层上至多有 $m^{i-1}$ 个结点（$i\ge 1$）。

• 高度为 $h$ 的 $m$ 叉树至多有 $\sum_{i=1}^h m^{i-1}=\frac{m^h-1}{m-1}$ 个结点。

• 度为 $m$，具有 $n$ 个结点的树的最小高度为 $\left \lceil \log_m(n(m-1)+1) \right \rceil$。

  证明：

$$\begin{align} &\frac{m^{h-1}-1}{m-1} < n \le \frac{m^h-1}{m-1} \\ &\Rightarrow h-1 < \log_m(n(m-1)+1) \le h \\ &\Rightarrow h_{\text{min}} = \left \lceil \log_m(n(m-1)+1) \right \rceil \end{align}$$

• 度为 $m$，具有 $n$ 个结点的树的最大高度 $h$ 为 $n-m+1$。

  证明：只有一层有 $m$ 个结点，其余层全只有一个结点。

1.3 存储结构

注意区分于二叉树的存储结构。

1.3.1 双亲表示法

根据每个结点只有一个双亲结点的性质，每个点记录其双亲结点的位置。

1.3.2 孩子表示法

每个点都有一个单链表，存储其孩子。

1.3.3 孩子兄弟表示法

也称作二叉树表示法。每个点只存其第一个孩子结点，以及其右兄弟的指针。

1.4 树与遍历

对于树：

• 先根遍历：先访问根结点，然后再依次遍历根节点的每棵子树。

  遍历序列与这棵树对应的二叉树的先序序列相同。

• 后根遍历：先依次遍历根节点的每棵子树，然后再访问根结点。

  遍历序列与这棵树对应的二叉树的中序序列相同。

对于森林：

• 先序遍历：从第一棵树开始，对每棵树进行先根遍历。
• 中序遍历：从第一棵树开始，对每棵树进行后根遍历。（部分教材也将中序遍历称为后序遍历）

2. 二叉树

2.1 概念与性质

二叉树是有序树（左右子树次序不能任意颠倒）。

二叉树和度为 $2$ 的有序树有显著区别：

• 二叉树不一定度为 $2$，只是度最多为 $2$。二叉树可为空树。
• 二叉树的结点无论其孩子数量是否为 $2$，均需要确定其左右次序。孩子的左右次序不是相对于另一结点而言的，而是确定的。

二叉树性质：

• 设非空二叉树中度为 $2$ 的结点数为 $n_2$，叶结点（度为 $0$ 的结点）的数量为 $n_0$，则有 $n_0 = n_2+1$。

  证明：设度为 $0$、$1$、$2$ 的结点个数为 $n_0$、$n_1$、$n_2$。结点总数 $n=n_0+n_1+n_2 = n_1+2n_2+1$，得到 $n_0=n_2+1$。

几种特殊的二叉树：

• 满二叉树：一颗高度为 $h$，且有 $2^h-1$ 个结点的二叉树。

  可以对满二叉树按从根结点开始，自上而下，自左向右进行编号。对于编号为 $i$ 的结点，如果有双亲，则其双亲为 $\left \lfloor \frac{i}{2} \right \rfloor$，如果只有左孩子，则左孩子为 $2i$，如果有右孩子，则右孩子为 $2i+1$。

• 完全二叉树：高度为 $h$，有 $n$ 个结点，且每个结点都与高度为 $h$ 的满二叉树中编号为 $1\sim n$ 的结点一一对应时。

  • 若 $i\le \left \lfloor \frac{n}{2} \right \rfloor$，则 $i$ 为分支结点，否则为叶结点。
  • 叶结点只可能在层次最大的两层上出现。对于最大层次中的叶结点，都依次排列在该层最左边的位置上。
  • 如果有度为 $1$ 的结点，则最多只可能有一个，且该结点只有左孩子而无右孩子。
  • 如果 $i$ 为叶结点或只有左孩子，则编号大于 $i$ 的结点均为叶结点。
  • 如果 $n$ 为奇数，则每个分支结点都有左孩子和右孩子。如果 $n$ 为偶数，则编号最大的分支结点（编号为 $\frac{n}{2}$）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。
  • 结点 $i$ 所在层次/深度为 $\left \lfloor \log_2i \right \rfloor + 1$。
  • 具有 $n$ 个结点的完全二叉树的高度为 $\left \lceil \log_2(n+1) \right \rceil$ 或 $\left \lfloor \log_2n \right \rfloor + 1$。

• 二叉排序树：左子树上所有结点的关键字均小于（严格小于）根结点的关键字。右子树上所有结点的关键字均大于（严格大于）根结点的关键字。

• 平衡二叉树：树中任意一个结点的左子树和右子树的高度差的绝对值不超过 $1$。

2.2 存储结构

二叉树本身是一个逻辑结构。

2.2.1 顺序存储

完全二叉树和满二叉树比较适合顺序存储。将树上的结点存储到其编号对应的下标中。

对于一般的二叉树，也可以使用顺序结构存储。

但是最坏情况下，一个高度为 $h$ 且只有 $h$ 个结点的单支二叉树需要占据 $2^h-1$ 个存储单元。

2.2.2 链式存储

二叉树一般都采用链式存储结构。

含有 $n$ 个结点的二叉树，使用链式存储，链表含有 $n+1$ 个空链域。

这种存储结构也称为二叉链表。

2.3 二叉树遍历

先序/中序/后序遍历

时间复杂度：$O(n)$

空间复杂度：递归工作栈是遍历算法需要的辅助空间。最坏情况下，工作栈深度为树的深度，时间复杂度为 $O(n)$

使用栈可以做到非递归：

栈中数据的含义表示后续我要访问这个点的右孩子。

后序遍历的实现稍微有些复杂，因为需要确保左右孩子都已经被访问，才能访问根结点。

这里只 GetTop(S,p) ，没有把双亲结点弹出去。当右孩子遍历完之后，会将自己弹栈，紧接着访问自己，然后设置 r，并直接令 p=NULL。这会使得下一个 while 循环直接触发 else 内容，此时栈顶结点为右孩子的双亲结点，p->rchild!=r 必然不成立，那么又会继续往上回溯。

非递归遍历时，栈中存放着当前结点以及当前结点的所有祖先结点。这可以用来求根结点到某个结点的路径、两个结点的最近公共祖先等。

层次遍历

由遍历序列构造二叉树

只给出四种遍历序列的任意一种，无法唯一确定一颗二叉树。

有两个遍历序列，且有一个中序遍历才可以唯一确定二叉树（比如只有前序+后序是不能唯一确定的）。中序遍历序列用于划分左右子树。

2.4 线索二叉树

对二叉树进行遍历后，会得到一个遍历序列。序列中每个结点（非头尾）都有一个直接前序和一个直接后继。

一般的二叉树仅能体现出一种父子关系，不能直接得到结点在遍历序列中的前驱或后继。

二叉树使用二叉链表进行存储的时候有很多空链域，所以我们考虑利用这些空链域来记录结点的前驱和后继。这就是线索二叉树。指向结点前序和后继的指针称为线索。

线索二叉树使用如下被称为线索链表的存储结构。线索二叉树本身也是一种存储结构。但二叉树确实逻辑结构。

线索化：指将二叉树的二叉链表中的空指针改为指向前驱或者后继的线索。

中序线索二叉树

核心思想是，在对当前结点进行线索化的时候，更新当前结点的前驱和 pre 的后继。最后再把线索二叉树中的最后一个结点单独处理一下。

为了方便，可以在线索链表上添加一个头结点，lchild 指向二叉树的根节点（非线索），rchild 指向中序序列的最后一个结点（线索）。同时中序序列的第一个结点的前驱和最后一个结点的后驱都指向头结点（线索）。

• 求第一个结点

• 求最后一个结点

  也就是找最右下的结点。

  将 Firstnode 函数中的 ltag 改为 rtag，lchild 改为 rchild。

• 求后继

  如果有线索则直接用线索。没线索的话找右子树中最左下结点。

• 求前驱

  如果有线索则直接用线索。没线索的话找左子树中最右下结点。

先序/后序线索二叉树

线索化的方法和中序差不多，就是该一下线索化和递归遍历的位置。

对于先序线索二叉树：

• 第一个结点：就是根节点。
• 最后一个结点：最右下的结点。
• 后继：如果有左孩子，那么左孩子就是其后继。如果没有左孩子，那么右孩子就是其后继。右孩子也没有的话，右链域就指向了其后继。
• 前驱：和后序线索二叉树中求前驱是对称的。

对于后序线索二叉树：

• 第一个结点：最左下的结点。
• 最后一个结点：根节点。
• 后继：较为复杂，分三种情况。由于需要得到一个点的双亲，所以需要带标志域的三叉链表作为存储结构。
  • 如果结点是二叉树的根，则后继为空。
  • 如果结点是双亲结点的右孩子，或是其双亲的左孩子且双亲没有右子树，那么后继即为双亲。
  • 如果结点是双亲结点的左孩子，且双亲有右子树，那么需要在其双亲的右子树的上找第一个结点。
• 前驱：和先序线索二叉树中求后继是对称的。

2.5 树/森林转二叉树

对于树：

1. 在兄弟结点之间连线
2. 对于每个结点，只保留与它第一个孩子的连线，其他的全都抹掉

对于森林：

假如树/森林 $F$ 转为二叉树 $T$，$F$ 中有 $n$ 个结点，其中 $a$ 个为叶结点。则 $F$ 中有 $n-a$ 个非叶结点，$T$ 中二叉链表左指针域为空的个数为 $a$，右指针域为空的个数为 $n-a+1$。

2.6 哈夫曼树

结点的带权路径长度：从树的根到一个结点的路径长度与该结点上的权值的乘积。

树的带权路径长度：树中所有结点的带权路径长度之和。

哈夫曼树/最优二叉树：在含有 $n$ 个带权叶结点的二叉树中，带权路径长度最小的二叉树。

构造

将所有结点视为只含有一个结点的二叉树构成的森林。然后每次，从这个森林中选择两个根节点权值最小的两个树，作为新结点的左右子树，新节点的权值为左右子树上的根节点权值之和。然后从森林中删除选出的两棵树，并把新得到的树放入森林。

性质

• 共进行了 $n-1$ 次构造，每次构造引入一个新结点。哈夫曼树的结点总数为 $2n-1$。
• 每次构造都选择两颗子树作为新结点的孩子，因此哈夫曼树不存在度为 $1$ 的结点。
• 根据构造过程还能够发现，树的带权路径长度为树中所有分支结点的权值之和。

编码

前缀编码：没有一个编码是另一个编码的前缀。前缀编码使得解码比较简单，从左到右扫一遍就可以。

在构造出来的哈夫曼树的边上标 $1$ 或 $0$，然后根节点到叶结点的路径上的 $0$ 和 $1$ 就构成了这个叶结点的哈夫曼编码。

哈夫曼树的左右分支用 $0$ 表示还是 $1$ 表示没有明确规定，因此构造的哈夫曼编码不唯一。

2.7 并查集

没有带路径优化得并查集，最坏情况下的时间复杂度为 $O(n)$。如果没有特殊说明，408 题目中会认为并查集的时间复杂度为 $O(n)$。

3. 错题

有可能只有一个结点，这样的话 Ⅲ 就不对了。

对于所有树形的情况，最少只需要 $16$ 个存储单元就可以存下某个特定的树形情况。但是这个题应该是要求存储单元可以把所有树形都存下。

一个点在另一个点在左边，并不意味着这两个结点的深度是一样的。C 选项的反例是一个全右的链。

后序遍历可以做到在从 $n$ 回溯的时候得到到 $m$ 的路径（毕竟 $n$ 的所有祖先的左右子树已经遍历完了）

根结点没有前驱，叶子节点没有后继。

度为 $m$ 的哈夫曼树即为正则 $m$ 叉树。度为 $0$ 的点数量为 $n_0=n$，度为 $m$ 的点数量为 $n_m$。

于是有 $mn_m+1=n_m+n_0$，得 $n_m=\frac{n-1}{m-1}$。