努力解决这个练习面试问题。感谢所有帮助

Question

霍夫曼编码是一种基于频率对字符进行编码的方法。每个字母都被分配了一个可变长度的二进制字符串，例如0101或111110，其中较短的长度对应于更常见的字母。为了实现这一点，构建了一棵二进制树，使得从根到任何叶子的路径唯一地映射到一个字符。当遍历路径时，下降到左子项对应于前缀中的0，而下降到右子项对应于1。

下面是一个示例树（请注意，只有叶节点有字母）：

        *
      /   \
    *       *
   / \     / \
  *   a   t   *
 /             \
c               s

使用这种编码，猫将被表示为0000110111。

给定一个字符频率字典，构建一个霍夫曼树，并使用它来确定字符及其编码的二进制字符串之间的映射。

Answer 1

输入是唯一字符及其出现频率的数组，输出是霍夫曼树。

>

为每个唯一字符创建一个叶节点，并构建所有叶节点的最小堆（最小堆用作优先级队列。频率字段的值用于比较最小堆中的两个节点。最初，频率最低的字符位于根）

从最小堆中提取两个频率最小的节点。

创建一个新的内部节点，其频率等于两个节点频率之和。将第一个提取的节点作为其左子节点，将另一个提取的节点作为其右子节点。将此节点添加到最小堆。

重复步骤#2和#3，直到堆只包含一个节点。剩下的节点是根节点，树是完整的。

请看这个教程，这里描述了一步一步的构建树过程。