酷酷是懒虫

这个屌丝很懒，什么也没留下！

热门标签

哈夫曼树(Huffman Tree,霍夫曼树,赫夫曼树)哈夫曼编码

作者：酷酷是懒虫 | 2024-06-26 06:27:28

踩

霍夫曼树

哈夫曼树的相关概念：

重要概念：

二叉树的带权路径长度：（叶子节点的路径长度 * 相应叶子节点的权值）之和
哈夫曼树：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

在这里插入图片描述

哈夫曼树的特点：

节点的度：子节点的个数

哈夫曼树的特点：

权值越大的叶子节点越靠近根节点，而权值越小的叶子节点越远离根节点。
只有子节点的个数为0的和子节点的个数为2的节点，不存在度为1的节点。

在这里插入图片描述

哈夫曼算法基本思想（重要）：

在这里插入图片描述

哈夫曼树的构建过程：

在这里插入图片描述

哈夫曼树的存贮结构：

在这里插入图片描述

代码实现构建哈夫曼树：

package com.fan.tree;
import java.util.ArrayList;
import java.util.Collections;

public class HuffmanTreeTest {
    public static void main(String[] args) {
        int[] arr ={13,7,8,3,29,6,1};
        HuffmanTree huffmanTree = new HuffmanTree();
        Node root = huffmanTree.createHuffmanTree(arr);
        System.out.println("哈夫曼树构建后，进行前序遍历进行验证：");
        huffmanTree.preOrder(root);
    }
}
class HuffmanTree{
    //前序遍历的方法
    public  void preOrder(Node root){
        if(root != null){
            root.preOrder();
        }else{
            System.out.println("是空树，不能遍历！！");
        }
    }
    //构建霍夫曼树的方法
    /**
     *
     * @param arr 一个权值数组
     * @return :哈夫曼树的根节点
     */
    public Node createHuffmanTree(int[] arr){
        //注意：这里的数组中放的是节点。
        /*
        一、初始化：构造只有根节点的 二叉树  集合
         */
        //1.遍历数组，将数组中的每个元素构成一个Node
        //2.将Node放入到ArrayList中
        ArrayList<Node> nodes = new ArrayList<>();
        for (int value : arr) {
            nodes.add(new Node(value));
        }
        /*
        当二叉树集合中只剩下一颗二叉树的时候，
        这颗二叉树就是哈夫曼树，所以我们这里用循环
         */
        while(nodes.size() > 1) {
        /*
        二、选取与合并：在只有根节点的 集合中，选取根节点的权值最小
        的两个节点 分别作为左右子树构造一个新的二叉树，且新构造的二叉树的
        根节点的权值为左右子树的权值之和
         */
            //将数组中的节点的权值从小到大排序
            Collections.sort(nodes);
            System.out.println("节点集合排序后：" + nodes);

            Node leftNode = nodes.get(0);//排序后的直接获取最小和次小的节点
            Node rightNode = nodes.get(1);
            //构建选取的那两个子树的 父/根节点
            Node parent = new Node(leftNode.weight + rightNode.weight);
            //设置这个新的二叉树的 左右子树
            parent.left = leftNode;
            parent.right = rightNode;
        /*
        三、删除与加入：在节点集合中，删除作为左右子树的两颗二叉树，
        并将新建立的二叉树加入到二叉树集合中
         */
            //从二叉树集合中 删除处理过的 二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将parent加入到 nodes二叉树集合中
            nodes.add(parent);
        /*
        四、重复二三两步，当二叉树集合中只剩下一颗二叉树的时候，
        这颗二叉树就是哈夫曼树，所以我们这里用循环
         */
        }//end-while
        //返回哈夫曼树的root节点
        return nodes.get(0);
    }
}
//节点是可排序的，实现可排序接口
class Node implements Comparable<Node>{
    int weight;//节点的权值
    Node left;//指向左子树的节点
    Node right;//指向右子树的节点

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

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

    @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();
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

霍夫曼编码,赫夫曼编码:

在这里插入图片描述

哈夫曼编码是无损的处理方案。

在这里插入图片描述

哈夫曼编码的思路：
在这里插入图片描述
代码：

package com.fan.tree.haffumantree;
import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
    String str = "i like like like java do you like a java";
    //将字符串转成字节数组
        byte[] strBytes = str.getBytes();
        System.out.println(strBytes.length);//40字节长度
        List<Node> nodes = getNodes(strBytes);//构建list集合
        System.out.println("nodes="+nodes);
        //测试
        System.out.println("哈夫曼树");
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        System.out.println("前序遍历：");
        preOrder(huffmanTreeRoot);//二叉树的遍历,调用静态方法
    }

    //前序遍历的方法
    private static void preOrder(Node root){
        if(root != null){
            root.preOrder();
        }else{
            System.out.println("树为空！！！");
        }
    }
    /**
     * 方法作用：将字节数组装成map形式存储，key是字母的字节本身，
     * value是出现的次数，然后将其每个封装成Node，并添加到list中
     *
     * @param bytes
     * @return list集合，其中存放的是Node
     */
    private static List<Node>  getNodes(byte[] bytes){
        //1.创建一个Arraylist
        ArrayList<Node> nodes = new ArrayList<>();
        //遍历bytes,统计每一个byte出现的次数，并放入到map中,map【k，v】
        HashMap<Byte, Integer> map = new HashMap<>();
        //for的作用是将byte数组中的字节以map形式存储，value是该字节出现的次数
        for (byte aByte : bytes) {
            Integer count = map.get(aByte);//开始是null,通过key,获取对应的value
            //给map中的value赋值，即出现的次数
            if(count ==null ){//map中还没有这个字符，第一次出现
                map.put(aByte,1);//存入到map中
            }else{
                map.put(aByte,count+1);//出现多次
            }
        }
        //把每一个键值对 转成一个NOde(date,weight属性) 对象，并加到我list集合nodes中
        //遍历map
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            //Node(T data, int weight)构造方法
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

    /**
     * 构建一个哈夫曼树
     * @param nodes list集合，其中存的是Node节点的二叉树
     * @return 赶回二叉树的根节点
     */
    private static Node createHuffmanTree(List<Node> nodes){
    //1.初始化，即准备List集合，这里参数已经准备好了
        while(nodes.size() > 1){
            //排序后就好选取了
            Collections.sort(nodes);//从小到大排序的
            //2.选取与合并
            Node leftNode = nodes.get(0);//选取结合中的第一个元素，即最小权值的
            Node rightNode = nodes.get(1);
            Node<Byte> parent = new Node<>(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //3.删除与加入
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);//将新的二叉树加入到结合Node集合中
        }
        return nodes.get(0);//返回唯一的根节点，也就是哈夫曼树的根节点
    }
}

//节点类
class Node<T> implements Comparable<Node<T>>{
    T data;//存放的数据（如字符，a--97）
    int weight;//权值
    Node<T> left;//左子树节点
    Node<T> right;//右子树节点

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

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

    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.weight - o.weight;
    }
    //前序遍历
    public void preOrder(){
        //根，左右
        //根：输出当前节点this,即正在调用的节点
        System.out.println(this);
        //左:当前节点的左子树不为空，继续向下遍历
        if(this.left != null){
            this.left.preOrder();
        }
        //左:当前节点的右子树不为空，继续向下遍历
        if(this.right != null){
            this.right.preOrder();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

打印结果：

在这里插入图片描述
哈夫曼编码实现：

在这里插入图片描述
生成哈夫曼编码表代码：

package com.fan.tree.haffumantree;
import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
    String str = "i like like like java do you like a java";
    //将字符串转成字节数组
        byte[] strBytes = str.getBytes();
        System.out.println(strBytes.length);//40字节长度
        List<Node> nodes = getNodes(strBytes);//构建list集合
        System.out.println("nodes="+nodes);
        //测试
        System.out.println("哈夫曼树");
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        System.out.println("前序遍历：");
        preOrder(huffmanTreeRoot);//二叉树的遍历,调用静态方法
        //测试是否生成了对应的哈夫曼编码表
        haffumanCodesMap = getCodesMap(huffmanTreeRoot, "", stringBuilder);
        System.out.println("生成的哈夫曼编码表："+haffumanCodesMap);
    }

    //前序遍历的方法
    private static void preOrder(Node root){
        if(root != null){
            root.preOrder();
        }else{
            System.out.println("树为空！！！");
        }
    }
    /**
     * 方法作用：将字节数组装成map形式存储，key是字母的字节本身，
     * value是出现的次数，然后将其每个封装成Node，并添加到list中
     *
     * @param bytes
     * @return list集合，其中存放的是Node
     */
    private static List<Node>  getNodes(byte[] bytes){
        //1.创建一个Arraylist
        ArrayList<Node> nodes = new ArrayList<>();
        //遍历bytes,统计每一个byte出现的次数，并放入到map中,map【k，v】
        HashMap<Byte, Integer> map = new HashMap<>();
        //for的作用是将byte数组中的字节以map形式存储，value是该字节出现的次数
        for (byte aByte : bytes) {
            Integer count = map.get(aByte);//开始是null,通过key,获取对应的value
            //给map中的value赋值，即出现的次数
            if(count ==null ){//map中还没有这个字符，第一次出现
                map.put(aByte,1);//存入到map中
            }else{
                map.put(aByte,count+1);//出现多次
            }
        }
        //把每一个键值对 转成一个NOde(date,weight属性) 对象，并加到我list集合nodes中
        //遍历map
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            //Node(T data, int weight)构造方法
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

    /**
     * 构建一个哈夫曼树
     * @param nodes list集合，其中存的是Node节点的二叉树
     * @return 赶回二叉树的根节点
     */
    private static Node createHuffmanTree(List<Node> nodes){
    //1.初始化，即准备List集合，这里参数已经准备好了
        while(nodes.size() > 1){
            //排序后就好选取了
            Collections.sort(nodes);//从小到大排序的
            //2.选取与合并
            Node leftNode = nodes.get(0);//选取结合中的第一个元素，即最小权值的
            Node rightNode = nodes.get(1);
            Node<Byte> parent = new Node<>(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //3.删除与加入
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);//将新的二叉树加入到结合Node集合中
        }
        return nodes.get(0);//返回唯一的根节点，也就是哈夫曼树的根节点
    }
    //利用哈夫曼树 生成对应的哈夫曼编码表
    /*
    思路：
    1.将哈夫曼编码表存放到Map中，形式32->01  97->100 100->11000等等
        key是字符的byte,value是字符对应的的哈夫曼编码
     */
    static Map<Byte,String> haffumanCodesMap= new HashMap<Byte,String>();
    //2.在生成的哈夫曼编码的时候，需要拼接路径，
    //定义一个StringBuilder来存储叶子节点的路径
    static StringBuilder stringBuilder = new StringBuilder();

    /**
     * 
     * @param node 传入节点
     * @param code 路径：左子节点是0，右子节点是1
     * @param stringBuilder  用于拼接路径
     */
    private static Map<Byte,String> getCodesMap(Node<Byte> node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        //将code加入到stringBuilder2
        stringBuilder2.append(code);//追加
        if(node != null){//如果node==null,不处理
            //判断当前node 是叶子节点还是非叶子节点
            if(node.data == null){//非叶子节点：数据域为空，权值不为空
                //递归处理，向左递归
                getCodesMap(node.left,"0",stringBuilder2);
                //递归处理，向右递归
                getCodesMap(node.right,"1",stringBuilder2);
            }else{//处理叶子节点
                //key是字符的byte,value是字符对应的的哈夫曼编码，String类型的
                haffumanCodesMap.put(node.data,stringBuilder2.toString());
            }
        }
        return haffumanCodesMap;
    }
}

//节点类
class Node<T> implements Comparable<Node<T>>{
    T data;//存放的数据（如字符，a--97）
    int weight;//权值
    Node<T> left;//左子树节点
    Node<T> right;//右子树节点

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

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

    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.weight - o.weight;
    }
    //前序遍历
    public void preOrder(){
        //根，左右
        //根：输出当前节点this,即正在调用的节点
        System.out.println(this);
        //左:当前节点的左子树不为空，继续向下遍历
        if(this.left != null){
            this.left.preOrder();
        }
        //左:当前节点的右子树不为空，继续向下遍历
        if(this.right != null){
            this.right.preOrder();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

在这里插入图片描述

package com.fan.tree.haffumantree;
import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
    String str = "i like like like java do you like a java";
    //将字符串转成字节数组
        byte[] strBytes = str.getBytes();
        System.out.println(strBytes.length);//40字节长度
        /*
        List<Node> nodes = getNodes(strBytes);//构建list集合
        System.out.println("nodes="+nodes);
        //测试
        System.out.println("哈夫曼树");
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        System.out.println("前序遍历：");
        preOrder(huffmanTreeRoot);//二叉树的遍历,调用静态方法
        //测试是否生成了对应的哈夫曼编码表
        haffumanCodesMap = getHaffumanCodesMap(huffmanTreeRoot, "", stringBuilder);
        System.out.println("生成的哈夫曼编码表："+haffumanCodesMap);
        //测试
        byte[] huffmanCodeBytes = zip(strBytes, haffumanCodesMap);
        System.out.println("huffmanCodeBytes="+ Arrays.toString(huffmanCodeBytes));//17字节
        */
        byte[] haffumanCodesBytes = huffmanZip(strBytes);
        System.out.println("压缩后的结果是--："+Arrays.toString(haffumanCodesBytes)+
                "，长度="+haffumanCodesBytes.length);
    }

    //使用一个方法，将前面的方法封装起来，方便我们调用
    private static byte[] huffmanZip(byte[] bytes){
        List<Node> nodes = getNodes(bytes);
        //根据nodes创建 哈夫曼树
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        //根据哈夫曼树 创建  对应的 哈夫曼编码表 map表
        Map<Byte,String> haffumanCodesMap =
                getHaffumanCodesMap(huffmanTreeRoot);
        //根据生成的 哈夫曼编码表，亚索得到 压缩后的 哈夫曼编码字节数组
        byte[] haffumanCodesBytes = zip(bytes, haffumanCodesMap);
        return haffumanCodesBytes;
    }

    //前序遍历的方法
    private static void preOrder(Node root){
        if(root != null){
            root.preOrder();
        }else{
            System.out.println("树为空！！！");
        }
    }
    /**
     * 二、方法作用：将字节数组装成map形式存储，key是字母的字节本身，
     * value是出现的次数，然后将其每个封装成Node，并添加到list中
     *
     * @param bytes
     * @return list集合，其中存放的是Node
     */
    private static List<Node>  getNodes(byte[] bytes){
        //1.创建一个Arraylist
        ArrayList<Node> nodes = new ArrayList<>();
        //遍历bytes,统计每一个byte出现的次数，并放入到map中,map【k，v】
        HashMap<Byte, Integer> map = new HashMap<>();
        //for的作用是将byte数组中的字节以map形式存储，value是该字节出现的次数
        for (byte aByte : bytes) {
            Integer count = map.get(aByte);//开始是null,通过key,获取对应的value
            //给map中的value赋值，即出现的次数
            if(count ==null ){//map中还没有这个字符，第一次出现
                map.put(aByte,1);//存入到map中
            }else{
                map.put(aByte,count+1);//出现多次
            }
        }
        //把每一个键值对 转成一个NOde(date,weight属性) 对象，并加到我list集合nodes中
        //遍历map
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            //Node(T data, int weight)构造方法
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

    /**
     * 三、构建一个哈夫曼树
     * @param nodes list集合，其中存的是Node节点的二叉树
     * @return 赶回二叉树的根节点
     */
    private static Node createHuffmanTree(List<Node> nodes){
    //1.初始化，即准备List集合，这里参数已经准备好了
        while(nodes.size() > 1){
            //排序后就好选取了
            Collections.sort(nodes);//从小到大排序的
            //2.选取与合并
            Node leftNode = nodes.get(0);//选取结合中的第一个元素，即最小权值的
            Node rightNode = nodes.get(1);
            Node<Byte> parent = new Node<>(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //3.删除与加入
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);//将新的二叉树加入到结合Node集合中
        }
        return nodes.get(0);//返回唯一的根节点，也就是哈夫曼树的根节点
    }
    //利用哈夫曼树 生成对应的哈夫曼编码表
    /*
    思路：
    1.将哈夫曼编码表存放到Map中，形式32->01  97->100 100->11000等等
        key是字符的byte,value是字符对应的的哈夫曼编码
     */
    static Map<Byte,String> haffumanCodesMap= new HashMap<Byte,String>();
    //2.在生成的哈夫曼编码的时候，需要拼接路径，
    //定义一个StringBuilder来存储叶子节点的路径
    static StringBuilder stringBuilder = new StringBuilder();
    //getHaffumanCodesMap重载的方法--为了方便调用
    private static Map<Byte,String> getHaffumanCodesMap(Node<Byte> node){
        Map<Byte, String> haffumanCodesMap =
                getHaffumanCodesMap(node, "", stringBuilder);
        return haffumanCodesMap;
    }

        /**
         * 四、方法作用：利用哈夫曼树 生成对应的哈夫曼编码表，map表
         * @param node 传入节点
         * @param code 路径：左子节点是0，右子节点是1
         * @param stringBuilder  用于拼接路径
         */
    private static Map<Byte,String> getHaffumanCodesMap
    (Node<Byte> node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        //将code加入到stringBuilder2
        stringBuilder2.append(code);//追加
        if(node != null){//如果node==null,不处理
            //判断当前node 是叶子节点还是非叶子节点
            if(node.data == null){//非叶子节点：数据域为空，权值不为空
                //递归处理，向左递归
                getHaffumanCodesMap(node.left,"0",stringBuilder2);
                //递归处理，向右递归
                getHaffumanCodesMap(node.right,"1",stringBuilder2);
            }else{//处理叶子节点
                //key是字符的byte,value是字符对应的的哈夫曼编码，String类型的
                haffumanCodesMap.put(node.data,stringBuilder2.toString());
            }
        }
        return haffumanCodesMap;
    }

    /**
     *  五、将原始字节数组  利用 哈夫曼编码表 进行 编码，
     * 返回压缩后的 字节数组
     * @param bytes 原始的字符串对应的byte[]
     * @param haffumanCodesMap 生成的哈夫曼编码表map
     * @return 返回一个哈夫曼编码 压缩后的 字节数组
     */
    private static byte[] zip(byte[] bytes,Map<Byte,String> haffumanCodesMap){
        //1.利用haffumanCodesMap  将 bytes 转成 哈夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //遍历bytes 数组,将所有字符对应的哈夫曼编码穿到一个字符串中
        for (byte aByte : bytes) {
            //haffumanCodesMap.get(aByte)：字符对应的哈夫曼编码
            stringBuilder.append(haffumanCodesMap.get(aByte));
        }
        System.out.println("测试stringbuilder:"+stringBuilder.toString());
        /*
        将"11010001111..."转成对应的byte数组，便于网络传输
        统计返回byte[] haffumanCodesMapBytes长度
         */
        int len;
        //一句话：int len =( stringBuilder.length() +7 ) /8
        if(stringBuilder.length() % 8 == 0){
            len = stringBuilder.length() / 8;//8位字符组成 一个字节
        }else{
            len = stringBuilder.length() / 8 + 1;
        }
        //创建存储压缩后 的byte数组
        byte[] haffumanCodesBytes = new byte[len];
        int index = 0;//记录是第几个byte
        for (int i = 0; i < stringBuilder.length(); i+=8) {
            String strByte;
            if(i+8 > stringBuilder.length()){
                //stringBuilder长度不够8位
                strByte = stringBuilder.substring(i);//从i开始到末尾截取
            }else{
                strByte = stringBuilder.substring(i,i+8);//截取8位
            }
            //将strByte 转成一个byte,放入到haffumanCodesMapBytes
            //Integer.parseInt(strByte,2):将一个字符串如1001 1001 按照二进制转成int
            //string-->int -->byte然后放入byte数组中
            haffumanCodesBytes[index] = (byte)Integer.parseInt(strByte,2);
            index++;
        }
        return haffumanCodesBytes;
    }
}

//一、节点类
class Node<T> implements Comparable<Node<T>>{
    T data;//存放的数据（如字符，a--97）
    int weight;//权值
    Node<T> left;//左子树节点
    Node<T> right;//右子树节点

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

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

    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.weight - o.weight;
    }
    //前序遍历
    public void preOrder(){
        //根，左右
        //根：输出当前节点this,即正在调用的节点
        System.out.println(this);
        //左:当前节点的左子树不为空，继续向下遍历
        if(this.left != null){
            this.left.preOrder();
        }
        //左:当前节点的右子树不为空，继续向下遍历
        if(this.right != null){
            this.right.preOrder();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235

数据解码：

在这里插入图片描述

代码实现解码：

package com.fan.tree.haffumantree;
import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
    String str = "i like like like java do you like a java";
    //将字符串转成字节数组
        byte[] strBytes = str.getBytes();
        System.out.println(strBytes.length);//40字节长度
        /*
        List<Node> nodes = getNodes(strBytes);//构建list集合
        System.out.println("nodes="+nodes);
        //测试
        System.out.println("哈夫曼树");
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        System.out.println("前序遍历：");
        preOrder(huffmanTreeRoot);//二叉树的遍历,调用静态方法
        //测试是否生成了对应的哈夫曼编码表
        haffumanCodesMap = getHaffumanCodesMap(huffmanTreeRoot, "", stringBuilder);
        System.out.println("生成的哈夫曼编码表："+haffumanCodesMap);
        //测试
        byte[] huffmanCodeBytes = zip(strBytes, haffumanCodesMap);
        System.out.println("huffmanCodeBytes="+ Arrays.toString(huffmanCodeBytes));//17字节个大小
        */
        byte[] haffumanCodesBytes = huffmanZip(strBytes);
        System.out.println("压缩后的结果是--："+Arrays.toString(haffumanCodesBytes)+
                "，长度="+haffumanCodesBytes.length);

        //测试解码
        byte[] decode = decode(haffumanCodesMap, haffumanCodesBytes);
        System.out.println("解码后："+new String(decode));//使用new String(byte[] b)
    }

    //使用一个方法，将前面的方法封装起来，方便我们调用
    private static byte[] huffmanZip(byte[] bytes){
        List<Node> nodes = getNodes(bytes);
        //根据nodes创建 哈夫曼树
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        //根据哈夫曼树 创建  对应的 哈夫曼编码表 map表
        Map<Byte,String> haffumanCodesMap =
                getHaffumanCodesMap(huffmanTreeRoot);
        //根据生成的 哈夫曼编码表，亚索得到 压缩后的 哈夫曼编码字节数组
        byte[] haffumanCodesBytes = zip(bytes, haffumanCodesMap);
        return haffumanCodesBytes;
    }

    //前序遍历的方法
    private static void preOrder(Node root){
        if(root != null){
            root.preOrder();
        }else{
            System.out.println("树为空！！！");
        }
    }
    /**
     * 二、方法作用：将字节数组装成map形式存储，key是字母的字节本身，
     * value是出现的次数，然后将其每个封装成Node，并添加到list中
     *
     * @param bytes
     * @return list集合，其中存放的是Node
     */
    private static List<Node>  getNodes(byte[] bytes){
        //1.创建一个Arraylist
        ArrayList<Node> nodes = new ArrayList<>();
        //遍历bytes,统计每一个byte出现的次数，并放入到map中,map【k，v】
        HashMap<Byte, Integer> map = new HashMap<>();
        //for的作用是将byte数组中的字节以map形式存储，value是该字节出现的次数
        for (byte aByte : bytes) {
            Integer count = map.get(aByte);//开始是null,通过key,获取对应的value
            //给map中的value赋值，即出现的次数
            if(count ==null ){//map中还没有这个字符，第一次出现
                map.put(aByte,1);//存入到map中
            }else{
                map.put(aByte,count+1);//出现多次
            }
        }
        //把每一个键值对 转成一个NOde(date,weight属性) 对象，并加到我list集合nodes中
        //遍历map
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            //Node(T data, int weight)构造方法
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

    /**
     * 三、构建一个哈夫曼树
     * @param nodes list集合，其中存的是Node节点的二叉树
     * @return 赶回二叉树的根节点
     */
    private static Node createHuffmanTree(List<Node> nodes){
    //1.初始化，即准备List集合，这里参数已经准备好了
        while(nodes.size() > 1){
            //排序后就好选取了
            Collections.sort(nodes);//从小到大排序的
            //2.选取与合并
            Node leftNode = nodes.get(0);//选取结合中的第一个元素，即最小权值的
            Node rightNode = nodes.get(1);
            Node<Byte> parent = new Node<>(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //3.删除与加入
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);//将新的二叉树加入到结合Node集合中
        }
        return nodes.get(0);//返回唯一的根节点，也就是哈夫曼树的根节点
    }
    //利用哈夫曼树 生成对应的哈夫曼编码表
    /*
    思路：
    1.将哈夫曼编码表存放到Map中，形式32->01  97->100 100->11000等等
        key是字符的byte,value是字符对应的的哈夫曼编码
     */
    static Map<Byte,String> haffumanCodesMap= new HashMap<Byte,String>();
    //2.在生成的哈夫曼编码的时候，需要拼接路径，
    //定义一个StringBuilder来存储叶子节点的路径
    static StringBuilder stringBuilder = new StringBuilder();
    //getHaffumanCodesMap重载的方法--为了方便调用
    private static Map<Byte,String> getHaffumanCodesMap(Node<Byte> node){
        Map<Byte, String> haffumanCodesMap =
                getHaffumanCodesMap(node, "", stringBuilder);
        return haffumanCodesMap;
    }

        /**
         * 四、方法作用：利用哈夫曼树 生成对应的哈夫曼编码表，map表
         * @param node 传入节点
         * @param code 路径：左子节点是0，右子节点是1
         * @param stringBuilder  用于拼接路径
         */
    private static Map<Byte,String> getHaffumanCodesMap(Node<Byte> node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        //将code加入到stringBuilder2
        stringBuilder2.append(code);//追加
        if(node != null){//如果node==null,不处理
            //判断当前node 是叶子节点还是非叶子节点
            if(node.data == null){//非叶子节点：数据域为空，权值不为空
                //递归处理，向左递归
                getHaffumanCodesMap(node.left,"0",stringBuilder2);
                //递归处理，向右递归
                getHaffumanCodesMap(node.right,"1",stringBuilder2);
            }else{//处理叶子节点
                //key是字符的byte,value是字符对应的的哈夫曼编码，String类型的
                haffumanCodesMap.put(node.data,stringBuilder2.toString());
            }
        }
        return haffumanCodesMap;
    }

    /**
     *  五、将原始字节数组  利用 哈夫曼编码表 进行 编码，
     * 返回压缩后的 字节数组
     * @param bytes 原始的字符串对应的byte[]
     * @param haffumanCodesMap 生成的哈夫曼编码表map
     * @return 返回一个哈夫曼编码 压缩后的 字节数组
     */
    private static byte[] zip(byte[] bytes,Map<Byte,String> haffumanCodesMap){
        //1.利用haffumanCodesMap  将 bytes 转成 哈夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //遍历bytes 数组,将所有字符对应的哈夫曼编码穿到一个字符串中
        for (byte aByte : bytes) {
            //haffumanCodesMap.get(aByte)：字符对应的哈夫曼编码
            stringBuilder.append(haffumanCodesMap.get(aByte));
        }
        System.out.println("测试stringbuilder:"+stringBuilder.toString());
        /*
        将"11010001111..."转成对应的byte数组，便于网络传输
        统计返回byte[] haffumanCodesMapBytes长度
         */
        int len;
        //一句话：int len =( stringBuilder.length() +7 ) /8
        if(stringBuilder.length() % 8 == 0){
            len = stringBuilder.length() / 8;//8位字符组成 一个字节
        }else{
            len = stringBuilder.length() / 8 + 1;
        }
        //创建存储压缩后 的byte数组
        byte[] haffumanCodesBytes = new byte[len];
        int index = 0;//记录是第几个byte
        for (int i = 0; i < stringBuilder.length(); i+=8) {
            String strByte;
            if(i+8 > stringBuilder.length()){
                //stringBuilder长度不够8位
                strByte = stringBuilder.substring(i);//从i开始到末尾截取
            }else{
                strByte = stringBuilder.substring(i,i+8);//截取8位
            }
            //将strByte 转成一个byte,放入到haffumanCodesMapBytes
            //Integer.parseInt(strByte,2):将一个字符串如1001 1001 按照二进制转成int
            //string-->int -->byte然后放入byte数组中
            haffumanCodesBytes[index] = (byte)Integer.parseInt(strByte,2);
            index++;
        }
        return haffumanCodesBytes;
    }

    //-------------------------数据的解码-----------------------------------------

    /**
     *
     * @param b 传入的一个字节byte
     * @param flag:标识是否需要补高位，如果是true,表示需要补高位，false表示不补
     * @return :传入的字节 对应的二进制 字符串（注意是按补码返回）
     */
    private static String byteToBitString(boolean flag,byte b){
        //使用变量保存b
        int temp = b;//将b转成int,因为Integer.toBinaryString(int i)参数是int
        //如果是正数，我们还需要补高位
        if(flag){
            temp |= 256;//按位与 256，如1 0000 0000 | 0000 0001 -->1 0000 0001
        }
        //返回的是temp对应的二进制的补码
        String str = Integer.toBinaryString(temp);
        if(flag){
            return str.substring(str.length() -8);
        }else{
            return str;
        }
    }
    //
    private static byte[] decode(Map<Byte,String> huffmanCodesMap,
                                 byte[] haffumanCodesBytes){
        //1.先得到haffumanCodesBytes 对应的二进制字符串，形式10101000...
        StringBuilder stringBuilder = new StringBuilder();
        //将byte数组转成 二进制 的字符串
        for (int i = 0; i < haffumanCodesBytes.length; i++) {
            byte b = haffumanCodesBytes[i];//取出每一个字节
            //判断是不是最后一个字节
            boolean flag = (i == haffumanCodesBytes.length - 1);
            //不是最后一个字节，追加
            stringBuilder.append(byteToBitString(!flag,b));
        }
        System.out.println("hafuman字节数组对应的二进制字符串："+
                stringBuilder.toString());
        //把字符串 按照指定的哈夫曼编码表 进行解码
        //把哈夫曼编码表 进行调换，因为要反向查询 a->100 ,100->a
        HashMap<String, Byte> map = new HashMap<>();//反向的存储结构
        for (Map.Entry<Byte, String> entry : huffmanCodesMap.entrySet()) {
            map.put(entry.getValue(),entry.getKey());
        }
        System.out.println("map="+map);
        //创建 给定集合，存放byte
        ArrayList<Byte> list = new ArrayList<>();
        //i 可以理解为索引，扫描stringBuilder
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1;//小的计数器
            boolean flag = true;
            Byte b = null;
            while(flag){
                //i 不动哦那个，让count移动，指定匹配到一个字符
                //递增的取出 key 1
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if(b == null){//说明没有匹配到
                    count++;
                }else{//匹配到
                    flag = false;
                }
            }
            list.add(b);
            i+= count;//i直接移动到count
        }
        //当for循环结束后，我们list中就存放了所有的字符"1 like like like..."
        byte[] b = new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            //把list中的数据 放入到byte[] 并返回
            b[i] = list.get(i);
        }
        return b;
    }
}

//一、节点类
class Node<T> implements Comparable<Node<T>>{
    T data;//存放的数据（如字符，a--97）
    int weight;//权值
    Node<T> left;//左子树节点
    Node<T> right;//右子树节点

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

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

    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.weight - o.weight;
    }
    //前序遍历
    public void preOrder(){
        //根，左右
        //根：输出当前节点this,即正在调用的节点
        System.out.println(this);
        //左:当前节点的左子树不为空，继续向下遍历
        if(this.left != null){
            this.left.preOrder();
        }
        //左:当前节点的右子树不为空，继续向下遍历
        if(this.right != null){
            this.right.preOrder();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313

在这里插入图片描述

最终测试结果：
在这里插入图片描述

文件压缩：如图片压缩:

在这里插入图片描述

//文件的压缩方法
    public static void zipFile(String srcFile,String desFile){
        //创建输出流
        FileOutputStream os = null;
        //创建对象输出流
        ObjectOutputStream oos = null;
        //创建文件的输入流
        FileInputStream is = null;
        try{
            //创建文件的输入流
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一样的byte[],将源文件转成字节数组
            byte[] b = new byte[is.available()];
            //读取文件,读取源文件的字节数组
            is.read(b);
            //直接对源文件压缩
            byte[] huffmanBytes = huffmanZip(b);//压缩字节数组
            //创建文件的输出流，存放压缩文件
            os = new FileOutputStream(desFile);
            oos = new ObjectOutputStream(os);
            //把哈夫曼编码后的字节数组 写入到压缩文件
            oos.writeObject(huffmanBytes);
            //再写入一个编码表对象
            oos.writeObject(haffumanCodesMap);
        }catch (Exception e){
            try {
                oos.close();
                os.close();
                is.close();
            }catch (Exception ex){
                ex.printStackTrace();
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

在这里插入图片描述

最终代码：(无法解压文件：)

package com.fan.tree.haffumantree;
import java.io.*;
import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
    String str = "i like like like java do you like a java";
    //将字符串转成字节数组
        byte[] strBytes = str.getBytes();
        System.out.println(strBytes.length);//40字节长度
        /*
        List<Node> nodes = getNodes(strBytes);//构建list集合
        System.out.println("nodes="+nodes);
        //测试
        System.out.println("哈夫曼树");
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        System.out.println("前序遍历：");
        preOrder(huffmanTreeRoot);//二叉树的遍历,调用静态方法
        //测试是否生成了对应的哈夫曼编码表
        haffumanCodesMap = getHaffumanCodesMap(huffmanTreeRoot, "", stringBuilder);
        System.out.println("生成的哈夫曼编码表："+haffumanCodesMap);
        //测试
        byte[] huffmanCodeBytes = zip(strBytes, haffumanCodesMap);
        System.out.println("huffmanCodeBytes="+ Arrays.toString(huffmanCodeBytes));//17字节个大小
        */
        byte[] haffumanCodesBytes = huffmanZip(strBytes);
        System.out.println("压缩后的结果是--："+Arrays.toString(haffumanCodesBytes)+
                "，长度="+haffumanCodesBytes.length);

        //测试解码
        byte[] decode = decode(haffumanCodesBytes,haffumanCodesMap );
        System.out.println("解码后："+new String(decode));//使用new String(byte[] b)
        //测试压缩文件
        /*String srcFile = "d://test.bmp";
        String desFile = "d://des2.zip";
        zipFile(srcFile,desFile);
        System.out.println("压缩文件完毕！！！");*/
        //测试解码
        String zipFile = "d://des2.zip";
        String des2File = "d://src2.jpg";
        unZip(zipFile,des2File);
        System.out.println("解压成功");
    }

    //使用一个方法，将前面的方法封装起来，方便我们调用
    private static byte[] huffmanZip(byte[] bytes){
        //获取字母的权值，并封装到list中
        List<Node> nodes = getNodes(bytes);
        //根据nodes创建 哈夫曼树
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        //根据哈夫曼树 创建  对应的 哈夫曼编码表 map表
        Map<Byte,String> haffumanCodesMap =
                getHaffumanCodesMap(huffmanTreeRoot);
        //根据生成的 哈夫曼编码表，亚索得到 压缩后的 哈夫曼编码字节数组
        byte[] haffumanCodesBytes = zip(bytes, haffumanCodesMap);
        return haffumanCodesBytes;
    }

    //前序遍历的方法
    private static void preOrder(Node root){
        if(root != null){
            root.preOrder();
        }else{
            System.out.println("树为空！！！");
        }
    }
    /**
     * 二、方法作用：将字节数组装成map形式存储，key是字母的字节本身，
     * value是出现的次数，然后将其每个封装成Node，并添加到list中
     *
     * @param bytes
     * @return list集合，其中存放的是Node
     */
    private static List<Node>  getNodes(byte[] bytes){
        //1.创建一个Arraylist
        ArrayList<Node> nodes = new ArrayList<>();
        //遍历bytes,统计每一个byte出现的次数，并放入到map中,map【k，v】
        HashMap<Byte, Integer> map = new HashMap<>();
        //for的作用是将byte数组中的字节以map形式存储，value是该字节出现的次数
        for (byte aByte : bytes) {
            Integer count = map.get(aByte);//开始是null,通过key,获取对应的value
            //给map中的value赋值，即出现的次数
            if(count ==null ){//map中还没有这个字符，第一次出现
                map.put(aByte,1);//存入到map中
            }else{
                map.put(aByte,count+1);//出现多次
            }
        }
        //把每一个键值对 转成一个NOde(date,weight属性) 对象，并加到我list集合nodes中
        //遍历map
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            //Node(T data, int weight)构造方法
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

    /**
     * 三、构建一个哈夫曼树
     * @param nodes list集合，其中存的是Node节点的二叉树
     * @return 赶回二叉树的根节点
     */
    private static Node createHuffmanTree(List<Node> nodes){
    //1.初始化，即准备List集合，这里参数已经准备好了
        while(nodes.size() > 1){
            //排序后就好选取了
            Collections.sort(nodes);//从小到大排序的
            //2.选取与合并
            Node leftNode = nodes.get(0);//选取结合中的第一个元素，即最小权值的
            Node rightNode = nodes.get(1);
            Node<Byte> parent = new Node<>(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //3.删除与加入
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);//将新的二叉树加入到结合Node集合中
        }
        return nodes.get(0);//返回唯一的根节点，也就是哈夫曼树的根节点
    }
    //利用哈夫曼树 生成对应的哈夫曼编码表
    /*
    思路：
    1.将哈夫曼编码表存放到Map中，形式32->01  97->100 100->11000等等
        key是字符的byte,value是字符对应的的哈夫曼编码
     */
    static Map<Byte,String> haffumanCodesMap= new HashMap<Byte,String>();
    //2.在生成的哈夫曼编码的时候，需要拼接路径，
    //定义一个StringBuilder来存储叶子节点的路径
    static StringBuilder stringBuilder = new StringBuilder();
    //getHaffumanCodesMap重载的方法--为了方便调用
    private static Map<Byte,String> getHaffumanCodesMap(Node<Byte> root){
        if(root == null){
            return null;
        }
        //处理root左子树
        getHaffumanCodesMap(root.left,"0",stringBuilder);
        //处理root右子树
        getHaffumanCodesMap(root.right,"1",stringBuilder);
        return haffumanCodesMap;
    }

        /**
         * 四、方法作用：利用哈夫曼树 生成对应的哈夫曼编码表，map表
         * @param node 传入节点
         * @param code 路径：左子节点是0，右子节点是1
         * @param stringBuilder  用于拼接路径
         */
    private static void getHaffumanCodesMap(Node<Byte> node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        //将code加入到stringBuilder2
        stringBuilder2.append(code);//追加
        if(node != null){//如果node==null,不处理
            //判断当前node 是叶子节点还是非叶子节点
            if(node.data == null){//非叶子节点：数据域为空，权值不为空
                //递归处理，向左递归
                getHaffumanCodesMap(node.left,"0",stringBuilder2);
                //递归处理，向右递归
                getHaffumanCodesMap(node.right,"1",stringBuilder2);
            }else{//处理叶子节点
                //key是字符的byte,value是字符对应的的哈夫曼编码，String类型的
                haffumanCodesMap.put(node.data,stringBuilder2.toString());
            }
        }

    }

    /**
     *  五、将原始字节数组  利用 哈夫曼编码表 进行 编码，
     * 返回压缩后的 字节数组
     * @param bytes 原始的字符串对应的byte[]
     * @param haffumanCodesMap 生成的哈夫曼编码表map
     * @return 返回一个哈夫曼编码 压缩后的 字节数组
     */
    private static byte[] zip(byte[] bytes,Map<Byte,String> haffumanCodesMap){
        //1.利用haffumanCodesMap  将 bytes 转成 哈夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //遍历bytes 数组,将所有字符对应的哈夫曼编码穿到一个字符串中
        for (byte aByte : bytes) {
            //haffumanCodesMap.get(aByte)：字符对应的哈夫曼编码
            stringBuilder.append(haffumanCodesMap.get(aByte));
        }
        System.out.println("测试stringbuilder:"+stringBuilder.toString());
        /*
        将"11010001111..."转成对应的byte数组，便于网络传输
        统计返回byte[] haffumanCodesMapBytes长度
         */
        int len;
        //一句话：int len =( stringBuilder.length() +7 ) /8
        if(stringBuilder.length() % 8 == 0){
            len = stringBuilder.length() / 8;//8位字符组成 一个字节
        }else{
            len = stringBuilder.length() / 8 + 1;
        }
        //创建存储压缩后 的byte数组
        byte[] haffumanCodesBytes = new byte[len];
        int index = 0;//记录是第几个byte
        for (int i = 0; i < stringBuilder.length(); i+=8) {
            String strByte;
            if(i+8 > stringBuilder.length()){
                //stringBuilder长度不够8位
                strByte = stringBuilder.substring(i);//从i开始到末尾截取
            }else{
                strByte = stringBuilder.substring(i,i+8);//截取8位
            }
            //将strByte 转成一个byte,放入到haffumanCodesMapBytes
            //Integer.parseInt(strByte,2):将一个字符串如1001 1001 按照二进制转成int
            //string-->int -->byte然后放入byte数组中
            haffumanCodesBytes[index] = (byte)Integer.parseInt(strByte,2);
            index++;
        }
        return haffumanCodesBytes;
    }

    //-------------------------数据的解码-----------------------------------------

    /**
     *
     * @param b 传入的一个字节byte
     * @param flag:标识是否需要补高位，如果是true,表示需要补高位，false表示不补
     * @return :传入的字节 对应的二进制 字符串（注意是按补码返回）
     */
    private static String byteToBitString(boolean flag,byte b){
        //使用变量保存b
        int temp = b;//将b转成int,因为Integer.toBinaryString(int i)参数是int
        //如果是正数，我们还需要补高位
        if(flag){
            temp |= 256;//按位与 256，如1 0000 0000 | 0000 0001 -->1 0000 0001
        }
        //返回的是temp对应的二进制的补码
        String str = Integer.toBinaryString(temp);
        if(flag){
            return str.substring(str.length() -8);
        }else{
            return str;
        }
    }
    //解压的方法
    private static byte[] decode(
                                 byte[] haffumanCodesBytes,
                                 Map<Byte,String> huffmanCodesMap){
        //1.先得到haffumanCodesBytes 对应的二进制字符串，形式10101000...
        StringBuilder stringBuilder = new StringBuilder();
        //将byte数组转成 二进制 的字符串
        for (int i = 0; i < haffumanCodesBytes.length; i++) {
            byte b = haffumanCodesBytes[i];//取出每一个字节
            //判断是不是最后一个字节
            boolean flag = (i == haffumanCodesBytes.length - 1);
            //不是最后一个字节，追加
            stringBuilder.append(byteToBitString(!flag,b));
        }
        System.out.println("hafuman字节数组对应的二进制字符串："+
                stringBuilder.toString());
        //把字符串 按照指定的哈夫曼编码表 进行解码
        //把哈夫曼编码表 进行调换，因为要反向查询 a->100 ,100->a
        HashMap<String, Byte> map = new HashMap<>();//反向的存储结构
        for (Map.Entry<Byte, String> entry : huffmanCodesMap.entrySet()) {
            map.put(entry.getValue(),entry.getKey());
        }
        System.out.println("map="+map);
        //创建 给定集合，存放byte
        ArrayList<Byte> list = new ArrayList<>();
        //i 可以理解为索引，扫描stringBuilder
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1;//小的计数器
            boolean flag = true;
            Byte b = null;
            while(flag){
                //i 不动哦那个，让count移动，指定匹配到一个字符
                //递增的取出 key 1
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if(b == null){//说明没有匹配到
                    count++;
                }else{//匹配到
                    flag = false;
                }
            }
            list.add(b);
            i+= count;//i直接移动到count
        }
        //当for循环结束后，我们list中就存放了所有的字符"1 like like like..."
        byte[] b = new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            //把list中的数据 放入到byte[] 并返回
            b[i] = list.get(i);
        }
        return b;
    }
    //文件的压缩方法
    public static void zipFile(String srcFile,String desFile){
        //创建输出流
        OutputStream os = null;
        //创建对象输出流
        ObjectOutputStream oos = null;
        //创建文件的输入流
        FileInputStream is = null;
        try{
            //创建文件的输入流
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一样的byte[],将源文件转成字节数组
            byte[] b = new byte[is.available()];
            //读取文件,读取源文件的字节数组
            is.read(b);
            //直接对源文件压缩
            byte[] huffmanBytes = huffmanZip(b);//压缩字节数组
            //创建文件的输出流，存放压缩文件
            os = new FileOutputStream(desFile);
            oos = new ObjectOutputStream(os);
            //1.把哈夫曼编码后的字节数组 写入到压缩文件
            oos.writeObject(huffmanBytes);
            //2.再写入一个编码表对象
            oos.writeObject(haffumanCodesMap);
        }catch (Exception e){
            try {
                is.close();
                oos.close();
                os.close();
            }catch (Exception ex){
                ex.printStackTrace();
            }
        }
    }
    //文件的解压

    /**
     *
     * @param zipFile 准备解压的文件
     * @param desFile 将文件解压到哪个路径
     */
    public static void unZip(String zipFile,String desFile){
        //定义文件输入流
        InputStream is =null;
        //定义一个对象输入流
        ObjectInputStream ois = null;
        //定义文件的输出流
        OutputStream os = null;
        try {
            //创建文件输入流
            is= new FileInputStream(zipFile);
            //创建一个和is关联的对象输入流
             ois = new ObjectInputStream(is);
             //1.读取byte数组，即压缩后的字节数组
            byte[] huffmanBytes = (byte[])ois.readObject();
            //2.再读取哈夫曼编码表97-->001等
            Map<Byte,String> huffmanCodesMap =
                    (Map<Byte,String>) ois.readObject();
            //解码
            byte[] bytes = decode(huffmanBytes,huffmanCodesMap);
            //将bytes 数组写入到 目标文件
             os = new FileOutputStream(desFile);
             //写数据到 desFile，os.write(byte b[])
            os.write(bytes);
        }catch (Exception e){
            System.out.println(e.getMessage());
        }finally {
            try {
                os.close();
                ois.close();
                is.close();
            }catch (Exception ex){
                System.out.println(ex.getMessage());
            }
        }

    }

}

//一、节点类
class Node<T> implements Comparable<Node<T>>{
    T data;//存放的数据（如字符，a--97）
    int weight;//权值
    Node<T> left;//左子树节点
    Node<T> right;//右子树节点

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

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

    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.weight - o.weight;
    }
    //前序遍历
    public void preOrder(){
        //根，左右
        //根：输出当前节点this,即正在调用的节点
        System.out.println(this);
        //左:当前节点的左子树不为空，继续向下遍历
        if(this.left != null){
            this.left.preOrder();
        }
        //左:当前节点的右子树不为空，继续向下遍历
        if(this.right != null){
            this.right.preOrder();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/758488

哈夫曼树(Huffman Tree,霍夫曼树,赫夫曼树)哈夫曼编码

目录

哈夫曼树的相关概念：

哈夫曼树的特点：

哈夫曼算法基本思想（重要）：

哈夫曼树的构建过程：

哈夫曼树的存贮结构：

霍夫曼编码,赫夫曼编码:

数据解码：

文件压缩：如图片压缩: