高效的霍夫曼树搜索，同时记住所采取的路径

Question

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

这就是我目前所拥有的：

• 将根节点添加到队列中
• 当队列不为空时，将项目从队列中弹出
  • 检查这是否是我们正在寻找的
    • 是的：沿着头指针回到根节点，同时在每个节点上我们访问检查它是左节点还是右节点并记录下来。
    • 摆脱搜索
  • 将左右节点入队

由于这是一棵霍夫曼树，因此我正在查找的所有条目都将存在。上面是广度优先搜索，这被认为是霍夫曼树的最佳搜索，因为源中经常出现的项目在树中的位置较高，以获得更好的压缩，但是我找不到一种好方法来跟踪我们如何使用我放入节点中的头指针在不回溯的情况下到达特定节点。

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

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

Answer 1

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

如果这些值的大小已知，您可能只需使用一个位字符串数组即可通过它们的索引查找这些值。

Answer 2

如果您一次一位地解码霍夫曼编码的数据，您的性能将会很差。尽管您希望避免使用查找表，但如果您关心性能，这是唯一的方法。霍夫曼代码的创建方式从左到右都是唯一的，非常适合快速表查找。