c++ - 高效的霍夫曼树搜索，同时记住所走的路径

Question

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

这是我目前拥有的:

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

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

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

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

Answer 1

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

如果值的大小已知，您可能只需要一个位串数组并通过索引查找值。