数据结构与算法---哈夫曼编码

package com.hfm.util;

public class HfmNode implements Comparable<HfmNode>{

     String chr;

     int weight;

    HfmNode left;

    HfmNode right;

    HfmNode parent;

    @Override
    public int compareTo(HfmNode o) {
        return this.weight - o.weight;
    }
}

package com.hfm.util;

import java.nio.charset.StandardCharsets;
import java.util.*;
import java.util.stream.Collectors;

public class HfmTree {

    HfmNode root;

    List<HfmNode> leafList;

    Map<String,Integer> direct;

    Map<String,String> dic = new HashMap<>();

    public HfmTree(Map<String, Integer> direct) {
        this.direct = direct;
        this.leafList = new ArrayList<>(direct.size());
        create();
    }

    public void encode(){
        leafList.stream().forEach(node -> {
            HfmNode current = node;
            String curStr = "";
            while(current.parent != null) {
                if(current == current.parent.left) {
                    curStr = "0" + curStr;
                }else {
                    curStr = "1" + curStr;
                }
                current = current.parent;
            }
            dic.put(curStr,node.chr);
            System.out.println(node.chr+" after encode:"+curStr);
        });
    }

    public void decode(String oxStr){
        String res = "";
        String curStr = "";
        HfmNode current = root,pre = null;
        for (char c : oxStr.toCharArray()) {
            curStr += c;
            if(dic.containsKey(curStr)){
                res += dic.get(curStr);
                curStr = "";
            }
        }
        System.out.println(oxStr+" after decode:"+res);
    }

    private void create(){
        PriorityQueue<HfmNode> priorityQueue = new PriorityQueue<>();
        String tags [] = direct.keySet().toArray(new String[0]);
        for (String item : tags) {
            HfmNode tmp = new HfmNode();
            tmp.weight = direct.get(item);
            tmp.chr = item;
            priorityQueue.add(tmp);
            leafList.add(tmp);
        }

        for (int i = 1; i < leafList.size(); i++) {
            HfmNode left = priorityQueue.poll();
            HfmNode right = priorityQueue.poll();
            HfmNode parent = new HfmNode();
            parent.chr = left.chr.concat(right.chr);
            parent.weight = left.weight + right.weight;
            left.parent = parent;
            right.parent = parent;
            parent.left = left;
            parent.right = right;
            priorityQueue.add(parent);
        }
        this.root = priorityQueue.poll();
    }

    public static void main(String[] args) {
        Map<String,Integer> integerMap = new HashMap<>();
        integerMap.put("a",3);
        integerMap.put("b",24);
        integerMap.put("c",6);
        integerMap.put("d",20);
        integerMap.put("e",34);
        integerMap.put("f",4);
        integerMap.put("g",12);
        HfmTree tree = new HfmTree(integerMap);
        tree.encode();
        //gecbaf
        String oxStr = "100111010011011010111";
        tree.decode(oxStr);
    }
}