如何建立哈夫曼樹？

假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 k1、k2、…、kn，則哈夫曼樹的構造規則為：

(1) 將k1、k2、…，kn看成是有n 棵樹的森林(每棵樹僅有一個結點)；

(2) 在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；

(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；

(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。哈夫曼靜態編碼：它對需要編碼的數據進行兩遍掃描：

第一遍統計原數據中各字符出現的頻率，利用得到的頻率值創建哈夫曼樹，并必須把樹的信息保存起來，即把字符0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示范圍為0--2^32-1，這已足夠表示大文件中字符出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；

第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，并把編碼后得到的碼字存儲起來。哈夫曼動態編碼：動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字符的編碼是根據原始數據中前t個字符得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字符，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。

編碼和解碼一個字符所需的時間與該字符的編碼長度成正比，所以動態哈夫曼編碼可實時進行。