对于Ternary Huffman问题，我们可以为“4”字符制作树（或编码方案）吗？

Question

对于Ternary Huffman问题，我们可以为“4”字符制作一个树（或编码方案）吗？“我说这些频率有4个字符：freq（a）= 5 freq（b）= 3 freq（c）= 2 freq （d）= 2

我将如何以0,1,2的形式对它们进行编码，使得没有代码字是另一个代码字的前缀？

Answer 1

对于经典的霍夫曼来说，你只需要一次合并2个最低频率的节点来构建一个树，当分配1到左（或右）边缘和0到其他边缘时，dfs到某个节点的路径是节点代码。

即

所以在这种情况下编码是：

a - 1 b - 01 c - 001 d - 000

在三元霍夫曼中，您一次只加入节点3个最低频率（如果最后一步节点不够，则节点数量减少）

即

所以在这种情况下编码是：

a2 b - 12 c - 11 d - 10