爱站程序员基地 赫夫曼树1 基本介绍1) 给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。2) 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近2 赫夫曼树几个重要概念和举例说明1) 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L-12) 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积3) 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL(weighted pathlength) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。4) WPL 最小的就是赫夫曼树
3 赫夫曼树创建思路图解给你一个数列 {13, 7, 8, 3, 29, 6, 1}，要求转成一颗赫夫曼树. 思路分析(示意图)：{13, 7, 8, 3, 29, 6, 1}构成赫夫曼树的步骤：1) 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树2) 取出根节点权值最小的两颗二叉树3) 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和4) 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树5) 图解:
4 赫夫曼树的代码实现
package huffmanTree;importad8java.util.ArrayList;import java.util.Collections;public class HuffmanTree {public static void main(String[] args) {int[] arr = {13, 7, 8, 3, 29, 6, 1};Node createHuffmanTree = createHuffmanTree(arr);preOrder(createHuffmanTree);}// 前序遍历方法public static void preOrder(Node root) {if(root != null) {root.preOrder();} else {System.out.println(\"空树！\");}}// 创建哈夫曼树public static Node createHuffmanTree(int[] arr) {// 1 遍历arr数组// 2 将arr的每个元素构成一个Node// 3 将Node放入ArrayListArrayList<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.toString());// 取出根节点权值最小的两个二叉树Node leftNode = nodes.get(0);Node rightNode = nodes.get(1);// 构建新二叉树Node parent = new Node(leftNode.value + rightNode.value);parent.left = leftNode;parent.right = rightNode;// 删除处理过的节点nodes.remove(leftNode);nodes.remove(rightNode);// parent加入Listnodes.add(parent);// Collections.sort(nodes);// System.out.println(nodes.toString());}// 返回rootreturn nodes.get(0);}}// 创建节点class Node implements Comparable<Node>{int value;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 = value;}@Overridepublic String toString() {return \"Node [value= \" + value +ad8\"]\";}@Overridepublic int compareTo(Node o) {return this.value - o.value;}}
赫夫曼编码1 基本介绍1) 赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法2) 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。3) 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%～90%之间4) 赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，称之为最佳编码2 原理剖析 通信领域中信息的处理方式 1-定长编码
通信领域中信息的处理方式 2-变长编码
通信领域中信息的处理方式 3-赫夫曼编码步骤如下：传输的 字符串1) i like like like java do you like a java2) d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5:9 // 各个字符对应的个数3) 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值步骤：构成赫夫曼树的步骤：1) 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树2) 取出根节点权值最小的两颗二叉树3) 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和4) 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
3 最佳实践-数据压缩(创建赫夫曼树)将给出的一段文本，比如 \”i like like like java do you like a java\” ， 根据前面的讲的赫夫曼编码原理，对其进行数据压缩处理，形式如：\”1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110\”步骤 ：根据赫夫曼编码压缩数据的原理，需要创建 \”i like like like java do you like a java\” 对应的赫夫曼树思路：前面已经分析过了，而且我们已然讲过了构建赫夫曼树的具体实现。代码实现：
package com.lin.HuffmanCode_0314;import java.util.ArrayList;import java.util.Collections;import java.util.HashMap;import java.util.List;import java.util.Map;public class HuffmanCode {public static void main(String[] args) {String content = \"i like like like java do you like a java\";byte[] contentBytes = content.getBytes();System.out.println(contentBytes.length); // 40List<Node> nodes = getNodes(contentBytes);System.out.println(nodes);// 创建哈夫曼树System.out.println(\"哈夫曼树\");Node createHuffmanTree = createHuffmanTree(nodes);preOrder(createHuffmanTree);}/**** @Description:生成赫夫曼树对应的赫夫曼编码<br>* 思路：将赫夫曼编码存放在Map<* @author LinZM* @date 2021-3-14 21:09:30* @version V1.8*/// 前序遍历private static void preOrder(Node root){if(root != null) {root.preOrder();} else {System.out.println(\"空树！\");}}/**** @Description:* @author LinZM* @date 2021-3-14 20:45:23* @version V1.8* @param bytes接收字节数组* @param*/private static List<Node> getNodes(byte[] bytes){// 1 创建一个ArrayListArrayList<Node> nodes= new ArrayList<Node>();// 遍历bytes，统计每一个byte出现的次数->map[key, value]Map<Byte, Integer> counts = new HashMap();for(byte b: bytes) {Integer count = counts.get(b); //if(count == null) { // Map中还没有这个字符数据, 第一次counts.put(b, 1);} else {counts.put(b, count + 1);}}// 把每个键值对转成一个Node对象， 并加入到nodes集合for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {nodes.add(new Node(entry.getKey(), entry.getValue()));}return nodes;}// 通过List创建赫夫曼树private static Node createHuffmanTree(List<Node> nodes) {while(nodes.size() > 1) {Collections.sort(nodes);Node leftNode = nodes.get(0);Node rightNode = nodes.get(1);Node parent = new Node(nad8ull, leftNode.weight + rightNode.weight);parent.left = leftNode;parent.right = rightNode;nodes.remove(leftNode);nodes.remove(rightNode);nodes.add(parent);}return nodes.get(0);}}class Node implements Comparable<Node>{Byte data;// 存放数据本身int weight; // 权值，字符出现的次数Node left;Node right;public Node(Byte data, int weight) {this.data = data;this.weight = weight;}@Overridepublic int compareTo(Node o) {// TODO Auto-generated method stubreturn this.weight - o.weight;}@Overridepublic String toString() {return \"Node [data = \" + data + \" weight= \" + weight + \"]\";}// 前序遍历public void preOrder() {System.out.println(this);if(this.left != null) {this.left.preOrder();}if(this.right != null) {this.right.preOrder();}}}
仅供参考，有错误还请指出！
有什么想法，评论区留言，互相指教指教。
觉得不错的可以点一下右边的推荐哟
