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

Question

作为与我的question regarding efficient way of storing huffman tree's有关的后续问题，我想知道什么是最快和最有效的搜索二叉树（基于霍夫曼编码输出）和存储所采取的路径到特定节点。

这是我目前有：

• 添加根节点排队
• 而队列不为空，弹出项关闭队列
  • 检查，如果它是什么，我们正在寻找
    • 是： 将一个头指针返回到根节点，而在我们访问的每个节点上检查它是左或右，并制作一个注意它。
    • 打出来的搜索
  • 排队左，右节点

由于这是一个哈夫曼树，所有我要找会存在的条目。以上是广度优先搜索，它被认为是霍夫曼树最好的搜索，因为源代码中的项目经常在树中更高，以获得更好的压缩效果，但是我无法找到一种跟踪我们如何通过使用我放入节点的头指针进行回溯来访问特定节点。

在这种情况下，我也以相反的顺序获得所有的右/左路径，例如，如果我们按照头部到根，并且我们从根中发现它是右，左，左，我们左，左，右。或二进制001，当我正在寻找的是以有效的方式获得100。

还建议存储从根节点到节点的路径作为节点内部的单独值，但是如果我们有一棵树大于我们为此目的创建的变量可能容纳的很多位，那时存储数据也会占用大量的内存。

Answer 1

创建一个有价值的字典 - >位串，这会给你最快的查找。

如果这些值是一个已知大小，那么您可能只需要一串比特串就可以通过它们的索引查找值。

Answer 2

如果你一次一个位地解码霍夫曼编码数据，你的性能会很差。尽可能避免使用查找表，如果您关心性能，这是唯一的途径。霍夫曼代码的创建方式，它们是从左到右的独特之处，完美适用于快速查表。