c++ - 在记住路径的同时进行高效的霍夫曼树搜索

Question

作为与我关于存储霍夫曼树的有效方法的问题相关的后续问题，我想知道搜索二叉树（基于霍夫曼编码输出）和存储到特定节点的路径的最快和最有效的方法是什么.

这是我目前拥有的：

• 将根节点加入队列
• 当队列不为空时，将项目从队列中弹出
  • 检查它是否是我们正在寻找的
    • 是的：跟随一个头指针回到根节点，而在每个节点上我们访问检查它是左还是右并记下它。
    • 跳出搜索
  • 将左右节点入队

由于这是一棵霍夫曼树，我正在寻找的所有条目都将存在。以上是广度优先搜索，这被认为是霍夫曼树的最佳选择，因为源中的项目更频繁地在树中较高以获得更好的压缩，但是我无法找到跟踪的好方法我们如何使用我放在节点中的头指针不回溯就到达特定节点。

在这种情况下，我还以相反的顺序获取所有右/左路径，例如，如果我们从头到根，我们发现从根开始是右、左、左，我们得到左， 左右。或二进制的 001 ，当我正在寻找的是以有效的方式获得 100 时。

还建议将从根到节点的路径存储为节点内的单独值，但是如果我们有一个大于我们为此目的创建的变量可以容纳的位数的树，那么这将崩溃，并且在那点存储数据也会占用大量内存。

Answer 1

创建一个值 -> 位串的字典，这将为您提供最快的查找。

如果这些值的大小是已知的，那么您可能只需要一个位字符串数组并通过它们的索引来查找这些值。

Answer 2

If you're decoding Huffman-encoded data one bit at a time, your performance will be poor. As much as you'd like to avoid using lookup tables, that's the only way to go if you care about performance. The way Huffman codes are created, they are left-to-right unique and lend themselves perfectly to a fast table lookup.