本篇文章用来总结赫夫曼树的创建以及赫夫曼编码的生成。

1.结点的创建

结点类实现的方法主要有前序遍历、结点的比较,因为赫夫曼树的创建需要保持节点序列里结点从小到大的排列顺序。

class Node implements Comparable<Node>{
    Byte data;  //存放数据(字符)本身,比如a=》97
    int weight; //放权值,字符出现的次数
    Node left;
    Node right;

    public Node(Byte data, int weight){
        this.data = data;
        this.weight = weight;
    }

    //前序遍历
    public void preOrder(){
        System.out.println(this);
        if(this.left != null){
            this.left.preOrder();
        }
        if(this.right != null){
            this.right.preOrder();
        }
    }
		
  	//比较结点大小
    @Override
    public int compareTo(Node o) {
      	//从小到大排列
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
}

2.赫夫曼树的创建

2.1 创建结点数组

赫夫曼树的创建需要依赖一个结点序列(数组),下面是该数组的实现方式:

//创建结点数组
public static List<Node> getNodes(byte[] bytes){
    //1.创建一个ArrayList,用于存放节点
    ArrayList<Node> nodes = new ArrayList<>();

    //2.遍历bytes,统计每个字符出现的次数,用map来存储
    Map<Byte,Integer> counts = new HashMap<>();
    for(byte b : bytes){
        Integer count = counts.get(b);

        if(count == null){
            counts.put(b,1);
        }else{
            counts.put(b,count+1);
        }
    }

    //将每个键值对转换成Node对象,并加入到nodes
    //遍历map
    for(Map.Entry<Byte,Integer> entry : counts.entrySet()){
        nodes.add(new Node(entry.getKey(),entry.getValue()));
    }

    return nodes;
}

###2.2 创建树

之前在树的相关概念那篇文章里讲过赫夫曼树的创建步骤,下面的代码就是该步骤的实现,该函数传入的是未排序的结点序列,返回的是最终生成的赫夫曼树的根节点。可以看到,循环结束的条件是结点序列中只剩下一个根节点时。

//通过结点数组创建赫夫曼树
public static Node createhuffmanTree(List<Node> nodes){

    while (nodes.size()>1) {
        //对该数组进行排序
        Collections.sort(nodes);

        //取出权值最小的两个结点
        Node leftNode = nodes.get(0);
        Node rightNode = nodes.get(1);
        
        //构建一个新的二叉树,没有数据只有权值
        Node parentNode = new Node(null, leftNode.weight + rightNode.weight);
        parentNode.left = leftNode;
        parentNode.right = rightNode;

        //将取出的两个结点删除
        nodes.remove(leftNode);
        nodes.remove(rightNode);

        //将新创建的结点放入数组
        nodes.add(parentNode);
    }
    return nodes.get(0);
}

2.3 测试

有了节点数组和树的创建方式,我们就进行测试了:

public static void main(String[] args) {
    String content = "i like like like java do you like a java";
    byte[] contentByte = content.getBytes();
    System.out.println(contentByte.length);     //当前长度是40

    //获取结点数组
    List<Node> nodes = getNodes(contentByte);

    //获取赫夫曼树
    Node node = createhuffmanTree(nodes);

    //前序遍历
    preOrder(node);
}

前序遍历的代码:

//创建前序遍历
public static void preOrder(Node root){
    if(root != null){
        root.preOrder();
    }else{
        System.out.println("空树无法遍历");
    }
}

3. 赫夫曼编码的生成

有了赫夫曼树之后,我们就可以用它来生成赫夫曼编码:

//创建赫夫曼树对应的编码表
//1.将赫夫曼编码表存放在map中比较合适map<Byte,String>
static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
//2.在生成赫夫曼编码表时,需要拼接路径,因此定义一个StringBuilder来存储叶子结点路径
static StringBuilder stringBuilder = new StringBuilder();


/**
 * 将传入的node结点的所有叶子结点的赫夫曼编码得到,并放入huffmanCodes集合中
 * @param node  赫夫曼树结点
 * @param code  路径,左子树为0,右子树为1
 * @param stringBuilder 用于拼接路径
 */
private static void getCodes(Node node, String code, StringBuilder stringBuilder){
    StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);

    //将code加入StringBuilder1
    stringBuilder1.append(code);
    if(node != null){
        //判断节点是叶子结点还是非叶子结点
        if(node.data == null){
            //递归处理,向左递归
            getCodes(node.left,"0",stringBuilder1);
            //递归处理,向右递归
            getCodes(node.right,"1",stringBuilder1);
        }else{
            //叶子结点,将路径放入map
            huffmanCodes.put(node.data,stringBuilder1.toString());
        }
    }
}

然后使用下列代码进行测试:

//测试赫夫曼编码的生成
Map<Byte,String> huffmanCodes = getCodes(node);
System.out.println(huffmanCodes);