独角兽企业重金招聘Python工程师标准>>>
package org.loda.greedy;import org.junit.Test;import org.loda.structure.MinQ;/*** * @ClassName: HuffmanCoding * @Description: 哈夫曼编码 * @author minjun* @date 5月21日 上午12:04:02 **/public class HuffmanCoding {@Testpublic void huffmanCoding(){String text="ABRACADABRA!";MinQ<Node> minQ=getMinQFromText(text);Node root=getRoot(minQ);printTree(root,"");}/*** * @Title: printTree * @Description: 打印哈夫曼编码后的字符编码键值对 * @param @param x* @param @param str 设定文件 * @return void 返回类型 * @throws*/private void printTree(Node x,String str) {if(x.left==null&&x.right==null){System.out.println("字符"+x.c+"\t——>编译码\t"+str);return;}printTree(x.left,str+"0");printTree(x.right,str+"1");}/*** * @Title: getRoot * @Description: 构造哈夫曼树，并返回根节点 * @param @param minQ* @param @return 设定文件 * @return Node 返回类型 * @throws*/private Node getRoot(MinQ<Node> minQ) {//保证本次迭代前队列至少有两个元素，不然两次poll取出元素会报错while(minQ.size()>1){//选出当前最优解（即选出目前最小的两个节点，为其组合父亲节点，以便使得优先队列的元素不断组合成一棵二叉树）Node x=minQ.poll();Node y=minQ.poll();//创建两个最小节点的父节点Node node=new Node(x.freq+y.freq,'\0');//将父节点与两个子节点组合node.left=x;node.right=y;//将组合完成的父节点添加到哈弗曼树中minQ.offer(node);}//取出哈夫曼树的根节点return minQ.poll();}/*** * @Title: getMinQFromText * @Description: 统计文本串中字符出现频率（次数），并以出现频率小到到排序（添加到优先队列） * @param @param text* @param @return 设定文件 * @return MinQ<Node> 返回类型 * @throws*/private MinQ<Node> getMinQFromText(String text) {MinQ<Node> minQ=new MinQ<Node>();int R=256;Node[] nodes=new Node[R];for(int i=0;i<text.length();i++){if(nodes[text.charAt(i)]!=null){nodes[text.charAt(i)].freq++;}else{nodes[text.charAt(i)]=new Node(1,text.charAt(i));}}for(Node node:nodes){if(node!=null){minQ.offer(node);}}return minQ;}class Node implements Comparable<Node>{//访问频率int freq;//字母char c;//左右节点Node left;Node right;public Node(int freq, char c) {super();this.freq = freq;this.c = c;}@Overridepublic int compareTo(Node o) {return this.freq-o.freq;}@Overridepublic String toString() {return "Node [freq=" + freq + ", c=" + c + "]";}}}输出内容为：字符A——>编译码0字符D——>编译码100字符!——>编译码1010字符C——>编译码1011字符R——>编译码110字符B——>编译码111
上面代码中使用到的优先队列MinQ是我在该系列博客中已经放出来过的，可以参考/u/1378920/blog/417175这个地址
