一本正經的聊數據結構（6）：最優二叉樹 —— 哈夫曼樹_租車

Posted on by

※超省錢租車方案

商務出差、學生出遊、旅遊渡假、臨時用車!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地圖已可更新顯示潭子電動車充電站設置地點!!

日本、大陸，發現這些先進的國家已經早就讓電動車優先上路，而且先進國家空氣品質相當好，電動車節能減碳可以減少空污