Huffman 编码Java实现（贪心算法）

Huffman 编码

问题分析

• 可参考 数据结构——HuffmanTreeJava 代码实现内含详细注释/* * 若尘 */ package huffmancode; import java.util.Collections; import java.util.LinkedList; import java.util.Scanner; /** * 哈夫曼编码 * @author ruochen * @version 1.0 */ public class Test { /** 用来存放节点值 */ private static LinkedList<HuffNode> huffList = new LinkedList<HuffNode>(); public static void main(String[] args) { // 第一个输入元素个数 // 然后换行输入 对应权值 元素 /** 如 * 5 * 10 a * 6 b * 4 c * 19 d * 1 e * **/ System.out.println("Please input: "); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) { huffList.add(new Test().new HuffNode(sc.nextInt(), sc.next())); } huffmanCode(); decode(huffList.get(0), ""); } class HuffNode implements Comparable<HuffNode> { /** 权值 */ int value; String name; /** 左孩子节点 */ HuffNode lChild = null; /** 右孩子节点 */ HuffNode rChild = null; public HuffNode(int value, String name) { this.value = value; this.name = name; } public HuffNode(HuffNode lChild, HuffNode rChild) { this.lChild = lChild; this.rChild = rChild; // 权值之和，即合并两个叶子节点 this.value = lChild.value + rChild.value; } /** * 按照权值大小非递减序列 * @param o * @return */ @Override public int compareTo(HuffNode o) { if (this.value < o.value) { return -1; } else if (this.value == o.value) { return 0; } else { return 1; } } } /** * 哈夫曼编码 */ public static void huffmanCode() { if (huffList.size() == 1) { return ; } while (huffList.size() > 1) { // 排序 Collections.sort(huffList); // 将前两个节点进行合并 HuffNode node = new Test().new HuffNode(huffList.get(0), huffList.get(1)); // 删除前两个节点 huffList.remove(); huffList.remove(); // 将新生成的节点添加到列表中 huffList.add(node); } // 编码完成后，此时huffList中只剩一个根节点 } /** * 解码 * @param n * @param code */ public static void decode(HuffNode n, String code) { if ((n.lChild == null) && (n.rChild == null)) { // 叶子节点， 此时输出其对应编码 System.out.print(n.name + "--->" + code); System.out.println(); return ; } // 遍历左子树 decode(n.lChild, code + "0"); // 遍历右子树 decode(n.rChild, code + "1"); return ; } }Please input: 5 10 a 6 b 4 c 19 d 1 e d--->0 a--->10 e--->1100 c--->1101 b--->111