哈夫曼樹權值是什麼?

哈夫曼樹中的“權值”是指什麼

權值，是數學領域中的詞，指加權平均數中的每個數的頻數。

比如下列字符串：

aabbccad

a出現頻數為3次，b 2 c 2 d 1

哈夫曼樹中，就可以用權值3表示a出現次數， 權值2表示b出現次數。。。。

這樣根據這個權值可以做出哈夫曼樹

數據結構 建立一棵哈夫曼樹，權值分別為 1 2 3 4 5生成的樹是什麼樣子的，根節點權值應該是

哈夫曼樹:

15

/ \

6 9

/ \ / \

3 3 4 5

/ \

1 2

根節點權值 15

C++: 由n個權值構成的哈夫曼樹共有( )個結點。 需要說明下怎麼算的

n個權值構成的Huffman樹一共有2n-1個結點

因為根據二叉樹的性質，度為0的葉子結點個數總是比度為2結點多1個，而且Huffman樹沒有度為1的結點，權值都在葉子上，因此即可得到結論

只要權值最小是不是就是哈夫曼樹

你的問題，這裡的權值最小是指帶權路徑長度吧？權值和是固定的，無所謂最小不最小。

樹的帶權路徑最小的不一定是哈夫曼樹，可能其他情況構造出來的樹也可能權值跟哈夫曼樹一樣大，只能證明哈夫曼樹的是最優的二叉樹。

我舉一個例子，權值序列 4 5 6 7,構造瞭如下樹

22

/ \

10 12

/ \ / \

4 6 5 7

按照哈夫曼樹構造方法，選擇兩個最小的權值點進行構造，選擇4和5構造一顆樹，6和7構造一顆樹。顯然上面的二叉樹WPL跟哈夫曼構造出來的二叉樹WPL是一樣大的。

所以結論：不是。

另外補充，歷史上，霍夫曼和他在MIT信息論的同學需要選擇是完成學期報告還是期末考試。導師Robert M. Fano給他們的學期報告的題目是，查找最有效的二進制編碼。由於無法證明哪個已有編碼是最有效的，霍夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二叉樹編碼的想法，並很快證明了這個方法是最有效的。

以克勞德·香農和範諾-羅伯特命名的香農-範諾編碼，在理想意義上，它與哈夫曼編碼一樣。