霍夫曼二叉樹是否必須正確？

Question

我可以找到霍夫曼編碼的所有例子都有數量的字符可以使用。如果它是奇數個字符，最後添加到樹的內部節點是否只有一個孩子？或者我必須添加某種類型的NULL節點，以便所有內部節點都有兩個孩子？

如果是後者，它似乎令人困惑，因爲我不知道你將如何有一個字符的NULL值（因爲所有的值都被用作有效的ASCII碼）。

Answer 1

奇數char s是沒有問題的。但是這不會導致只有一個孩子的內部節點。

/\ 
/\ 
a × 
    /\ 
    b c 

樹的構造方式確保所有的內部節點有兩個孩子，無論char S如何多有。

從葉子列表開始，然後在每個步驟中，（頻率最低的）兩棵樹通過將它們作爲左側樹結合起來。一個新的 - 然後是內部節點的右子樹，直到只剩下一棵樹。最終結果中的每個內部節點都來自加入兩棵子樹，因此有兩個子樹。