高效的霍夫曼樹搜索，同時記住路徑

Question

作爲與我的question regarding efficient way of storing huffman tree's有關的後續問題，我想知道什麼是最快和最有效的搜索二叉樹（基於霍夫曼編碼輸出）和存儲所採取的路徑到特定節點。

這是我目前有：

• 添加根節點排隊
• 而隊列不爲空，彈出項關閉隊列
  • 檢查，如果它是什麼，我們正在尋找
    • 是： 將一個頭指針返回到根節點，而在我們訪問的每個節點上檢查它是左或右，並製作一個注意它。
    • 打出來的搜索
  • 排隊左，右節點

由於這是一個哈夫曼樹，所有我要找會存在的條目。以上是廣度優先搜索，它被認爲是霍夫曼樹最好的搜索，因爲源代碼中的項目經常在樹中更高，以獲得更好的壓縮效果，但是我無法找到一種跟蹤我們如何通過使用我放入節點的頭指針進行回溯來訪問特定節點。

在這種情況下，我也以相反的順序獲得所有的右/左路徑，例如，如果我們按照頭部到根，並且我們從根中發現它是右，左，左，我們左，左，右。或二進制001，當我正在尋找的是以有效的方式獲得100。

還建議存儲從根節點到節點的路徑作爲節點內部的單獨值，但是如果我們有一棵樹大於我們爲此目的創建的變量可能容納的很多位，那時存儲數據也會佔用大量的內存。

Answer 1

創建一個有價值的字典 - >位串，這會給你最快的查找。

如果這些值是一個已知大小，那麼您可能只需要一串比特串就可以通過它們的索引查找值。

Answer 2

如果你一次一個位地解碼霍夫曼編碼數據，你的性能會很差。儘可能避免使用查找表，如果您關心性能，這是唯一的途徑。霍夫曼代碼的創建方式，它們是從左到右的獨特之處，完美適用於快速查表。