algorithm - 哈夫曼码的全二叉树有什么优势？

Question

我正在研究用于对字符流进行位编码的霍夫曼代码，并了解到最佳代码将由一棵完整的二叉树表示，其中每个不同的字符由一个叶子表示，并且所有内部节点都恰好包含两个子节点。

我想知道为什么满二叉树是这里的最佳选择？换句话说，这里全二叉树的优势是什么？

Answer 1

这不是选择，而是等价。

最优霍夫曼码由有限状态机解码，其中

• 每个状态恰好有两个导出(下一位是0或1)
• 每个州只有一个条目
• 所有包含输出符号的状态都是停止状态，和
• 所有停止状态都包含输出符号

这相当于一个搜索树，其中

• 所有内部节点恰好有两个 child
• 所有节点只有一个父节点
• 所有包含输出符号的节点都是叶节点，和
• 所有叶节点都包含输出符号

也有非最优霍夫曼代码，它们的停止状态/叶节点不包含输出符号。这样的二叉树不会完整。