一、概念
樹的路徑長度：樹的路徑長度是從樹根到樹中每一結點的路徑長度之和。在結點數目相同的二叉樹中，完全二叉樹的路徑長度最短。 結點的權：在一些應用中，賦予樹中結點的一個有某種意義的實數。 結點的帶權路徑長度：結點到樹根之間的路徑長度與該結點上權的乘積。 樹的帶權路徑長度(Weighted Path Length of Tree)：定義為樹中所有葉結點的帶權路徑長度之和，通常記為：
其中：
n表示葉子結點的數目
wi和li分别表示葉結點ki的權值和根到結點ki之間的路徑長度。
樹的帶權路徑長度亦稱為樹的代價。
哈夫曼樹或最優二叉樹：在權為wl，w2，…，wn的n個葉子所構成的所有二叉樹中，帶權路徑長度最小(即代價最小)的二叉樹稱為哈夫曼樹或最優二叉樹。
【例】給定4個葉子結點a，b，c和d，分别帶權7，5，2和4。構造如下圖所示的三棵二叉樹(還有許多棵)，它們的帶權路徑長度分别為：
(a)WPL=7*2+5*2+2*2+4*2=36
(b)WPL=7*3+5*3+2*1+4*2=46
(c)WPL=7*1+5*2+2*3+4*3=35
其中(c)樹的WPL最小，可以驗證，它就是哈夫曼樹。
注意： ① 葉子上的權值均相同時，完全二叉樹一定是最優二叉樹，否則完全二叉樹不一定是最優二叉樹。 ② 最優二叉樹中，權越大的葉子離根越近。 ③ 最優二叉樹的形态不唯一，WPL最小。
二、構造最優二叉樹
哈夫曼算法經常用來解決編碼方面的問題，運用這種方式的編碼我們稱做哈夫曼編碼，它是一種變長編碼，其優點是可以根據字元出現的不同頻率來節省空間。假設給定8個葉子結點Z、K、F、C、U、D、L、E，分别帶權2、7、24、32、37、42、42、120，我們來看看這組數的哈夫曼編碼過程。
最終的哈夫曼樹，我們加入編碼後的效果如下圖：
字首特性：一組編碼中，其他任何字元的編碼都不是某個字元編碼的字首。 DEED的編碼: 10100101 1011001110111101的解碼: DUCK 每個字元的平均編碼位數：Σ(ci*fi) / fT= 785 / 306 = 2.56536
三、哈夫曼算法
哈夫曼首先給出了對于給定的葉子數目及其權值構造最優二叉樹的方法，故稱其為哈夫曼算法。其基本思想是： (1)根據給定的n個權值wl，w2，…，wn構成n棵二叉樹的森林F={T1，T2，…，Tn}，其中每棵二叉樹Ti中都隻有一個權值為wi的根結點，其左右子樹均空。 (2)在森林F中選出兩棵根結點權值最小的樹(當這樣的樹不止兩棵樹時，可以從中任選兩棵)，将這兩棵樹合并成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個新結點作為新樹的根，并将所選的兩棵樹的根分别作為新根的左右孩子(誰左，誰右無關緊要)，将這兩個孩子的權值之和作為新樹根的權值。 (3)對新的森林F重複(2)，直到森林F中隻剩下一棵樹為止。這棵樹便是哈夫曼樹。 注意： ① 初始森林中的n棵二叉樹，每棵樹有一個孤立的結點，它們既是根，又是葉子 ② n個葉子的哈夫曼樹要經過n-1次合并，産生n-1個新結點。最終求得的哈夫曼樹中共有2n-1個結點。 ③ 哈夫曼樹是嚴格的二叉樹，沒有度數為1的分支結點。
由哈夫曼樹的構造思想可知，用一個數組存放原來的n個葉子結點和構造過程中臨時生成的結點，數組的大小為2n-1.是以哈夫曼數中有兩個成員字段：data和leafNum。