粗陋的哈夫曼算法的实现

[size=large][color=darkblue]1.Node.java[/color][/size]package cn.com.Huffman;/** * 二叉树的节点的实现 * @author Administrator *2013.3.31 */public class Node {public String data;//保存的字符public int a; //字符个数public String huffmandata;//哈夫曼编码public Node leftchild; //左孩子public Node rightchild;//右孩子/** * 构造器的实现 * @param data 字符 * @param a  data字符个数 */public Node(String data,int a){this.data = data;this.a = a;huffmandata = null;leftchild = null;rightchild = null;}/** * 构造器的实现 * @param a 字符的个数 */public Node(int a){this.a = a;}}[size=large][color=darkblue]2.HuffmanCode.java[/color][/size]package cn.com.Huffman;import java.util.ArrayList;import java.util.List;/** * Huffman编码的实现 * @author Administrator *2013.3.31 */public class HuffmanCode {private Node root; //根节点List<Node> list = new ArrayList<Node>();/** * 默认构造器的实现 */public HuffmanCode(){root = null;}/** * 实现Huffman编码 * @param node 传入的节点数组 */public void huffman(Node[] node){if(node.length==1){return;}if(node.length==2){int d = node[0].a+node[1].a;root = new Node(d);root.leftchild = node[0];addZeroLeftChild(node[0]);//实现节点内哈夫曼编码的加0root.rightchild = node[1];addOneRightChild(node[1]);//实现节点内哈夫曼编码的加1return;}int d = node[0].a+node[1].a;Node no = new Node(d);no.leftchild = node[0];addZeroLeftChild(node[0]);//实现节点内哈夫曼编码的加0no.rightchild = node[1];addOneRightChild(node[1]);//实现节点内哈夫曼编码的加1Node[] c = new Node[node.length-1];for(int i=0;i<c.length-1;i++){c[i] = node[i+2];}c[c.length-1] = no;huffman(sort(c));}/** * 对节点数组进行排序 * @param a无序的节点数组 * @return 返回的是有序的节点数组 */public Node[] sort(Node[] a){for(int i=0;i<a.length;i++){for(int j=i;j<a.length;j++){if(a[i].a>a[j].a){Node b = a[i];a[i] = a[j];a[j] = b;}}}return a;}/** * 子节点node作为右孩子，则它以及它的子节点对象中的Huffmancode前加1； * @param node 孩子节点 */public void addOneRightChild(Node node){if(node!=null){node.huffmandata ="1"+ node.huffmandata;addOneRightChild(node.leftchild);addOneRightChild(node.rightchild);}}/** * 子节点node作为左孩子，则它以及它的子节点对象中的Huffmancode前加0； * @param node 孩子节点 */public void addZeroLeftChild(Node node){if(node!=null){node.huffmandata ="0"+ node.huffmandata;addZeroLeftChild(node.leftchild);addZeroLeftChild(node.rightchild);}}/** * 可传入root根节点，在控制台输出字符的个数和Huffman编码 * @param node  */public void get(Node node){if(node!=null){System.out.println(node.a+" ,"+node.huffmandata);get(node.leftchild);get(node.rightchild);}}/** * 将字符串转换成Node节点数组 * @param str //传入的字符串 * @return 返回一个有序Node[] */public Node[] formString(String str){char[] ch = str.toCharArray();for(int i=0;i<ch.length;i++){Node node = new Node(String.valueOf(ch[i]),0);list.add(node);}for(int i=0;i<ch.length;i++){int k = 0;Node no =null;for(int j=0;j<list.size();j++){if(String.valueOf(ch[i]).equals(list.get(j).data) && list.get(j).a==0){no = list.get(j);list.remove(j);k++;}}if(no!=null){no.a = k;list.add(no);}}Node[] n = new Node[list.size()];for(int i=0;i<n.length;i++){n[i] = list.get(i);}return n;}/** * 主函数入口 * @param args */public static void main(String args[]){HuffmanCode hc = new HuffmanCode();Node[] node = hc.formString("jiandequn");for(int i=0;i<hc.list.size();i++){System.out.println(hc.list.get(i).data+",  "+hc.list.get(i).a);}System.out.println("====================");hc.sort(node);hc.huffman(hc.sort(node));hc.get(hc.root);}}