对霍夫曼树感到困惑.在上面的链接的末尾附近,它显示剩下2个元素的树,然后是完成的树.我对它的分支方式感到困惑.霍夫曼树需要分支的特定方式吗？
例如,57:*及其右子35:*分支到右侧.它可能是35分支到左边,22分支到右边？另外,为什么不是22:*与15:4配对 - 它只是与20:5配对以创建一棵新树.
从最初的观察看来,除了叶子的频率加起来父节点的值之外,树似乎不需要平衡或具有任何特定顺序.创建具有相同数据的霍夫曼树的两个人最终会得到不同的编码值吗？
到目前为止,这些帖子是错误的和误导性的:选择具有相同权重的叶子确实很重要,它们确实会改变它们压缩数据的程度.
这是一个反例,演示了不同的选择如何导致不同的压缩率:ABBBCCCDDDDEEEEEEEE
A:1,B:3,C:3,D:4,E:8.第一步:取A和B组成一个重量为4的节点.第二步:
如果您在第一步中使用C获取新创建的节点,那么您将获得
(19 (11 (7 (4 (1-A) (3-B)) (3-C)) (4-D)) (8-E))37位压缩数据.
另一方面,如果你使用权重为4的D而不是新创建的节点,则得到
(19 (11 (4 (1-A) (3-B)) (7 (3-C) (4-D))) (8-E))41位压缩数据.
哈夫曼树的关键是：
按频率对这个列表进行排序，并将最低的两个元素变成叶子
如果您有两个以上频率最低的元素（例如 3,4,4...），任何两个都可以（3 和 4 中的任何一个 - 不是两个 4）。此外，这些最低元素中的哪个被分配为 0 和哪个为 1 并不重要。这两个事实允许从相同的数据中产生不同但有效的霍夫曼编码。
霍夫曼树应该通过频率而不是节点数来平衡。因此，以下是平衡的：
(100 (50 (25 (12 (12 1)))))
这不是：
(((100 50) 25) ((12 12) 1)))
特别是在您的问题中，15 与 20 配对而不是 22，因为 15 和 20 是两个最低的剩余值（均小于 22）。分支（左或右）都可以，只要它是一致的（在同一算法中总是较小的左，或总是较小的右，以便可以在另一端重建编码）。