package 哈夫曼二叉树820;/** * 节点中的数据域，一个字符，一个数字； * @author Administrator * */public class Data {    private String c;//字符；    private int number;//字符出现的次数；        public Data(String c,int number){//构造方法        this.c=c;        this.number=number;    }    public Data(){//构造方法            }    public String getC() {        return c;    }    public void setC(String c) {        this.c = c;    }    public int getNumber() {        return number;    }    public void setNumber(int number) {        this.number = number;    }    }

package 哈夫曼二叉树820;/** * 一个节点类，每一个节点都有左节点，右节点，以及数据域； * @author YuanMo; * */public class Node {    private Data data;//数据域，数据域内存放两个数据，所以定义一个类来表示；    public Node left;//左子节点；    public Node  right;//右子节点；        /**     * 重写构造方法；data在构造方法中取得；     */    public Node(Data data){        this.data =http://www.mamicode.com/ data;    }    /**     * 因为定义Data的是private型，所以实现Data的set和get方法；     */    public Data getData() {        return data;    }    public void setData(Data data) {        this.data =http://www.mamicode.com/ data;    }                }

package 哈夫曼二叉树820;public class HFMTree {    /**     * 创建哈夫曼数；     * @param left哈夫曼树的左子节点；     * @param right哈夫曼熟的右子节点     * @return     */    public Node creatHFMTree(Node left, Node right) {        Data data = new Data();        String c = left.getData().getC() + right.getData().getC();// 得到新的字符c；        int number = left.getData().getNumber() + right.getData().getNumber();// 得到新的number；        data.setC(c);// 把c给新的data        data.setNumber(number);// 把number给新的data        Node fathernode = new Node(data);// 根据data数据域创建父节点；        fathernode.left = left;// 把left设为父节点的左子节点        fathernode.right = right;// 把left设为父节点的右子节点        return fathernode;// 把父节点传回去；    }    /**     * 打印哈夫曼树； 采用前序遍历；     * @param node要打印的当前的节点；     */    public void printHFMTree(Node node) {        if (node != null) {        String c=    node.getData().getC();        int number=node.getData().getNumber();            System.out.print("" + "字符：" + c + "    频率：" + number);            System.out.println();            if (node.left != null) {// 当不为空时，递归调用该方法输出；                printHFMTree(node.left);            }            if (node.right != null) {// 当不为空时，递归调用该方法输出；                printHFMTree(node.right);            }        }    }}

package 哈夫曼二叉树820;import java.util.ArrayList;public class CreatHFMTree {    public static void main(String[] args) {        ArrayList<Node> list = new ArrayList<Node>();// 实例化一个数组队列进行存储数据；        list.add(new Node(new Data("b", 3)));        list.add(new Node(new Data("c", 7)));        list.add(new Node(new Data("d", 10)));        list.add(new Node(new Data("a", 15)));        // 实例化一个哈夫曼树对象；        HFMTree hfm = new HFMTree();        // 根据list数组队列中的节点去创建哈夫曼；        for (int i = 0; i < list.size(); i++) {            sort(list);// 对数组队列进行排序；            /*因为每取一次，我们就删除，而删除之后数组队列的数改变了，也就是形成了一个新的数组             *     所以我们需要从头开始找，也就是从新的数组的第一个数开始；    */            i = 0;            Node left = list.get(i);// 得到左子节点；            list.remove(i);// 在数组队列中删除该节点            Node right = list.get(i);// 得到右子节点；            list.remove(i);// 在数组队列中删除该节点                        Node father = hfm.creatHFMTree(left, right);// 得到父节点；            list.add(father);// 把父节点添加到数组中；        }        Node root = list.get(0);// 获取根节点；        hfm.printHFMTree(root);    }    /**     * 将数组队列进行排序；采用了冒泡排序法；     * @param list   要进行排序的数组队列；     */    public static void sort(ArrayList<Node> list) {        for (int j = 0; j < list.size(); j++) {            for (int i = 0; i < list.size() - 1; i++) {                Node c = list.get(i);                int z = i;                z++;                Node x = list.get(z);                if (c.getData().getNumber() > x.getData().getNumber()) {                    list.remove(i);                    list.add(i, x);                    list.remove(z);                    list.add(z, c);                }            }        }    }}