如何建立哈夫曼樹？假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 k1、k2、…、kn，則哈夫曼樹的構造規(guī)則為：(1) 將k1、k2、…，kn看成是有n 棵樹的森林(每棵樹僅有一

如何建立哈夫曼樹？

假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 k1、k2、…、kn，則哈夫曼樹的構造規(guī)則為：(1) 將k1、k2、…，kn看成是有n 棵樹的森林(每棵樹僅有一個結點)；(2) 在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。哈夫曼靜態(tài)編碼：它對需要編碼的數(shù)據(jù)進行兩遍掃描：第一遍統(tǒng)計原數(shù)據(jù)中各字符出現(xiàn)的頻率，利用得到的頻率值創(chuàng)建哈夫曼樹，并必須把樹的信息保存起來，即把字符0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示范圍為0--2^32-1，這已足夠表示大文件中字符出現(xiàn)的頻率了）以便解壓時創(chuàng)建同樣的哈夫曼樹進行解壓；第二遍則根據(jù)第一遍掃描得到的哈夫曼樹進行編碼，并把編碼后得到的碼字存儲起來。哈夫曼動態(tài)編碼：動態(tài)哈夫曼編碼使用一棵動態(tài)變化的哈夫曼樹，對第t 1個字符的編碼是根據(jù)原始數(shù)據(jù)中前t個字符得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字符，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字符所需的時間與該字符的編碼長度成正比，所以動態(tài)哈夫曼編碼可實時進行。