如何使用Java赫夫曼樹技術

本篇內容介紹了“如何使用Java赫夫曼樹技術”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

基本介紹

給定 n 個權值作為 n 個葉子節點，構造一顆二叉樹，若該樹的帶權路徑長度(wpl)達到最小，稱這樣的二叉樹為最優二叉樹，也成為哈夫曼樹(Huffman  Tree)，還有的書翻譯成霍夫曼樹。

赫夫曼樹是帶權路徑長度最短的樹，權值較大的節點離根很近。

幾個重要概念

1. **路徑和路徑長度：**在一顆樹種，從一個節點往下可以達到的孩子或孫子節點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根節點的層數為1，則從根節點到L層節點的路徑長度為：L-1.

2. **節點的權和帶權路徑長度：**若將樹種的節點賦給一個有某種含義的數值，則這個數值稱為該節點的權。節點的帶權路徑長度為：從根節點到該節點之間的路徑長度與該節點的權的乘積。

3. 樹的帶權路徑長度：樹的帶權路徑長度規定為所有葉子節點的帶權路徑長度之和，即為WPL(weighted path  length)，權值越大的節點離根節點越近的二叉樹才是最優二叉樹。

4. WPL最小的就是赫夫曼樹

wpl=59的是赫夫曼樹

赫夫曼樹創建思路

給定一個數列{13,7,8,3,29,6,1}，要求轉成一個赫夫曼樹

1. 從小到大進行排序，將每一個數據都看成一個節點，每個節點可以看成是一顆最簡單的二叉樹。

2. 取出根節點權值最小的兩顆二叉樹。

3. 組成一顆新的二叉樹，該新的二叉樹的根節點的權值就是前面兩個二叉樹根節點權值的和。

4. 再將這個新的二叉樹，以根節點的權值大小排次排序，不斷重復1-2-3-4的步驟，直到數列中，所有的數據都被處理，就得到一顆赫夫曼樹。如下圖所示：

代碼案例

package com.xie.huffmantree;  import java.util.ArrayList; import java.util.Collections; import java.util.List;  public class HuffmanTree {     public static void main(String[] args) {         int[] arr = {13, 7, 8, 3, 29, 6, 1};         Node huffmanTree = createHuffmanTree(arr);         //前序遍歷         preOrder(huffmanTree);         /**          * Node{value=67}          * Node{value=29}          * Node{value=38}          * Node{value=15}          * Node{value=7}          * Node{value=8}          * Node{value=23}          * Node{value=10}          * Node{value=4}          * Node{value=1}          * Node{value=3}          * Node{value=6}          * Node{value=13}          */     }      //創建赫夫曼樹     public static Node createHuffmanTree(int[] arr) {         //第一步為了操作方便         //1.遍歷 arr 數組         //2.將 arr 的每個元素構成一個Node         //3.將 Node 放入 ArrayList中         List<Node> nodes = new ArrayList<>();         for (int value : arr) {             nodes.add(new Node(value));         }          while (nodes.size() > 1) {             //排序 從小到大             Collections.sort(nodes);             System.out.println("nodes = " + nodes);              //取出根節點權值最小的兩顆二叉樹             //(1)取出權值最小的節點(二叉樹)             Node leftNode = nodes.get(0);             //(2) 取出權值第二小的節點(二叉樹)             Node rightNode = nodes.get(1);              //(3) 構建一顆新的二叉樹             Node parent = new Node(leftNode.value + rightNode.value);             parent.left = leftNode;             parent.roght = rightNode;              //(4) 從ArrayList中刪除處理過的二叉樹             nodes.remove(leftNode);             nodes.remove(rightNode);              //(5) 將parent加入nodes             nodes.add(parent);         }          //返回赫夫曼樹的root節點         return nodes.get(0);      }      public static void preOrder(Node node) {         if (node != null) {             node.preOrder();         } else {             System.out.println("是空樹，不能遍歷~~");         }      } }  //創建節點類,為了讓Node對象支持排序，實現了Comparble接口 class Node implements Comparable<Node> {     //權值     int value;     //指向左子節點     Node left;     //指向右子節點     Node roght;      //寫一個前序遍歷     public void preOrder() {         System.out.println(this);         if (this.left != null) {             this.left.preOrder();         }          if (this.roght != null) {             this.roght.preOrder();         }     }      public Node(int value) {         this.value = value;     }      @Override     public String toString() {         return "Node{" +                 "value=" + value +                 '}';     }      @Override     public int compareTo(Node o) {         //從小到大進行排序         return this.value - o.value;     } }

“如何使用Java赫夫曼樹技術”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！