最佳实践-数据压缩(创建赫夫曼树)

将给出的一段文本,比如"i like like like java do you like a java",根据前面的赫夫曼编码原理,对其进行数据压缩处理,形式如"1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110"。
思路:
(1) Node { data{存放数据}, weight(权值), left和right }
(2) 得到"i like like like java do you like a java"对应的byte[]数组
(3) 编写一个方法,将准备构建赫夫曼树的Node结点放到一个list中,形式[Node[data=97,weight=5],Node[data=32,weight=9]],d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9
(4) 可以通过List创建对应的赫夫曼树

package com.young.huffmancode;

import java.util.*;

public class HuffmanTreeCode {

    public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        List<Node> nodes = getNodes(contentBytes);
        System.out.println(nodes);
        //测试一把,创建的二叉树
        System.out.println("赫夫曼树");
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        System.out.println("前序遍历");
        huffmanTreeRoot.preOrder();
    }

    /**
     * 前序遍历的方法
     */
    private static void preOrder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("赫夫曼树为空");
        }
    }

    /**
     * @param bytes 接收字节数组
     * @return 返回的就是List
     */
    private static List<Node> getNodes(byte[] bytes) {
        //1. 先创建一个ArrayList
        List<Node> nodes = new ArrayList<>();

        //2. 遍历bytes,统计每个byte出现的次数 -> map[key,value]
        Map<Byte, Integer> counts = new HashMap<>(16);
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) {
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }

        //3. 把每一个键值对转成一个Node对象,并加入到nodes集合
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }

        return nodes;

    }

    /**
     * 可以通过List,创建对应的赫夫曼树
     */
    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //排序,从小到大
            Collections.sort(nodes);
            //取出第一颗最小的二叉树
            Node leftNode = nodes.get(0);
            //取出第二颗最小的二叉树
            Node rightNode = nodes.get(1);
            //创建一颗新二叉树,它的根结点没有data,只有权值
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //将已经处理的两颗二叉树从nodes删除
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将parent加入到nodes
            nodes.add(parent);
        }
        //nodes最后的结点,就是赫夫曼数的根结点
        return nodes.get(0);
    }

}

/**
 * 创建Node,带数据和权值
 */
class Node implements Comparable<Node> {

    /**
     * 存放数据(字符)本身,比如'a' => 97
     */
    Byte data;
    /**
     * 权值,表示字符出现的次数
     */
    int weight;
    Node left;
    Node right;

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

    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.weight - o.weight;
    }

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

    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

}