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

如何建立哈夫曼樹？

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