霍夫曼树一、基本介绍
二、霍夫曼树几个重要概念和举例说明
构成霍夫曼树的步骤
举例：以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中霍夫曼树的示例分析的详细内容。