0

我能找到的所有霍夫曼编码示例都有偶数个字符可供使用。如果是奇数个字符,添加到树中的最后一个内部节点是否只有一个子节点?或者我是否必须添加某种 NULL 节点,以便所有内部节点都有 2 个子节点?

如果是后者,这似乎令人困惑,因为我不确定您如何为 char 设置 NULL 值(因为所有值都被用作有效的 ASCII 代码)。

4

1 回答 1

2

奇数个chars 没问题。但这不会导致只有一个孩子的内部节点。

  /\
 /  \
a    ×
    / \
   b   c

树的构造方式确保所有内部节点都有两个孩子,无论有多少chars。

一个从叶子列表开始,然后在每一步中,将频率最低的两棵树连接起来,使它们分别成为左侧。一个新的 - 然后是内部 - 节点的右子树,直到只剩下一棵树。最终结果中的每个内部节点都来自连接两个子树,因此有两个孩子。

于 2013-05-08T21:39:06.113 回答