如何遍歷霍夫曼樹以遞歸搜索特定元素？ - C

我正在哈夫曼代碼中工作，目前我正處於編碼/解碼文本文件到二進制文件的階段。我有這樣的一段代碼及其所有相關數據（文字，frecuency，路線）沿檢索來自樹上的一個節點：如何遍歷霍夫曼樹以遞歸搜索特定元素？ - C

EmptyString (string); 
while ((c = fgetc (nameTextFile)) != EOF) { 
    nodeHuffmanTree = SearchHuffmanTree (rootHuffmanTree, c); 
    strcpy (string, nodeHuffmanTree -> route); 
    Encode (nameBinaryFile, string); 
    EmptyString (string); 
}

假設對每個節點的路由（0和1）已經已生成。我想要的SearchHuffmanTree函數是，給定一個字符，它在霍夫曼樹中搜索所述字符，並返回包含它的節點。這是相關的，因爲該節點將包含編碼函數將轉換爲字節的路由。

我知道我不能像二叉搜索樹一樣對待哈夫曼樹，因爲它沒有共享相同的特徵，所以如果我想要搜索特定的角色，我將不得不遍歷整個樹。

我已經尋找替代品而不使用遞歸（在一些堆棧中），儘管它們更容易理解，但它們產生的代碼更簡單，更簡潔，所以我更喜歡使用遞歸的解決方案。

我已經想出了編碼/解碼部分，所以這幾乎是最終完成我的代碼的最後一步。期待任何幫助，你可以給我。

來源

2015-12-22 ShadowGeist

提示：查看根節點，然後查看左側子樹，然後查看右側子樹。 – immibis

@immibis你的意思是遍歷整個樹預訂，訂單或郵購？我已經試過了，但是函數似乎沒有用我正在查找的字符檢索節點，而是程序停止工作。也許有一些我一直在做錯，但我不明白爲什麼。我可以編輯添加我想出來的問題，或許你可以指出我出錯的地方。 – ShadowGeist

構建Huffman樹之後，應該使用它來創建一個編碼數組，它只是一個256個結構的數組，其中每個結構都包含一個位模式和一個長度。這樣，輸入字符可以用作數組中的索引進行快速查找。 – user3386109

是的，因爲節點的位置取決於字符的頻率而不取決於它們的值，所以不能假設樹中任何特定節點（即字符）的位置。因此，你必須找到一種遍歷整個樹的方式，而不作任何假設。

有兩種遍歷圖的方法：基於隊列的廣度優先搜索（BFS）和基於堆棧的深度優先搜索（DFS）。

由於DFS基於堆棧，因此它是一個固有的遞歸問題。而且，由於2種方法遍歷樹的方式不同，因此您的情況下DFS的平均效率會更高。

DFS如何工作？

那麼，基本的原則是，如果一個節點不是一片葉子，就對它的每個孩子執行一個DFS。如果您選擇遍歷子樹的順序，則可以首先採用最高概率路徑，這會增加更快找到結果的機率。

下面是該算法的一個簡單的僞代碼：

DFS(node T, char x) { 
    if (T is leaf) 
     if (T == x) 
      return found 
     else 
      return not found 
    else 
     foreach child of T 
      if DFS(child, x) == found 
       return found 
     return not found

你可以找到DFS維基百科頁面上的更多細節。

來源

2015-12-22 01:24:02 Paul92

此解決方案是否避免使用其他數據結構？我已經使用堆棧爲樹中的每個節點（堆棧使用char數組）生成路由。我有點想避免使用第二個堆棧來存儲其他類型的元素。 – ShadowGeist

是的，它的確如此。你可以使用遞歸棧，你不必實現它。實際上，我正在使用它顯示的僞代碼。 – Paul92

只是一個問題。該僞代碼是針對通用樹的。我如何將T'的foreach孩子的部分翻譯成我的具有兩個孩子的樹的特殊情況？ – ShadowGeist

如何遍歷霍夫曼樹以遞歸搜索特定元素？ - C

回答

相關問題