遍歷霍夫曼樹

Question

所以目前我有一個程序創建一個霍夫曼樹。樹由這些字段組成的「Hnodes」組成：右（指向右邊的孩子）左邊（指向左邊的孩子）代碼（整數串，理想情況下是0和1，它是該節點的霍夫曼編碼）character（包含在節點中的字符）。

我已經通過添加鏈接列表中的節點創建了霍夫曼樹 - 我知道該樹已正確創建。當我創建樹時，我告訴節點何時給它一個父節點，如果它是父節點的「正確」，那麼它的代碼字符串爲1，如果爲0，但顯然在創建完整個樹之後，每個節點都是隻會有一個0或1，但不是像00100101這樣的字符串。我的問題是，現在我有這棵樹，我可以遍歷它嗎？我理解的想法是給每個孩子父母的代碼+孩子自己的代碼，但我不知道如何循環通過樹來完成這一點。

預先感謝您。

Answer 1

也許這樣？

ExpandBinaryPaths(node, prefix) 
    1. if node is null then return 
    2. else then 
    3. node.binary = prefix concat node.binary 
    4. ExpandBinaryPaths(node.left, node.binary) 
    5. ExpandBinaryPaths(node.right, node.binary) 
    6. return 

這個想法是你可以在沒有前綴的根上調用它... ExpandBinaryPaths（root，「」）。