天天看點

哈夫曼樹知識點

哈夫曼樹,又稱最優二叉樹。

概念:

1.樹的帶權路徑:所有葉子節點到根節點的路徑權重和。

2.哈夫曼樹:帶權路徑長度最短的二叉樹。

特點:

1.每個節點的度隻能為2或者0;

2.葉子結點數是N時,中間節點數為N-1,總結點樹為2*N-1

3.哈夫曼編碼:任意一個葉節點的編碼都不是其他葉節點編碼的字首。

問題1:

1.為什麼帶權路徑最短?

前提:帶全路徑所求的是葉子到根節點的長度,每個節點的度隻能為0或者2

因為哈夫曼樹的建立步驟是:每次取出節點中權最小的兩個節點構樹。得到的結果是,權數越小的節點,路徑越長;權數越大的節點,路徑越短。一顆樹上的節點為N時,所有節點的連線共有N-1條,隻要保證小權節點所占路徑越大,大權路徑越小,得到的帶權路徑長度才能越小。

2.哈夫曼編碼為啥任意一個編碼都不是其他編碼的字首?

因為這裡所說的編碼都是對葉子結點的編碼。每個葉子節點的度都是0,是終結節點,沒有其他節點經過。是以通過哈夫曼編碼得到的結果不會存在歧義。是以在解碼的時候,可以順序讀取編碼,依次找編碼對應得值,而不會出現走不通或者歧義的情況。

繼續閱讀