WPL(weighted path length) ,權值越大的結點離根結點越近的二叉樹才是最優二叉樹 。
文章插圖
2.2、赫夫曼樹創建思路圖解給出一個數列
{13, 7, 8, 3, 29, 6, 1}，要求轉成一顆赫夫曼樹構成赫夫曼樹的步驟：
- 從小到大進行排序, 將每一個數據，每個數據都是一個節點 ，每個節點可以看成是一顆最簡單的二叉樹
- 取出根節點權值最小的兩顆二叉樹
- 組成一顆新的二叉樹, 該新的二叉樹的根節點的權值是前面兩顆二叉樹根節點權值的和
- 再將這顆新的二叉樹，以根節點的權值大小 再次排序，不斷重復 1-2-3-4 的步驟，直到數列中，所有的數據都被處理，就得到一顆赫夫曼樹
（1）選出最小的兩個數組成二叉樹
文章插圖
（2）接下來在
4,6,7,8...中選擇最小的兩個4，6(注意這里要加入第一步組成的節點4,大的在右邊，小的在左邊)
文章插圖
（3）重復上述步驟
文章插圖
2.3、赫夫曼樹代碼實現
public class HuffmanTree {public static void main(String[] args) {int arr[] = { 13, 7, 8, 3, 29, 6, 1 };Node root = createHuffmanTree(arr);preOrder(root); //67,29,38,15,7,8,23,10,4,1,3,6,13}//編寫一個前序遍歷的方法public static void preOrder(Node root) {if(root != null) {root.preOrder();}else{System.out.println("是空樹 ， 不能遍歷~~");}}// 創建赫夫曼樹的方法/**** @param arr 需要創建成哈夫曼樹的數組* @return 創建好后的赫夫曼樹的root結點*/public static Node createHuffmanTree(int[] arr) {// 第一步為了操作方便// 1. 遍歷 arr 數組// 2. 將arr的每個元素構成成一個Node// 3. 將Node 放入到ArrayList中List<Node> nodes = new ArrayList<Node>();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.right = rightNode;//(4)從ArrayList刪除處理過的二叉樹nodes.remove(leftNode);nodes.remove(rightNode);//(5)將parent加入到nodesnodes.add(parent);}//返回哈夫曼樹的root結點return nodes.get(0);}}// 創建結點類// 為了讓Node 對象持續排序Collections集合排序// 讓Node 實現Comparable接口class Node implements Comparable<Node> {int value; // 結點權值char c; //字符Node left; // 指向左子結點Node right; // 指向右子結點//寫一個前序遍歷public void preOrder() {System.out.println(this);if (this.left != null) {this.left.preOrder();}if (this.right != null) {this.right.preOrder();}}public Node(int value) {this.value = https://www.huyubaike.com/biancheng/value;}@Overridepublic String toString() {return"Node [value="https://www.huyubaike.com/biancheng/+ value +"]";}@Overridepublic int compareTo(Node o) {// TODO Auto-generated method stub// 表示從小到大排序return this.value - o.value;}}結果：
文章插圖
3、赫夫曼編碼3.1、簡介
- 赫夫曼編碼也翻譯為 哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式, 屬于一種程序算法
- 赫夫曼編碼是赫哈夫曼樹在電訊通信中的經典的應用之一 。
- 赫夫曼編碼廣泛地用于數據文件壓縮 。其壓縮率通常在 20%～90%之間
- 赫夫曼碼是可變字長編碼(VLC)的一種 。Huffman 于 1952 年提出一種編碼方法，稱之為最佳編碼
- 通信領域中信息的處理方式 1-定長編碼
文章插圖
- 通信領域中信息的處理方式 2-變長編碼
推薦閱讀
- 1 python-數據描述與分析
- 創造與魔法最新每日禮包兌換碼是多少
- 企業運維 | MySQL關系型數據庫在Docker與Kubernetes容器環境中快速搭建部署主從實踐
- 驅動通信：通過PIPE管道與內核層通信
- 光與夜之戀雙十一禮包怎么購買
- MES系統與ERP系統信息集成有哪些原則？
- 企業MES系統與ERP信息集成要素有哪些？
- 光與夜之戀鉅惠嘉年華怎么買劃算
- 補充部分---ScheduledThreadPoolExecutor類分析 線程池底層原理詳解與源碼分析
- 驅動開發：通過ReadFile與內核層通信