Prefix-free code 前缀无歧义编码
为了生成的编码是PFC，字符必须放在编码树的叶节点上，不能放在内部节点上
编码是前缀无歧义编码 (PFC) $\iff$ 树是编码树，也就是说 PFC 和 编码树 都是在指无歧义性。
各叶子权相等
要让平均编码长度 ($\iff$ 叶节点平均深度, average leaf depth, ald) 最小
最优编码树的性质：
双子性，每个内部节点一定有两个孩子
很好理解，若单孩子，不如直接收上去。说明一定会是真二叉树。
层次性，最优编码树的叶节点，深度之差 $\le$ 1
若有深度之差 $\ge 2$ 的两个节点 $x$ 和 $y$，由双子性，$x$ 必有一兄弟子树 $q$，记其parent为 $p$。交换子树 $p$ 与 $y$，$x$ 的上升量与 $y$ 的下降量抵消，即 $depth(x) + depth(y) = depth(x’) + depth(y’)$。而由于 $p$ 与 $y$ 的深度只差 $\ge 1$，因此子树 $p$ 一定会上升，从而子树 $q$ 一定会上升，ald一定会减小。
最优编码树中的叶节点只能出现于最低两层。
只需创建一棵规模为 $2\lvert \Sigma \rvert - 1$ 的完全二叉树，并将字符分配给叶子，即得到了最优编码树。（注意不能有度为$1$的节点，否则直接收上去更优）
字符出现有频率之分，带权要考虑频率，让带权平均编码长度 ($\iff$ 叶节点带权平均深度, weighted average leaf depth, wald) 最小。
最优带权编码树仍然满足双子性，但是不一定满足层次性。不过还有一个性质：
若字符 $x$ 和 $y$ 的出现概率在所有字符中最低，则必然存在某棵最优带权编码树，使 $x$ 和 $y$ 在其中同处于最底层，且互为兄弟。
证明（教材P142）:
若某棵最优带权编码树 $T$ 中，最低频率的 $x$ 和 $y$ 不在最底层（这是可能的，比如huffman树字符频率全相等），则最底层必然存在双子 $a$ 和 $b$，用 $x$ 和 $y$ 去替换 $a$ 和 $b$，现在证明得到的这棵树一定是最优带权编码树
\[\begin{align*} \Delta =& d'_x f_x + d'_y f_y + d'_a f_a + d'_b f_b - (d_x f_x + d_y f_y + d_a f_a + d_b f_b) \\ =& d_a f_x + d_b f_y + d_x f_a + d_y f_b - (d_x f_x + d_y f_y + d_a f_a + d_b f_b) \\ =& (d_a - d_x)(f_x - f_a) + (d_b - d_y)(f_y - f_b) \\ & 乘的正负关系为 + - + - \\ =& \le 0 \end{align*}\]所以 $T’$ 也是一棵最优编码树。
相关题目：
Huffman树一定是最优PFC编码树，但最优PFC编码树不一定是Huffman树。也就是说，最优PFC编码树的范围更大。
例如，出现频率为 ${1,2,3,3}$ 的字符集，其中一棵Huffman树为：
9
/ \
3 6
/ \ / \
1 2 3 3
由于叶子节点的深度都相等，所以可以将其随意交换，depth不变，例如：
9
/ \
4 5
/ \ / \
1 3 2 3
这是最优带权编码树，但是Huffman树的构造过程，一定会把 1 和 2 捏到一起，所以这棵树不是Huffman树。