博客

上一篇写的主要是关于如何根据给出的字节写出他的赫夫曼树.这一片是根据存在的字节转换成赫夫曼编码表

形式为:32->01 97->100 100->11000

新增的小段编码

   /**
     * 思路:
     * 1.将赫夫曼编码表放在Map<Byte,String >中
     * 形式为  32->01  97->100  100->11000
     */
    static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
    //  2.在生成赫夫曼编码表示,需要去拼接路径,定义一个StringBuilder,存储某个叶子节点的路径
    static StringBuilder stringBuilder = new StringBuilder();

    /**
     * @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 {

                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }
    }

目前为止总编码

import java.util.*;

public class HuffmanCodeDemo {
    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 = getNode(contentBytes);
        Node huffmanTree = createHuffmanTree(nodes);
        //System.out.println("前序遍历" );
        huffmanTree.preOrder();
//        getCodes(huffmanTree,"",stringBuilder);
//        System.out.println("生成的赫夫曼编码表"+huffmanCodes);
        Map<Byte, String> codes = getCodes(huffmanTree);
        System.out.println("生成的赫夫曼编码表" + codes);
    }

    //生成赫夫曼树对应的赫夫曼编码表
    //为了调用方便重载赫夫曼编码表
    private static Map<Byte, String> getCodes(Node root) {
        if (root == null) {
            return null;
        }
        //处理root左子树
        getCodes(root.left, "0", stringBuilder);
        //处理root右子树
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }

    /**
     * 思路:
     * 1.将赫夫曼编码表放在Map<Byte,String >中
     * 形式为  32->01  97->100  100->11000
     */
    static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
    //  2.在生成赫夫曼编码表示,需要去拼接路径,定义一个StringBuilder,存储某个叶子节点的路径
    static StringBuilder stringBuilder = new StringBuilder();

    /**
     * @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 {

                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }
    }

    private void preOrder(Node node) {
        if (node != null) {
            node.preOrder();
        } else {
            System.out.println("结点为空");
        }
    }

    /**
     * 传入字节数组返回结点
     *
     * @param bytes
     * @return
     */
    private static List<Node> getNode(byte[] bytes) {
        //1.创建一个Arraylist数组
        ArrayList<Node> nodes = new ArrayList<>();
        //创建map
        HashMap<Byte, Integer> map = new HashMap<>();
        //遍历数组将字节传入map中,并统计出现的次数
        for (byte b :
                bytes) {
            Integer count = map.get(b);
            if (count == null) {
                map.put(b, 1);
            } else {
                map.put(b, count + 1);
            }
        }

        //将字符放入结点中
        //遍历map
        for (Map.Entry<Byte, Integer> entry : map.entrySet()
                ) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }


    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.getWeight() + rightNode.getWeight());
            parentNode.setLeft(leftNode);
            parentNode.setRight(rightNode);

            //删除这两个数
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将该Node将入原先list中
            nodes.add(parentNode);

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

}

class Node implements Comparable<Node> {
    Byte data;   //进行数据的存储
    int weight;   //存储字符出现的次数
    Node left;
    Node right;

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

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

    public Byte getData() {
        return data;
    }

    public void setData(Byte data) {
        this.data = data;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

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

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

结果