🎈 作者：Linux猿
🎈 簡介：CSDN博客專家🏆，華為云享專家🏆，資料結構和演算法、C/C++、面試、刷題、Linux盡管咨詢我，關注我，有問題私聊！
🎈 關注專欄：動圖講解資料結構和演算法（優質好文持續更新中……）🚀
🎈 歡迎小伙伴們點贊👍、收藏?、留言💬
目錄
🍓一、什么是赫夫曼樹 ？
🍓二、赫夫曼樹的特性
🍓三、赫夫曼樹的構造程序
?3.1 演算法思路
?3.2 實體演示
🍓四、應用-赫夫曼編碼
?4.1 題目描述
?4.2 演算法思路
?4.3 動圖決議
🍓五、赫夫曼樹題目
🍓六、總結
赫夫曼樹是在考試、考研、面試中經常提到的一個知識點，下面就讓我們一塊來看下赫夫曼樹及其應用吧！
🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶
🍓一、什么是赫夫曼樹 ？
在說赫夫曼樹之前，一定要先了解一個概念“帶權路徑長度”，簡稱 WPL，WPL 已在文章【資料結構和演算法】超詳細，超多圖解，樹的各種概念匯總 中進行了介紹，
赫夫曼樹是帶權路徑長度（WPL） 最小的二叉樹，也稱作最優二叉樹、哈夫曼樹、霍夫曼樹，
該演算法是由 Huffman 在攻讀博士學位期間開發的演算法，
🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶
🍓二、赫夫曼樹的特性
（1）赫夫曼樹是一棵二叉樹；
（2）赫夫曼樹中結點的度為 0 或 2，即沒有度為 1 的結點；
🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶
🍓三、赫夫曼樹的構造程序
?3.1 演算法思路
假設給定 n 個權值 要求構造一棵具有 n 個葉子結點的二叉樹，每個葉子結點的權值為
，求帶權路徑最小的二叉樹，
構造赫夫曼樹的演算法步驟如下所示：
（1）根據給定的 n 個權值，構造一個二叉樹的集合 ，初始時，
為單個結點的子樹，權值為
，左右子樹為空；
（2）在二叉樹的集合中選擇權值最小的兩棵子樹，兩個子樹分別作為新子樹的左右子樹，添加一個新結點作為兩個子樹的父節點，新結點的權值為左右子樹根結點之和；
（3）洗掉原集合中步驟（2）選中的兩棵子樹，將新合并的子樹加入到集合 F 中；
（4）重復步驟 （2）~（3），直到集合中只有一顆子樹為止；
（5）此時的二叉樹稱為赫夫曼樹，
?3.2 實體演示
假設給定 7 個權值 {10, 8, 9, 15, 23, 7, 16} ，要求構造一棵具有 7 個葉子結點的二叉樹，葉子結點的權值依次為{10, 8, 9, 15, 23, 7, 16}，求帶權路徑最小的二叉樹，
初始時，集合 F 中子樹根結點的權值為 {10, 8, 9, 15, 23, 7, 16}，如下圖所示：
構造赫夫曼樹的步驟如下所示：
（1）選擇集合 F 中子樹根結點最小的兩個結點，選擇 8 和 7，將其組成一個新的子樹，如下所示：
（2）此時，集合 F 中子樹根結點的權值為 {10，9，15，23，15，16}，其中，第二個 15 為 8 和 7 合并后新的根結點的權值，再次選擇兩個最小權值的子樹，選擇 10 和 9，將其組成一個新的子樹，如下所示：
（3）此時，集合 F 中子樹根結點的權值為 {19,15,23,15,16}，19 為 10 和 9 合并后新的值，再次選擇兩個最小權值的子樹，選擇 15 和 15，將其組成一個新的子樹，如下所示：
（4）此時，集合 F 中子樹根結點的權值為 {19,23,30,16}，30 為 15 和 15 合并后的新值，再次選擇兩個最小權值的子樹，選擇19和16，將其組成一個新的子樹，如下所示：
（5） 此時，集合 F 中子樹根結點的權值為 {23,30,35}，35 為 19 和 16 合并后的新值，再次選擇兩個最小權值的子樹，選擇23 和 30，將其組成一個新的子樹，如下所示：
（6）此時，集合 F 中子樹根結點的權值為 {53,35}，其中，53 為 23 和 30 合并后的新值，再次選擇兩個最小權值的子樹，選擇 53 和 35，將其組成一個新的子樹，如下所示：
（7）此時，集合 F 中只有一顆樹，這棵樹便是最優二叉樹/赫夫曼樹，
🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶
🍓四、應用-赫夫曼編碼
?4.1 題目描述
已知存在字符集 {A，B，C，D，E，F} ，各字母出現的頻率依次為 5，7，12，2，18，9，求哈夫曼編碼，
?4.2 演算法思路
本題是赫夫曼編碼的應用，字母出現的頻率是字符的權重，將其作為葉子結點，計算赫夫曼樹，然后進行赫夫曼編碼即可，
?4.3 動圖決議
下面來看一下動圖建立赫夫曼樹的程序，如下所示：
在上圖中，紫色表示為構造赫夫曼樹新添加的點，建立完赫夫曼樹后，本文按照左 0 右 1 的策略編碼，如下所示：
經過上圖的編碼后，各字符的編碼如下所示：
A （權值為 5 的葉子結點）的編碼為：0000
B（權值為 7 的葉子結點）的編碼為：001
C（權值為 12 的葉子結點）的編碼為：11
D（權值為 2 的葉子結點）的編碼為：0001
E（權值為 18 的葉子結點）的編碼為：01
F（權值為 9 的葉子結點）的編碼為：10
赫夫曼編碼是一種無前綴編碼，什么是無前綴呢？
無前綴是指字符的編碼相互之間沒有哪個是另一個的前綴（例如：有兩個字符編碼分別為 0011 和 001，那么 001 就是 0011 的前綴），可以看到，上面的例子中，經過編碼后，A、B、C、D、E、F 都是無前綴編碼，相互之間沒有一個是另一個的前綴，
🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶
🍓五、赫夫曼樹題目
下面列出了兩道練習題，理解后一定要聯系哦！
（1）北大OJ Entropy
（2）杭電OJ Safe Or Unsafe
題解后續會更新到公眾號中，記得關注文章末尾公眾號！
🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶
🍓六、總結
在學習赫夫曼樹時，首先要掌握赫夫曼樹的構造程序，在此基礎上掌握赫夫曼編碼的原理，最后做題鞏固即可！
如果感覺對你有幫助，點贊👍、收藏?、留言💬支持下吧！
關注下方👇👇👇👇👇公眾號👇👇👇👇👇，獲取更多優質好文🤞（比心）！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/355333.html
標籤：其他
上一篇：初階資料結構——二叉樹