哈夫曼樹是二叉樹嗎

哈夫曼樹不一定是二叉樹，也有可能有度為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這種形式，然後再按照哈夫曼樹的方法進行構造即可。