哈夫曼樹（編碼）

文章目錄

一、為什麼要引入哈夫曼樹

二、哈夫曼樹的概念

三、哈夫曼樹的構造

四、 哈夫曼樹的特點

五、哈夫曼編碼

六、 二叉樹用于編碼

一、為什麼要引入哈夫曼樹

壓縮檔案的時候，為了減少不必要的空間，并且使儲存和傳遞都更加高效。于是，介紹最基本的壓縮編碼方法------哈夫曼樹

二、哈夫曼樹的概念

• 路徑：從樹中一個結點到另一個結點之間的分支構成的路徑
• 路徑長度：路徑上分支的數目
• 樹的路徑長度：從樹根到每一結點的路徑長度之和

考慮帶權的特點：

• 結點的帶權路徑長度：從根節點到該結點之間的路徑長度與該結點權的乘積
• 樹的帶權路徑長度：樹中所有葉子結點的帶權路徑之和

哈夫曼樹：帶權路徑長度WPL最小的二叉樹

三、哈夫曼樹的構造

• 每次把權值最小的兩棵二叉樹合并（比較二叉樹根結點上的大小）

  哈夫曼樹算法的複雜度主要由以下幾部分組成：

• 1、調整最小堆：O（N）
• 2、2（N-1）+1個删除：O（NlogN）
• 3、N-1個插入：O（NlogN）
• 整體複雜度為O（NlogN）

四、哈夫曼樹的特點：

• 沒有度為1的結點；（用于判斷是否是哈夫編碼），不一定是完全二叉樹。

• n0個葉子結點的哈夫曼樹共有2n0-1個結點；
• 哈夫曼樹的任意非葉節點的左右子樹交換後仍是哈夫曼樹；

  

五、哈夫曼編碼

• 給定一段字元串，如何對字元進行編碼，可以使得該字元串的編碼存儲空間最少？
• 不等長編碼：出現頻率高的字元用的編碼短些，出現頻率低的字元則可以編碼長些。
• 怎麼進行不等長編碼？如何避免二義性？
• 字首碼：任何字元的編碼都不是另一字元編碼的字首，可以無二義地編碼

六、二叉樹用于編碼

• 1、左右分支：0、1
• 2、字元隻在葉節點上