java數據結構圖論霍夫曼樹及其編碼示例詳解
霍夫曼樹
一、基本介紹
二、霍夫曼樹幾個重要概念和舉例說明
構成霍夫曼樹的步驟
舉例:以arr = {1 3 6 7 8 13 29}
public class HuffmanTree { public static void main(String[] args) { int[] arr = { 13, 7, 8, 3, 29, 6, 1 }; Node root = createHuffmanTree(arr); preOrder(root); } // 編寫一個前序遍歷的方法 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加入到nodes nodes.add(parent); } // 返回赫夫曼樹的root節點 return nodes.get(0); } } //創建節點類 //為瞭讓Node對象支持排序Collections集合排序 //讓Node實現Comparable接口 class Node implements Comparable<Node> { int value;// 節點權值 Node left;// 指向左子節點 Node right;// 指向右子節點 public Node(int value) { this.value = value; } // 寫一個前序遍歷 public void preOrder() { System.out.println(this); if (this.left != null) { this.left.preOrder(); } if (this.right != null) { this.right.preOrder(); } } @Override public String toString() { return "Node [value=" + value + "]"; } @Override public int compareTo(Node o) { // 表示從小到大排列 return this.value - o.value; } }
霍夫曼編碼
一、基本介紹
二、原理剖析
6)說明:
原來長度是359,壓縮瞭(359 – 133) / 359 = 62.9%
此編碼滿足前綴編碼,即字符的編碼都不能是其他字符編碼的前綴。不會造成匹配的多義性;
霍夫曼編碼是無損的壓縮處理方案
註意:
霍夫曼編碼壓縮文件註意事項
1)如果文件本身就是經過壓縮處理的,那麼使用赫夫曼編碼在壓縮效率不會有明顯變化,比如視頻,ppt等等文件
2)赫夫曼編碼是按字節來處理的,因此可以處理所有的文件(二進制文件、文本文件)
3)如果一個文件中的內容,重復的數據不多,壓縮效果也不會很明顯。
以上就是java數據結構圖論霍夫曼樹及其編碼示例詳解的詳細內容,更多關於圖論數據結構霍夫曼樹及其編碼的資料請關註WalkonNet其它相關文章!