问huffman算法中的二进制前缀码

EN

来自维基百科，

一棵完整的二叉树(有时是2棵树或严格的二叉树)是一棵树，其中除叶子以外的每个节点都有两个子节点。

生成huffman代码树的方式肯定会产生一个完整的二叉树。因为在算法的每一步，我们从队列中删除两个优先级最高(概率最低)的节点，并创建一个新的内部节点，并将这两个节点作为子节点。

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

为了证明一个最优的代码将由一个完整的二叉树来表示，让我们回顾一下一个完整的二叉树是什么，它是一个树，每个节点要么是叶子，要么有两个孩子。

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

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