哈夫曼樹一定是完全二叉樹嗎

哈夫曼樹不一定是完全二叉樹。哈夫曼樹是帶權路徑長度達到最小的二叉樹，也叫做最優二叉樹，不一定是完全二叉樹，也不一定是平衡二叉樹。哈夫曼樹也可以是k叉的，只是在構造k叉哈夫曼樹時需要先進行一些調整。

構造哈夫曼樹的思想是每次選k個權重最小的元素來合成一個新的元素，該元素權重為k個元素權重之和。但是當k大於2時，按照這個步驟做下去可能到最後剩下的元素少於k個。解決這個問題的辦法是假設已經有了一棵哈夫曼樹(且為一棵滿k叉樹)，則可以計算出其葉節點數目為(k-1)nk+1,式子中的nk表示子節點數目為k的節點數目。於是對給定的n個權值構造k叉哈夫曼樹時,可以先考慮增加一些權值為0的葉子節點，使得葉子節點總數為(k-1)nk+1這種形式,然後再按照哈夫曼樹的方法進行構造即可。

哈夫曼碼樹的解壓縮就是將得到的前置碼轉換回符號，通常藉由樹的追蹤，將接收到的位元串一步一步還原。但是要追蹤樹之前，必須要先重建哈夫曼樹；某些情況下，如果每個符號的權重可以被事先預測，那麼哈夫曼樹就可以預先重建，並且儲存並重復使用，否則，傳送端必須預先發送哈夫曼樹的相關資訊給接收端。