從分鐘C++創建霍夫曼代碼樹

Question

假設您有一個C++程序，必須從給定的.txt文件中讀取文本。該程序將：

• 文件中的每個字符，然後每個唯一字符（和它的頻率）的出現計算數目將被存儲爲一個新的樹節點
• 然後，程序將生成一個包含一個最小堆這些節點，然後使用這個最小堆構建霍夫曼代碼樹。
• 遍歷（預購和按順序）將被寫入輸出文件。樹的每個內部節點都將具有標籤I：xxx，其中xxx是int標籤，並且葉子具有L：xxx
• 程序最終構造一個表，其中包含每個節點的編碼（基於ASCII，不是真正的.bin版本）作爲字符串存儲

角色，我想我會霍夫曼類中的每個節點存儲這樣的：

struct CharNode { 

     char value; 
     int frequency; 
     bool internal; 
     int label; 
     CharNode *parent; 
     CharNode *left_child; 
     CharNode *right_child; 
}; 

我不完全知道從哪裏着手。任何幫助將非常感激！

Answer 1

首先使用一個數組，該數組的長度足以讓您的應用程序能識別每個字符。現在檢查字符串，對與它們的ASCII值對應的數組元素進行增量。 （您可能需要減去初始ASCII值的某個基本量，因此您可以從第一個數組元素開始計算'a'）

這部分也可以在C中輕鬆完成，因爲它使用字符和整數作爲等值。

完成後，您將所有字符都顯示爲出現次數。現在，一旦開始構建樹節點，就可以遍歷數組。並在該樹上使用堆算法。

或者只是對數組進行排序，然後從這裏開始構建樹。

祝您好運，快樂編碼:)