※超省錢租車方案
商務出差、學生出遊、旅遊渡假、臨時用車!GO 神州租賃有限公司!合法經營、合法連鎖、合法租賃小客車!
前文傳送門：
「一本正經的聊數據結構（1）：時間複雜度」
「一本正經的聊數據結構（2）：數組與向量」
「一本正經的聊數據結構（3）：棧和隊列」
「一本正經的聊數據結構（4）：樹」
「一本正經的聊數據結構（5）：二叉樹的存儲結構與遍歷」
基礎知識
感謝某位在後台留言的同學，讓我想起來我還有這個沒寫完的系列。
在最開始，先了解幾個基礎概念：
- 路徑：在一棵樹中，一個結點到另一個結點之間的通路，稱為路徑。
上面這個二叉樹中，根節點 A 到恭弘=叶 恭弘子結點 I 的路徑，就是A，B，D，I。
- 路徑長度：在一條路徑中，每經過一個結點，路徑長度都要加 1 。例如在一棵樹中，規定根結點所在層數為1層，那麼從根結點到第 i 層結點的路徑長度為 i – 1 。
在這個二叉樹中，根節點 A 到恭弘=叶 恭弘子結點 H 的路徑長度就是 3 。
- 結點的權：給每一個結點賦予一個數值，被稱為這個結點的權。
- 結點的帶權路徑長度：指的是從根結點到該結點之間的路徑長度與該結點的權的乘積。
我們假設節點 H 的權是 5 ，從根結點到結點 H 的路徑長度是 3 ，那麼結點 H 的帶權路徑長度是 3 X 5 = 15。
- 樹的帶權路徑長度：在一棵樹中，所有恭弘=叶 恭弘子結點的帶權路徑長度之和，被稱為樹的帶權路徑長度，也被簡稱為 「WPL」 。
還是這顆樹，它的帶權路徑長度是 1 X 2 + 2 X 1 + 2 X 3 + 2 X 4 + 3 X 5 + 3 X 6 = 51 。
哈夫曼樹
哈弗曼樹就是在用 n 個結點（都做恭弘=叶 恭弘子結點且都有各自的權值）試圖構建一棵樹時，如果構建的這棵樹的帶權路徑長度最小，稱這棵樹為「最優二叉樹」，有時也叫「哈夫曼樹」或者「赫夫曼樹」。
在構建哈弗曼樹時，要使樹的帶權路徑長度最小，只需要遵循一個原則，那就是：權重越大的結點離樹根越近。
需要注意的是，同樣恭弘=叶 恭弘子結點所構成的哈夫曼樹可能不止一顆，在同一層，左右恭弘=叶 恭弘子節點交換位置，樹的帶權路徑長度是一樣的，就比如下面這兩個哈夫曼樹：
哈弗曼樹的構建過程
那麼如何構建一個哈夫曼樹呢？我們這裏舉個例子，比如我們有這麼幾個恭弘=叶 恭弘子節點：3，4，7，9，13，15，17：
第一步：選出兩個最小的權值，對應的兩個結點組成一個新的二叉樹，且新二叉樹的根結點的權值為左右孩子權值的和：
第二步：從隊列中移除上一步選擇的兩個最小結點，把新的父節點加入隊列，也就是從隊列中刪除 3 和 4 ，插入 7 ，並且仍然保持隊列的升序：
第三步：選擇當前權值最小的兩個結點，生成新的父結點。
這一步其實是在重複上一步操作，當前隊列中最小的節點是 7 和 7 ，生成新的父結點權值是 7 + 7 = 14 ：
※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益
有別於一般網頁架設公司，除了模組化的架站軟體，我們的營業主軸還包含：資料庫程式開發、網站建置、網頁設計、電子商務專案開發、系統整合、APP設計建置、專業網路行銷。
第四步：從隊列中移除上一步選擇的兩個最小結點，把新的父節點加入隊列。
這一步依然是在重複，從隊列中刪除 7 和 7 ，加入 14 ，並且仍然保持隊列的升序：
第五步：選擇當前權值最小的兩個結點，生成新的父結點。
這一步還是重複操作。當前隊列中權值最小的結點是 9 和 14 ，生成新的父結點權值是 9 + 14 = 23 ：
第六步：從隊列中移除上一步選擇的兩個最小結點，把新的父節點加入隊列。
這一步依然是在重複，從隊列中刪除 9 和 14 ，加入 23 ，並且仍然保持隊列的升序：
第七步：選擇當前權值最小的兩個結點，生成新的父結點。
這一步從隊列中選擇權值最小的結點是 13 和 15 ，生成新的父結點權值是 13 + 15 = 28 ：
第八步：從隊列中移除上一步選擇的兩個最小結點，把新的父節點加入隊列。
從隊列中刪除 13 和 15 ，加入 28 ，並且仍然保持隊列的升序：
第九步：選擇當前權值最小的兩個結點，生成新的父結點。
這一步從隊列中選擇權值最小的結點是 17 和 23 ，生成新的父結點權值是 17 + 23 = 40 ：
第十步：從隊列中移除上一步選擇的兩個最小結點，把新的父節點加入隊列。
從隊列中刪除 17 和 23 ，加入 40 ，並且仍然保持隊列的升序：
第十一步：選擇當前權值最小的兩個結點，生成新的父結點，移除隊列中的最後兩個節點（懶得畫了，最後兩步並一步）。
這一步從隊列中選擇權值最小的結點是 28 和 40 ，生成新的父結點權值是 28 + 40 = 68 ：
此時，我們得到的這棵樹就是哈弗曼樹。
哈夫曼樹就介紹到這裏，下一節，將會介紹哈夫曼樹的用途：哈夫曼編碼。
參考
http://c.biancheng.net/view/3398.html
https://baijiahao.baidu.com/s?id=1663514710675419737&wfr=spider&for=pc
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
※Google地圖已可更新顯示潭子電動車充電站設置地點!!
日本、大陸，發現這些先進的國家已經早就讓電動車優先上路，而且先進國家空氣品質相當好，電動車節能減碳可以減少空污