树和二叉树

树

一棵树是 $n(n \geq 0)$ 个结点的有限集合，非空树满足： $$T = {r, T_1, T_2, \cdots, T_m}$$ 其中 $r$ 为树的根结点，$T_1, T_2, \cdots, T_m$ 为 $m$ 棵互不相交的子集合，每个子集合本身又是一棵树，称为 $r$ 的子树。

$n = 0$ 时，树为空树。

基本术语

结点：树中的每个元素称为结点。包含一个数据元素的值和若干指向结点的指针。
结点的度：结点的子树个数。
叶结点：度为 $0$ 的结点。又称为终端结点。
分支结点：除叶结点外的结点。又称为非终端结点。
子女结点：结点的子树的根结点称为该结点的子女结点。
双亲结点：若结点 $y$ 是结点 $x$ 的子女结点，则结点 $x$ 是结点 $y$ 的双亲结点。
兄弟结点：同一双亲结点的子女结点之间互称为兄弟结点。
祖先结点：从根结点到该结点的路径上的所有结点。
子孙结点：以某结点为根的子树中除了根结点之外的所有结点。
结点间的路径：从一个结点到另一个结点的分支构成的序列 $v_i, v_1, v_2, \cdots, v_k, v_j$。
结点的深度：即结点到根结点的路径长度 + 1，根结点的深度为 $1$。
结点的高度：空树的高度为 $0$，叶结点的高度为 $1$，非叶结点的高度为其所有子女结点的最大高度 + 1。
树的深度：树中所有结点的最大深度。
树的高度：根结点的高度。树的高度与树的深度相等。
树的宽度：树中各层结点的最大个数。
树的度：树中结点的最大度数。
有序树：树中结点的各子树 $T_1, T_2, \cdots$ 有序排列。其中 $T_1$ 是第一个子树，$T_2$ 是第二个子树，$\cdots$。
无序树：树中结点的各子树 $T_1, T_2, \cdots$ 无序排列，各棵子树之间的顺序不重要。
森林：$m(m \geq 0)$ 棵互不相交的树的集合。

二叉树

二叉树是具有 $n(n \geq 0)$ 个结点的有限集合，该集合或者为空集，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 $$T = \begin{cases} \varnothing & n = 0 \newline \lbrace r, T_L, T_R \rbrace & n > 0 \end{cases}$$

tips:

二叉树不是树，是一种树形结构。
二叉树都具有左右子树，只不过有的子树为空。

二叉树的性质

在二叉树的第 $i$ 层上至多有 $2^{i-1}$ 个结点。
深度为 $k$ 的二叉树至多有 $2^k - 1$ 个结点，最少有 $k$ 个结点。
对于任何一棵二叉树，如果其叶结点数为 $n_0$，度为 $2$ 的结点数为 $n_2$，则 $n_0 = n_2 + 1$。

特殊二叉树

满二叉树：每个结点要么是叶结点，要么有两个子女结点。
- 满二叉树的叶结点数 $n_0 = n_2 + 1$。
- 满二叉树的结点总数 $n = 2^{h+1} - 1$，其中 $h$ 为树的高度。
完全二叉树：若设二叉树的高度为 $h$，除第 $h$ 层外，其它各层的结点数都达到最大个数，第 $h$ 层的结点都连续集中在最左边。
- 完全二叉树的高度 $h = \lceil \log_2 (n+1) \rceil$（当 $n = 0$ 时不满足式子 $h = \lfloor \log_2 n \rfloor + 1$ ）。

二叉树的存储结构

顺序存储结构

完全二叉树：按照层次顺序存储，从上到下，从左到右，下标从 $0$ 开始。
一般二叉树：按照完全二叉树的方式存储，空结点用特殊值表示。

链式存储结构

每个结点至少含有三个域：lchild、data、rchild。（此时为二叉链表）若需要快速找到其双亲结点，可以增加一个域 parent。（此时为三叉链表）

广义表表示

A(B(D,E),C(,F)) 表示如下二叉树：

    A
   / \
  B   C
 / \   \
D   E   F

二叉树的遍历

先序遍历：根结点 -> 左子树 -> 右子树
中序遍历：左子树 -> 根结点 -> 右子树
后序遍历：左子树 -> 右子树 -> 根结点
层次遍历：从上到下，从左到右

遍历的应用

先序遍历：复制二叉树、求二叉树的深度、输出二叉树的括号表示法、输出二叉树的前缀表达式。
- 字符串 ABD##E##C#F## 表示如下二叉树：

    A
   / \
  B   C
 / \   \
D   E   F

中序遍历：输出二叉树的中缀表达式。
后序遍历：释放二叉树的空间，输出二叉树的后缀表达式。

单纯应用先序遍历或者中序遍历可以直接确定完全二叉树的结构。
需要结合先序遍历和中序遍历或者中序遍历和后序遍历才能确定一般二叉树的结构。先序遍历和后序遍历无法确定二叉树的结构。

以下结论也是成立的：

用二叉树的中序序列和层次序序列可以唯一确定一棵二叉树。
用二叉树的中序序列和各结点所处层次可以唯一确定一棵二叉树。
用二叉树的中序序列和各结点的左子女可以唯一确定一棵二叉树。
用二叉树的中序序列和各结点的右子女可以唯一确定一棵二叉树。
用二叉树的先序序列和各结点的右子女可以唯一确定一棵二叉树。
用二叉树的后序序列和各结点的左子女可以唯一确定一棵二叉树。

二叉树的计数

当先序遍历序列为 $1, 2, 3, \cdots, n$ 时，可以构造出多少种不同的二叉树？ $$b_n = \begin{cases} 1 & n = 0 \newline \displaystyle\sum_{i=0}^{n-1} b_i \times b_{n-1-i} & n > 0 \end{cases}$$ 卡特兰数： $$\mathcal{C}_n = \frac{1}{n+1} \binom{2n}{n}$$

线索二叉树

线索二叉树的结点会增加两个域：pred 和 succ，分别指向某个遍历次序下的前驱和后继结点。

也可以采用 ltag 和 rtag 两个域参数，分别表示左右指针是否指向子女结点还是前驱后继结点。 ltag 和 rtag 为 0 时，表示指向子女结点；为 1 时，表示指向前驱后继结点。

前序遍历：前驱是双亲结点，后继是右子女结点。
后序遍历：前驱是左子女结点，后继是双亲结点。

树与森林

三种存储结构

双亲表示法

每个结点都有一个指向双亲结点的指针域。

子女链表表示法

每个结点都存有一个链表，以第一个子女结点为头结点，其余子女结点依次排列。

子女-兄弟表示法

每个结点存储两个指针域，一个指向第一个子女结点，一个指向下一个兄弟结点。

是最省空间的存储的表示方式。

广义表表示法

R(A(D, E), B, C(F(G, H, K))) 表示如下树：

    R
   /|\
  A B C
 / \   \
D   E   F
       /|\
      G H K

树与森林转化为二叉树

树转化为二叉树

将 “子女-兄弟表示法” 中的每个结点的子女结点看作其左子女结点，其兄弟结点看作其右子女结点。

森林转化为二叉树

将森林中树的根看作兄弟，再用树转化为二叉树的方法。

二叉树转化为树与森林

采用上述方法的逆过程。转化成的树与森林是唯一的。

树与森林的遍历

树的遍历

先序遍历：根结点 -> 第一个子女结点 -> 第一个子女结点的子树 -> 第二个子女结点 -> 第二个子女结点的子树 -> $\cdots$
后序遍历：第一个子女结点 -> 第一个子女结点的子树 -> 第二个子女结点 -> 第二个子女结点的子树 -> $\cdots$
层次遍历：从上到下，从左到右

树的先序遍历与其转化成二叉树后的先序遍历是一致的。树的后序遍历与其转化成二叉树后的中序遍历是一致的。

森林的遍历

先根次序遍历：对每一课树进行先序遍历。
中根次序遍历：对每一课树进行后序遍历。
层次遍历：从上到下，从左到右，不要每棵树单独解决，而是将森林看作一个树（忽略最外层的根结点）。

森林	树	二叉树
先根次序遍历	先序遍历	先序遍历
…	中序遍历	…
中根次序遍历	后序遍历	中序遍历

Huffman 树

带权路径长度

树的路径长度（Path Length）是从树的根结点到每个结点的路径长度之和。树的带权路径长度（Weighted Path Length，WPL）是树的路径长度与结点的权值的乘积之和。即： $$WPL = \sum_{i=1}^n w_i \cdot l_i$$

扩充二叉树

给定一个具有 $n$ 个权值的集合 $W = \lbrace w_1, w_2, \cdots, w_n \rbrace$，和一棵具有 $n$ 个叶结点的二叉树，将 $w_1, w_2, \cdots, w_n$ 依次赋值给这棵二叉树的叶结点，得到的二叉树称为扩充二叉树。

带有权值的叶节点称为扩充二叉树的外结点。其余不带权值的分支结点称为扩充二叉树的内结点。定义：扩充二叉树的带权路径长度是从根结点到每个外结点的长度路径与该结点上的权值乘积之和。即 $$WPL = \sum_{i=1}^n w_i \cdot l_i$$

在权值为 $w_1, w_2, \cdots, w_n$ 的扩充二叉树中，其 $WPL$ 最小的二叉树称为最优二叉树或Huffman 树。

Huffman 树的构造

将 $n$ 个权值看作 $n$ 棵只有一个结点的二叉树。
选取两个根结点的权值最小的二叉树进行合并，生成一棵新的二叉树，其根结点的权值为两个根结点的权值之和。
删除原来的两个二叉树，将新生成的二叉树加入到二叉树集合中。
重复步骤 2 和 3，直到只剩下一棵二叉树为止。

Huffman 编码

Huffman 编码是一种变长编码，根据字符出现的频率来确定其编码。左分支为 0，右分支为 1。用平均编码长度 $\displaystyle\sum_{i=1}^n p_i \cdot l_i$ 来衡量编码的效率。

由于构造 Huffman 树的过程中，选取左右子树的顺序是任意的，所以 Huffman 编码不是唯一的。

堆

以完全二叉树的顺序存储结构来存储的一种特殊的二叉树。

大根堆：每个结点的值都大于或等于其左右子结点的值。
小根堆：每个结点的值都小于或等于其左右子结点的值。