在哈夫曼编码算法中，有一个引理是：“对于一个最优的二进制前缀编码所对应的二叉树是满二叉树。”但我不知道为什么会是这样。你如何证明这个引理？
霍夫曼编码中的二进制前缀编码
3
- Kadaj13
2
我猜最好的方法是证明任何非满树都会导致非最优代码，但是自从我做过那种事以来已经很长时间了...然而这并不是真正的编程问题，所以有点离题了... - twalberg
@twalberg 我认为有一种更简单的方法来证明这个问题。请看一下我的答案，并评论是否正确。 - Nikunj Banka
2个回答
2
任何二进制数据代码都可以表示为二叉树。该代码由从根到叶子的路径表示，左边的边表示前缀中的0，右边的边表示1（或反之亦然）。
请记住，对于每个符号，都有一个叶节点。
为了证明最优代码将被表示为完全二叉树，让我们回顾一下什么是完全二叉树，它是一棵树，其中每个节点要么是叶子节点，要么有两个孩子。
假设某个代码是最优的，并且由非完全树表示。因此，存在一个仅具有单个子节点v的某个顶点u。连接u和v之间的边将位x添加到以v为根的子树中符号（在叶子节点处）的前缀代码中。从这棵树中，我可以删除x边，并用v替换u，从而减少以v为根的子树中所有符号的前缀代码长度一位。这会减少至少一个符号的表示中的位数（当v是单例节点时）。
这表明，该树实际上并未表示出最优代码，我的前提是错误的。从而证明引理。
请记住，对于每个符号，都有一个叶节点。
为了证明最优代码将被表示为完全二叉树，让我们回顾一下什么是完全二叉树，它是一棵树，其中每个节点要么是叶子节点，要么有两个孩子。
假设某个代码是最优的，并且由非完全树表示。因此，存在一个仅具有单个子节点v的某个顶点u。连接u和v之间的边将位x添加到以v为根的子树中符号（在叶子节点处）的前缀代码中。从这棵树中，我可以删除x边，并用v替换u，从而减少以v为根的子树中所有符号的前缀代码长度一位。这会减少至少一个符号的表示中的位数（当v是单例节点时）。
这表明，该树实际上并未表示出最优代码，我的前提是错误的。从而证明引理。
- shebang
1
来自wikipedia，
完全二叉树（有时称为2叉树或严格二叉树）是一种树，其中除了叶子节点之外的每个节点都有两个子节点。
Huffman编码树的构建方式一定会产生一个完全二叉树。因为在算法的每一步中，我们从队列中移除具有最高优先级（最低概率）的两个节点，并使用这两个节点作为子节点创建一个新的内部节点。
- Nikunj Banka
1
@twalberg无论树的平衡程度如何，对于定义一棵是否为满二叉树并不重要。因为即使在这种情况下，所有非叶节点都有两个子节点。 - Nikunj Banka
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接