如何生成霍夫曼前缀码？

Question

我和我的小组正在开发一个 c++ 程序，但我无法弄清楚如何使用 inOrder 遍历生成前缀代码的逻辑。我们已经构建了 PrefixCode 树，我们想从中生成代码。

由于我们的逻辑有问题，我不知道是否需要提供任何代码。如果你需要任何让我知道。

谢谢。

Answer 1

如评论所述，我不确定是否理解。买我试试...

首先，我假设您已经正确构建了树。

其次，每片叶子都包含一个要编码的符号。每个符号的代码由从根到叶子的路径定义。最初，当您处于根目录时，代码是空的。如果您向左移动，则将 0 连接到代码。对称地，如果你向右走，那么你就连接了 1。

第三，我假设您想要对列表 <symbol, code>。 symbol 是一个字符，code 是一个包含前缀代码的字符串。结果是树表示的所有符号及其代码的列表。

现在，生成该列表的算法将使用堆栈来存储从根到当前节点的前缀。每次到达叶子时，代码都会进入堆栈，但会反转。这样的算法可以如下：

void codes(Node * root, stack<char> & s)
{
  if (is_leaf(root))
    {
      auto symbol = // symbol stored in the node
      string code = // the reversed stack content; that is the code of current leaf
      cout << symbol << " = " << code << endl;
    }

  s.push('0');
  codes(LLINK(root), s);
  s.pop();

  s.push('1');
  codes(RLINK(root), s);
  s.pop();
}

我提出栈是因为"natural"数据结构用于存储从根到节点的部分路径。但是，也许 vector<char> 会更好。在这种情况下，您应该将 push() 替换为 push_back()，将 pop() 替换为 pop_back()。但优点是您可以使用反向迭代器构建代码。

此外，您可以使用列表或向量来代替指令 cout ...，并在其中插入对。之后，如果您愿意，可以对其进行排序。或者，您可以使用 "naturally sorted" 数据结构，例如二叉搜索树，并且避免排序。如果您有兴趣，所有这些当然是生成按符号排序的输出。

希望对您有所帮助

如何生成霍夫曼前缀码？

How to generate Huffman prefix code?

c++

prefix-tree

huffman-code