基本概念
WPL（樹的帶權路徑長度）
若給具有m個葉結點的二叉樹的每個葉結點賦予一個權值，則該二叉樹的帶權路徑長度定義為:
其中，wi為第i個葉結點被賦予的權值，li為第i個葉結點的路徑長度；例子如下：
哈夫曼樹的定義
給定一組權值，構造出的具有最小帶權路徑長度的二叉樹稱為哈夫曼樹，如下：
哈夫曼樹的特點
哈夫曼樹具有如下特點：
1、權值越大的葉結點離根結點越近，權值越小的葉結點離根結點越遠；（這樣的二叉樹WPL最小）
2、無度為1的結點；
3、哈夫曼樹不是惟一的。
哈夫曼樹的構造
哈夫曼樹構造的核心思想如下：
1、對于給定的權值W={w1,w2,…, wm}，構造出樹林F={T1,T2,…, Tm}，其中，Ti(1≤i≤m)為左、右子樹為空，且根結點(葉結點)的權值為wi的二叉樹；
2、将F中根結點權值最小的兩棵二叉樹合并成為一棵新的二叉樹，即把這兩棵二叉樹分别作為新的二叉樹的左、右子樹，并令新的二叉樹的根結點權值為這兩棵二叉樹的根結點的權值之和，将新的二叉樹加入F的同時從F中删除這兩棵二叉樹；
3、重複步驟2，直到F中隻有一棵二叉樹。
例子如下：
哈夫曼編碼