哈夫曼树及哈夫曼编码

哈夫曼树

基本介绍

给定n个叶子结点，构造一棵二叉树。若该树的带权路径长度（wpl）达到最值，则称这棵树为最有二叉树，也称为哈夫曼树。
哈夫曼树是带权路径长度最短的树，权值较大点根本较近
路径个路径长度：在一棵树中，从一个节点往下可以达到的孩子节点或孙子节点之间的通路。成为路径，通路中分支的数目成为路径长度，若规定根节点的层数为1，则从根节点到第L层的节点的路径长度为L-1
结点的权及带权路径长度：若将树中结点赋予一个有某种含义的数值，则这个数值称为该节点的权，结点的带权路径长度为：从根节点到该结点之间的路经长度与该节点的权的乘积。
树的带权路径长度：所有叶子节点的带权路径长度之和。记作WPL,权值越大的结点越靠近根节点，这棵树的WPL越小。
WPL最小的是哈夫曼树

哈夫曼树的创建

 /**
     * 哈夫曼树的创建
     * @param nodes 一个树结点组成的集合
     * @return 创建的书的根结点
     */
   public static  HuffmanNode  creatHuffmanTree (ArrayList<HuffmanNode> nodes){
        while (nodes.size()>1){
            //对节点集合进行排序由小到大
            nodes.sort((o1, o2) ->{
                return o1.value-o2.value;
            });

            //取出集合前两个元素 组成新的节点
            HuffmanNode left = nodes.remove(0);
            HuffmanNode right = nodes.remove(0);
            //新的节点添加到节点集合中
            HuffmanNode father = new HuffmanNode(left.value + right.value);
            father.right=right;
            father.left=left;
            nodes.add(father);
        }

        //返回哈夫曼树的根结点
        return nodes.get(0);
    }

哈夫曼编码

哈夫曼编码是一种前缀编码

前缀编码：是指对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，例如：设有abcd需要编码表示（其中，a=0、b=10、c=110、d=11,则表示110的前缀可以是c或者da，不唯一）

根据权值，构建以一个哈夫曼树。向左的路径为0向右的路径为1

压缩

 //用于存储生成的哈夫曼编码
    public static Map<Character,String> codeMap=new HashMap<>();

    public static void main(String[] args) {

        String s="sjdbfsakjfhadbdsfdkjfbkrytnbvyjvblzgvflkvbigadbvklvo";
        char[] chars = s.toCharArray();
        //统计出权重
        Map<Character, Integer> map = calculateWeight(chars);
        //创建哈夫曼结点集合
        ArrayList<HuffmanNode> nodes = new ArrayList<>();
        map.forEach((k,v)-> {
            nodes.add(new HuffmanNode(k,v));
        });
        
        //创建哈夫曼树
        HuffmanNode root = HuffmanTree.creatHuffmanTree(nodes);

        //生成哈夫曼编码
        creatHuffmanCode(root,"",new StringBuffer());
        codeMap.forEach((k,v)-> System.out.println("字母:"+k+"-编码:"+v));


    }

    public static Map<Character,Integer> calculateWeight(char[] arr){

       Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (Character s : arr) {
            Integer weight = map.get(s);
            if (weight==null){
                map.put(s,1);
            }else {
                map.put(s,++weight);
            }
        }
        return map;
    }
    public static void creatHuffmanCode(HuffmanNode node, String code,StringBuffer stringBuffer){
        stringBuffer.append(code);
        if (node!=null){
            if (node.value==null){
                creatHuffmanCode(node.left,"0",stringBuffer);
                creatHuffmanCode(node.right,"1",stringBuffer);
            }else {
                codeMap.put(node.value,stringBuffer.toString());
            }

        }
    }