离散数学复习:树的应用

你妈的,终于快解放了

好看的

---

表达式的(逆)波兰序记法

---

• 使用根树来表达一个计算表达式.

• 使用内点来表示表达式中的运算符,使用内点的左/右子树表示对应的运算分量.

• 使用前序遍历 / 后序遍历可以得到该表达式的前/后缀形式.

• 使用中序遍历可以得到中缀形式, 但不同的根树(不同的表达式)可能具有相同的中缀形式, 因此不使用.

  • 前缀形式表达式的计算: 从右向左遍历表达式,遇到运算符就对运算符右边的两个运算对象进行计算.
  • 后缀形式表达式的计算: 从左向右遍历表达式,遇到运算符就对运算符左边的两个运算对象进行计算.

二叉搜索树(略)

这么简单的东西自己看看得了

---

前缀码

---

前缀

如果符号串$\alpha$可以表示为符号串$\beta_1$和$\beta_2$(均可以为空串)的并置,则称$\beta_1$为$\alpha$的一个前缀.

设$A = \set{\beta_1, \beta_2, ..., \beta_m}$是符号串的集合, 且对于任意$\beta_i, \beta_j \in A$, 若$i \neq j$, 有$\beta_i 与 \beta_j$互不为前缀, 则称$A$为前缀码.

若$A$中的任意串$\beta_i$只含有符号$0, 1$, 则称$A$为二元前缀码.

---

使用二叉树生成二元前缀码

生成方法

1. 给边标号: 对于每个内点, 对其出边标号.左出边标$0$, 右出边标$1$.
2. 给叶子编号: 从根节点到每个叶子节点存在唯一的通路; 构成该通路的边的标号依次并置(从根节点开始), 所得的串称为该树叶的编号.

给定一棵完全二叉树, 可以产生唯一的二元前缀码.

---

最优前缀码

问题: 使用二元前缀码$A = \set{\beta_1, \beta_2, ..., \beta_m}$ 表示$m$个不同的字母, 如果各个字母的使用频率不同,如何设计编码方案使得总传输量最小?

最优二叉树

若$T$是二叉树,且$T$的每个叶子节点$v_1, v_2, ..., v_t$均含有数值权重$w_1, w_2, ..., w_t$, 则该二叉树$T$的权重$W(T)$可以表示为$\sum_{i = 1}^{t} w_i l(v_i)$, 其中$l(v_i)$表示$v_i$在树中的层数.

具有相同权序列的二叉树中权值最小的二叉树称为最优二叉树.

---

Huffman编码算法

• 输入: 正实数序列$w_1, w_2, \cdots, w_t$.
• 输出: 具有$t$个树叶, 权序列为$w_1, w_2, \cdots, w_t$的最优二叉树.
• 算法过程:
  1. 将$t$个树叶初始化为根权为$w_i$的$t$棵根树.
  2. 每次选择当前森林中两棵根权最小的树,以它们为左, 右子树构建一棵新的, 根权为两棵子树根权(根权为树的根节点的权重, 等于该根对应的子树的权值之和)之和的根树.
  3. 当森林中只剩下一棵根树时停止.
• 注意: 该算法形成的结果可能不唯一.