哈夫曼樹是二叉樹嗎

哈夫曼樹不一定是二叉樹，也有可能有度爲m的哈弗曼樹，度爲m的哈弗曼樹只有度爲m的結點和度爲0的結點。給定N個權值作爲N個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹爲最優二叉樹，也稱爲哈夫曼樹。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。

多叉哈夫曼樹

哈夫曼樹也可以是k叉的，只是在構造k叉哈夫曼樹時需要先進行一些調整。構造哈夫曼樹的思想是每次選k個權重最小的元素來合成一個新的元素，該元素權重爲k個元素權重之和。但是當k大於2時，按照這個步驟做下去可能到最後剩下的元素少於k個。

解決這個問題的辦法是假設已經有了一棵哈夫曼樹，則可以計算出其葉節點數目爲(k-1)nk+1，式子中的nk表示子節點數目爲k的節點數目。於是對給定的n個權值構造k叉哈夫曼樹時，可以先考慮增加一些權值爲0的葉子節點，使得葉子節點總數爲(k-1)nk+1這種形式，然後再按照哈夫曼樹的方法進行構造即可。