資料結構中的赫夫曼樹

定義

赫夫曼編碼為字元提供程式碼，程式碼長度取決於相應字元的相對頻率或權重。赫夫曼編碼採用可變長度，且無任何字首（即任何程式碼都不是其他程式碼的字首）。任何無字首的二進位制程式碼都可以表示為二叉樹，其中編碼的字元儲存在葉節點。

赫夫曼樹或赫夫曼編碼樹定義為一棵滿二叉樹，其中樹的每個葉節點對應於給定字母表中的一個字母。

赫夫曼樹被視為具有最小外部路徑權重的二叉樹，即它與給定葉節點集的加權路徑長度總和最小。因此，目標是構建一棵具有最小外部路徑權重的樹。

舉例說明：

字母頻率表

赫夫曼編碼

霍夫曼樹（對於上述示例）如下所述 -

Arnab Chakraborty

更新於：2020 年 1 月 16 日

1.2 萬+ 瀏覽次數

開啟你的 職業生涯

透過完成課程獲得認證

開始