algorithm - 哈夫曼算法中的二进制前缀码

Question

在霍夫曼编码算法中，有一个引理说:

The binary tree corresponding to an optimal binary prefix code is full

但我想不通为什么。你如何证明这个引理？

Answer 1

数据的任何二进制代码都可以表示为二叉树。代码由从根到叶的路径表示，左边代表前缀中的 0，右边代表 1(反之亦然)。请记住，每个符号都有一个叶节点。

为了证明最优代码将由满二叉树表示，让我们回顾一下满二叉树是什么，它是一棵树，其中每个节点要么是叶子，要么有两个 child 。

让我们假设某个代码是最优的并且由非满树表示。所以有一个顶点 u 只有一个子节点 v。u 和 v 之间的边将位 x 添加到以 v 为根的子树中的符号前缀代码(在叶子上)。从这棵树中，我可以删除边 x 并将 u 替换为 v，从而将以 v 为根的子树中所有符号的前缀码长度减一。这减少了至少一个符号的表示中的位数(当 v 是单例节点时。)

这表明树实际上并不代表最优代码，我的前提是错误的。从而证明引理。