????????在了解哈夫曼樹之前我們要了解三個(gè)概念：結(jié)點(diǎn)的權(quán)值，結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度，樹的帶權(quán)路徑長(zhǎng)度。節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度就是結(jié)點(diǎn)的權(quán)值乘以路徑長(zhǎng)度；樹的帶權(quán)路徑長(zhǎng)度就是樹的所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。而哈夫曼樹就是帶權(quán)路徑長(zhǎng)度最小的樹，也叫做最優(yōu)二叉樹。

????????那么怎么構(gòu)造哈夫曼樹呢？首先在所有節(jié)點(diǎn)中選擇兩個(gè)權(quán)值最小的節(jié)點(diǎn)，作為兄弟節(jié)點(diǎn)，這兩個(gè)節(jié)點(diǎn)的權(quán)值之和就是他們根節(jié)點(diǎn)的權(quán)值，然后再在所有節(jié)點(diǎn)中選擇兩個(gè)根節(jié)點(diǎn)最小的樹作為兄弟節(jié)點(diǎn)以此類推。通過這樣的方法，可以保證該樹有一下幾個(gè)性質(zhì)：首先初始的幾個(gè)節(jié)點(diǎn)都將成為樹的葉結(jié)點(diǎn)，節(jié)點(diǎn)的權(quán)值越小，其距離根節(jié)點(diǎn)的距離越遠(yuǎn)。并且哈夫曼樹的節(jié)點(diǎn)總數(shù)為2n-1。

????????哈夫曼樹的誕生使得哈夫曼編碼應(yīng)運(yùn)而生，如果我們用0/1來表示數(shù)據(jù)，那么通過哈夫曼編碼，可以使權(quán)值高的數(shù)據(jù)用較少的字節(jié)表示出來，這就是可變長(zhǎng)度編碼。并且哈夫曼編碼可以有效避免解碼時(shí)產(chǎn)生的歧義，因?yàn)楣蚵幋a是一種前綴編碼，也就是沒有一個(gè)編碼是另一個(gè)編碼的前綴。這樣哈夫曼樹的帶權(quán)路徑長(zhǎng)度就變成哈夫曼編碼的傳輸字節(jié)數(shù)（葉子節(jié)點(diǎn)的權(quán)值就是要傳輸字符集中字符的頻度）。我們熟悉的摩爾斯電碼也體現(xiàn)出哈夫曼編碼思想，在英文中出現(xiàn)頻率越高的字母摩斯電碼越簡(jiǎn)單，現(xiàn)如今哈夫曼編碼已經(jīng)廣泛應(yīng)用于數(shù)據(jù)壓縮。