Huffman樹

Huffman樹,是有Huffman提出的Huffman算法的名稱，該算法由Huffman最早提出，並帶有規律性。

那么如何構造Huffman樹呢？Huffman最早給出了一個帶有規律的算法，俗稱Huffman算法：
1）將n個帶權值wi（i≤n）的結點構成n棵二叉樹的集合T={T1，T2，……，Tn}，每棵二叉樹只有一個根結點，其左右子樹均為空；
2）在T中選取兩個權值最小的結點作為左右子樹，構成一個新的二叉樹，其根結點的權值取左右子樹權值之和；
3）在T中刪除這兩棵樹，將新構成的樹加入到T中；
4）重複2）、3）步的操作，直到T中只含一棵樹為止，該樹就是Huffman樹。