从最小堆C创建哈夫曼代码树

Question

假设你有一个C程序，它必须从给定的文本中读取。txt文件。该计划将：

• 计算文件中每个字符的出现次数，然后每个唯一字符（及其频率）将存储为一个新的树节点
• 然后，程序构建包含这些节点的最小堆，然后使用该最小堆构建哈夫曼代码树
• 遍历（pre order和in order）将写入输出文件。树的每个内部节点都有标签I:xxx，其中xxx是int标签，叶子有L:xxx
• 该程序最后构造一个表，其中包含存储为字符串的每个字符的编码（基于ASCII的，非true.bin版本）

我想我会将每个节点存储在哈夫曼类中，如下所示：

struct CharNode {

      char value;
      int frequency;
      bool internal;
      int label;
      CharNode *parent;
      CharNode *left_child;
      CharNode *right_child;
};

我不太确定该怎么办。任何帮助都将不胜感激！

Answer 1

首先使用一个数组，该数组足够长，应用程序应该识别的每个字符都有一个元素。现在遍历字符串，增加与其ASCII值对应的数组元素。（您可能需要减去初始ASCII值的某个基数，因此您开始计算“a”的第一个数组元素）

这一部分也可以在C中轻松完成，因为它使用char和int作为等价项。

完成后，您将拥有所有字符及其出现次数。现在您可以在开始构建树节点时遍历数组。并在该树上使用您的堆算法。

或者对数组进行排序，然后从那里开始构建树。

祝你好运，快乐编码：）