哈夫曼樹知識點

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

概念：

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

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

特點：

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

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

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

問題1：

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

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

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

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

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