赫夫曼樹

假設有n 假設有n 個權值，則構造出的赫夫曼樹有n

假設有n個權值{w1，w2，w3，……wn}，試構造一棵具有n個葉子節點的二叉樹，每個葉子結點帶權為wi，則其中帶權路徑長度WPL最小的二叉樹稱作最優二叉樹或赫夫曼樹或哈夫曼樹
構造赫夫曼樹：
假設有n個權值，則構造出的赫夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則赫夫曼樹的構造規則為：　
(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；　
(2) 在森林中選出兩個根結點的權值最小的樹合併，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；　
(3)從森林中刪除選取的兩棵樹，並將新樹加入森林；　
(4)重複(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的赫夫曼樹。