霍夫曼二叉树是否必须正确？

Question

我可以找到霍夫曼编码的所有例子都有数量的字符可以使用。如果它是奇数个字符，最后添加到树的内部节点是否只有一个孩子？或者我必须添加某种类型的NULL节点，以便所有内部节点都有两个孩子？

如果是后者，它似乎令人困惑，因为我不知道你将如何有一个字符的NULL值（因为所有的值都被用作有效的ASCII码）。

Answer 1

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

/\ 
/\ 
a × 
    /\ 
    b c 

树的构造方式确保所有的内部节点有两个孩子，无论char S如何多有。

从叶子列表开始，然后在每个步骤中，（频率最低的）两棵树通过将它们作为左侧树结合起来。一个新的 - 然后是内部节点的右子树，直到只剩下一棵树。最终结果中的每个内部节点都来自加入两棵子树，因此有两个子树。