—————? 第二天? —————

————————————

概念1：什么是路徑？

在一棵樹中，從一個結點到另一個結點所經過的所有結點，被我們稱為兩個結點之間的路徑。

上面的二叉樹當中，從根結點A到葉子結點H的路徑，就是A，B，D，H

概念2：什么是路徑長度？

在一棵樹中，從一個結點到另一個結點所經過的“邊”的數量，被我們稱為兩個結點之間的路徑長度。

仍然用剛才的二叉樹舉例子，從根結點A到葉子結點H，共經過了3條邊，因此路徑長度是3

概念3：什么是 結點的帶權路徑長度？

樹的每一個結點，都可以擁有自己的“權重”（Weight），權重在不同的算法當中可以起到不同的作用。

結點的帶權路徑長度，是指樹的根結點到該結點的路徑長度，和該結點權重的乘積。

假設結點H的權重是3，從根結點到結點H的路徑長度也是3，因此結點H的帶權路徑長度是 3 X 3 = 9?

概念4：什么是 樹的帶權路徑長度？

在一棵樹中，所有葉子結點的帶權路徑長度之和，被稱為樹的帶權路徑長度，也被簡稱為WPL。

仍然以這顆二叉樹為例，樹的路徑長度是 3X3?+?6X3 + 1X2 +?4X2 +?8X2 =?53?

哈夫曼樹是由麻省理工學院的哈夫曼博士于1952年發明，這到底是一顆什么樣的樹呢？

剛才我們學習了樹的帶權路徑長度（WPL），而哈夫曼樹（Huffman Tree）是在葉子結點和權重確定的情況下，帶權路徑長度最小的二叉樹，也被稱為最優二叉樹。

舉個例子，給定權重分別為1，3，4，6，8的葉子結點，我們應當構建怎樣的二叉樹，才能保證其帶權路徑長度最小？

原則上，我們應該讓權重小的葉子結點遠離樹根，權重大的葉子結點靠近樹根。

下圖左側的這棵樹就是一顆哈夫曼樹，它的WPL是46，小于之前例子當中的53：

需要注意的是，同樣葉子結點所構成的哈夫曼樹可能不止一顆，下面這幾棵樹都是哈夫曼樹：

假設有6個葉子結點，權重依次是2，3，7，9，18，25，如何構建一顆哈夫曼樹，也就是帶權路徑長度最小的樹呢？

第一步：構建森林

我們把每一個葉子結點，都當做樹一顆獨立的樹（只有根結點的樹），這樣就形成了一個森林：

在上圖當中，右側是葉子結點的森林，左側是一個輔助隊列，按照權值從小到大存儲了所有葉子結點。至于輔助隊列的作用，我們后續將會看到。

第二步：選擇當前權值最小的兩個結點，生成新的父結點

借助輔助隊列，我們可以找到權值最小的結點2和3，并根據這兩個結點生成一個新的父結點，父節點的權值是這兩個結點權值之和：

第三步：從隊列中移除上一步選擇的兩個最小結點，把新的父節點加入隊列

也就是從隊列中刪除2和3，插入5，并且仍然保持隊列的升序：

第四步：選擇當前權值最小的兩個結點，生成新的父結點

這是對第二步的重復操作。當前隊列中權值最小的結點是5和7，生成新的父結點權值是5+7=12：

第五步：從隊列中移除上一步選擇的兩個最小結點，把新的父節點加入隊列

這是對第三步的重復操作，也就是從隊列中刪除5和7，插入12，并且仍然保持隊列的升序：

第六步：選擇當前權值最小的兩個結點，生成新的父結點

這是對第二步的重復操作。當前隊列中權值最小的結點是9和12，生成新的父結點權值是9+12=21：

第七步：從隊列中移除上一步選擇的兩個最小結點，把新的父節點加入隊列

這是對第三步的重復操作，也就是從隊列中刪除9和12，插入21，并且仍然保持隊列的升序：

第八步：選擇當前權值最小的兩個結點，生成新的父結點

這是對第二步的重復操作。當前隊列中權值最小的結點是18和21，生成新的父結點權值是18+21=39：

第九步：從隊列中移除上一步選擇的兩個最小結點，把新的父節點加入隊列

這是對第三步的重復操作，也就是從隊列中刪除18和21，插入39，并且仍然保持隊列的升序：

第十步：選擇當前權值最小的兩個結點，生成新的父結點

這是對第二步的重復操作。當前隊列中權值最小的結點是25和39，生成新的父結點權值是25+39=64：

第十一步：從隊列中移除上一步選擇的兩個最小結點，把新的父節點加入隊列

這是對第三步的重復操作，也就是從隊列中刪除25和39，插入64：

此時，隊列中僅有一個結點，說明整個森林已經合并成了一顆樹，而這棵樹就是我們想要的哈夫曼樹：

private Node root; private Node[] nodes; //構建哈夫曼樹 public void createHuffman(int[] weights) {//優先隊列，用于輔助構建哈夫曼樹Queue<Node> nodeQueue = new PriorityQueue<>();nodes = new Node[weights.length];//構建森林，初始化nodes數組for(int i=0; i<weights.length; i++){nodes[i] = new Node(weights[i]);nodeQueue.add(nodes[i]);}//主循環，當結點隊列只剩一個結點時結束while (nodeQueue.size() > 1) {//從結點隊列選擇權值最小的兩個結點Node left = nodeQueue.poll();Node right = nodeQueue.poll();//創建新結點作為兩結點的父節點Node parent = new Node(left.weight + right.weight, left, right);nodeQueue.add(parent);}root = nodeQueue.poll(); } //按照前序遍歷輸出 public void output(Node head) {if(head == null){return;}System.out.println(head.weight);output(head.lChild);output(head.rChild); } public static class Node implements Comparable<Node>{int weight;Node lChild;Node rChild;public Node(int weight) {this.weight = weight;}public Node(int weight, Node lChild, Node rChild) {this.weight = weight;this.lChild = lChild;this.rChild = rChild;}@Overridepublic int compareTo(Node o) {return new Integer(this.weight).compareTo(new Integer(o.weight));} } public static void main(String[] args) {int[] weights = {2,3,7,9,18,25};HuffmanTree huffmanTree = new HuffmanTree();huffmanTree.createHuffman(weights);huffmanTree.output(huffmanTree.root); }

在這段代碼中，為了保證結點隊列當中的結點始終按照權值升序排列，我們使用了優先隊列PriorityQueue。

與此同時，靜態內部類Node需要實現比較接口，重寫compareTo方法，以保證Node對象在進入隊列時按照權值來比較。

—————END—————

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習在線手冊深度學習在線手冊AI基礎下載（pdf更新到25集）本站qq群1003271085，加入微信群請回復“加群”獲取一折本站知識星球優惠券，請回復“知識星球”喜歡文章，點個在看

總結

以上是生活随笔為你收集整理的算法漫画：什么是 “哈夫曼树” ？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。