huffman-code - 霍夫曼树构造如何在左右两侧有元素

Question

我正在尝试从某些频率创建一个霍夫曼代码。我知道该怎么做，但我只有一个困惑，即我们将在哪一侧（左侧或右侧？）放置哪个元素。

我的意思是我对霍夫曼树的想法是-（1）首先，我们按降序对所有频率进行排序。(2)取最小的两个并合并。**但我不明白这两个频率中的哪个会向右，哪个会向左**，我知道在右侧我们有“0”，而右侧我们有“1”。但是我不知道哪个频率应该保持在右边或左边。我们这样做的依据是什么？

Answer 1

您可以将子节点放在左侧或右侧，这对整体解决方案无关紧要。我们只会看到长度，而不是这些值 0 和 1。

Answer 2

由于我不完全理解你的问题，我会给你一个霍夫曼编码的简单例子：

A: 0.5
B: 0.1
C: 0.2
D: 0.15
E: 0.05

现在按频率降序排列：

A: 0.5
C: 0.2
D: 0.15
B: 0.1
E: 0.05

现在我们结合底​​部的两个：

A: 0.5
C: 0.2
D: 0.15
B+E: 0.15

我们继续这样做，直到我们有一个完全的二叉树。在此示例中： A = 0, C = 10, D = 110, B = 1110, E = 11110 只要您的解压缩器知道如何读取它，我们选择以 0 或 1 继续树并不重要。