帶權(quán)路徑長(zhǎng)度
- 路徑長(zhǎng)度：路徑上所經(jīng)歷的邊的個(gè)數(shù)
- 結(jié)點(diǎn)的權(quán)：結(jié)點(diǎn)被賦予的數(shù)值
樹(shù)的帶權(quán)路徑長(zhǎng)度： 樹(shù)中所有葉節(jié)點(diǎn)的帶權(quán)路徑之和
公式及計(jì)算如下
哈夫曼樹(shù)：也成為最優(yōu)二叉樹(shù)无宿，就是含n的帶權(quán)葉子結(jié)點(diǎn)的樹(shù)之中帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)亡资。在上面的兩個(gè)樹(shù)中第二棵樹(shù)就是一顆哈夫曼樹(shù)攘须。
構(gòu)造哈夫曼樹(shù)穴翩，只需按照步驟一步一步來(lái)即可
哈夫曼樹(shù)在構(gòu)造的時(shí)候沒(méi)有規(guī)定左右子樹(shù)难咕，所以其不唯一
哈夫曼樹(shù)的構(gòu)造方法
哈夫曼樹(shù)的性質(zhì)
哈夫曼樹(shù)的應(yīng)用
編碼：對(duì)于一個(gè)字符串序列痢艺，用二進(jìn)制數(shù)來(lái)表示每一個(gè)字符
固定長(zhǎng)度編碼
可變長(zhǎng)度編碼赘理，因?yàn)闀?huì)產(chǎn)生歧義铅歼，不可應(yīng)用
使用哈夫曼樹(shù)構(gòu)造的過(guò)程如下
字母對(duì)應(yīng)的數(shù)字是指字母出現(xiàn)的次數(shù)
按照規(guī)則構(gòu)造出來(lái)的哈夫曼樹(shù)公壤，左0，右1
這樣構(gòu)造出來(lái)的編碼不會(huì)產(chǎn)生歧義椎椰，且長(zhǎng)度變短了
