我是根据B站尚硅谷韩顺平老师讲解的哈夫曼编码代码改写的

b站数据结构和算法
ps:虽然经常翻车（手动狗头） 但还是讲的不错的
因为老韩的解压二进制数组最后一位有bug 我改了一下，增加了一个约定，在要压缩的字符串对应的byte[]数组转为的二进制数组中首位加入了保存最后一位的长度（1-8） 并且约定解码的时候首位不用动 然后判断如果是最后一位了 不管是正数还是负数都要进行补位和截取 截取的长度取决于传入的最后一位的长度（1-8) 经过我的测试暂时是没有问题的 如果有更好的想法可以交流一下

public class Node implements Comparable<Node>{

    Byte data;  //存放数据的ASCII 'a' => 97
   int weight;  //权值 该数据出现的次数
   Node left;
   Node right;

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

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

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

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

public class HuffmanCode {

    //哈夫曼编码表
    public static Map<Byte,String> codeTable = new HashMap<Byte,String>();


        //将字节数组转为Node结点集合
        public static List<Node> getNodes(byte[] bytes){
            List<Node> nodes = new ArrayList<>();

            //遍历传入的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);
                }
            }

            //遍历map集合
            for (Map.Entry<Byte,Integer> entry: counts.entrySet()){
                nodes.add(new Node(entry.getKey(),entry.getValue()));
            }


            return nodes;
        }

     //根据Node结点集合 创建Huffman树
    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);
    }


    
    public static Map<Byte,String> getCodeTable(Node node){
        StringBuilder stringBuilder = new StringBuilder();
        Map<Byte, String> codeTable = getCodeTable(node, "", stringBuilder);
        return codeTable;
    }




    //生成Huffman树对应编码表
    //将Huffman编码表存放到Map<Byte,String>形式
    /**
     *
     * @param node  传入结点
     * @param code   路径 往左子节点是0 往右子节点是1
     * @param stringBuilder  用于拼接路径
     * @return
     */

    public static Map<Byte,String> getCodeTable(Node node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        stringBuilder2.append(code);

        if (node != null){
            if (node.data == null){ //非叶子节点
                //递归向左
                getCodeTable(node.left,"0",stringBuilder2);
                //递归向右
                getCodeTable(node.right,"1",stringBuilder2);
            }else {     //到叶子结点了
                //保存到map集合中
                codeTable.put(node.data,stringBuilder2.toString());

            }
        }

        return codeTable;
    }


    //我们在这约定 压缩后的byte数组中 首元素不用解码 它代表尾元素的二进制长度
    //i like like like java do you like a java
    //将字符串对应的byte[]数组(40)，通过哈夫曼编码表codeTable转为二进制byte数组(133)然后进行压缩，返回一个压缩后的byte[]数组
    //1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
    //然后压缩这133位二级制数字(将八位补码（计算机都是以补码存储数据的）转为一个字节传入byte[]数组)  传入byte[]数组并返回
    //huffmanCodeBytes[0] = -88  [10101000(补码) => 10100111(反码) => 11011000(原码) => -88(对应十进制数字)]

    /**
     *
     * @param bytes         字符串对应的byte[]数组
     * @param codeTable     哈夫曼编码表
     * @return              压缩后的byte[]数组
     */
    public static byte[] zip(byte[] bytes, Map<Byte,String> codeTable ){

        StringBuilder stringBuilder = new StringBuilder();

        for (byte b:bytes) {
            stringBuilder.append(codeTable.get(b));

        }


        int lastLength = stringBuilder.length()%8;



        int len;
        len = (stringBuilder.length() + 7 ) / 8;
        //+7 如果没有余数则还是原来的 如果有余数则长度+1
//        if (stringBuilder.length() % 8 == 0){
//            len = stringBuilder.length()/8;
//        }else {
//            len = stringBuilder.length()/8 + 1;
//        }

        byte[] huffmanCodeBytes = new byte[len+1];

        huffmanCodeBytes[0] = (byte) lastLength;

        for (int i = 0,index = 1; i < stringBuilder.length(); i+=8,index++) {
            String str ;
            if ( i+8 > stringBuilder.length() ){
                str =  stringBuilder.substring(i);
            }else {
                str = stringBuilder.substring(i, i + 8);
            }
            huffmanCodeBytes[index] = (byte)Integer.parseInt(str,2);

        }

        return huffmanCodeBytes;
    }

    public static byte[] huffmanZip(String str){
        //获取字符串对应的字节数组
        byte[] bytes = str.getBytes();

       return huffmanZip(bytes);

    }

    public static byte[] huffmanZip(byte[] bytes){
        //将字符数组转为Node结点集合
        List<Node> nodes = HuffmanCode.getNodes(bytes);

        //生成Huffman树
        Node huffmanCode = HuffmanCode.createHuffmanTree(nodes);

        //生成Huffman表
        Map<Byte, String> codeTable = HuffmanCode.getCodeTable(huffmanCode);

        //生成压缩后的Huffman数组
        byte[] zip = HuffmanCode.zip(bytes, codeTable);

        return zip;
    }


    public static byte[] decode(Map<Byte,String> huffmanCode,byte[] huffmanBytes){
        StringBuilder stringBuilder = new StringBuilder();

        //从下标为1开始解码 下标为0的代表压缩前byte数组最后一位长度
        for (int i = 1; i < huffmanBytes.length; i++) {
            byte huffmanByte = huffmanBytes[i];
            boolean flag = (i == huffmanBytes.length-1);
            stringBuilder.append(byteToBitString(!flag,huffmanByte,(int)huffmanBytes[0]));

        }
        //按照哈夫曼编码表进行解码
        //huffmanCode里面的键值对都是唯一对应的
        HashMap<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte,String> entry : huffmanCode.entrySet() ) {
                map.put(entry.getValue(), entry.getKey());
        }

        ArrayList<Byte> list = new ArrayList<>();

        int begin = 0;
        for (int i = 0; i < stringBuilder.length(); i++) {
            String key = stringBuilder.substring(begin,i+1);
                if (map.containsKey(key)){
                    list.add(map.get(key));
                    begin = i+1;
                }
        }

        byte[] bytes = new byte[list.size()];

        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = list.get(i);
        }

        return bytes;
    }
    private static String byteToBitString(boolean flag,byte b,int lastLength){
                int temp = b;
                //补高位
                //如果是负数还要截取！！！
                //最后一位都会进来补位
                     temp |= 256;  //按位与 保证符号位不参与运算 1 0000 0000 |  0000 0001 = 1 0000 0001


                 String s = Integer.toBinaryString(temp);

                        if (!flag){     //最后一位
                            return s.substring(s.length()-lastLength);
                        }
                            //否则
                      return s.substring(s.length()-8);

    }

    //压缩文件

    /**
     *
     * @param srcFile   要压缩文件的源地址
     * @param targetFile   压缩文件存放的目标地址
     * @throws Exception 压缩失败
     */
    public static void zipFile(String srcFile,String targetFile) throws Exception {
        FileInputStream fileInputStream = new FileInputStream(srcFile);

        FileOutputStream fileOutputStream = new FileOutputStream(targetFile);

        byte[] bytes = new byte[fileInputStream.available()];

        fileInputStream.read(bytes);

        byte[] bytes1 = HuffmanCode.huffmanZip(bytes);

        ObjectOutputStream objectOutputStream = new ObjectOutputStream(fileOutputStream);


        //传入压缩后的byte[]数组
        objectOutputStream.writeObject(bytes1);
        //传入编码表
        objectOutputStream.writeObject(HuffmanCode.codeTable);

        System.out.println("压缩成功");
    }

    //解压文件
    /**
     *
     * @param srcFile 要解压文件的源地址
     * @param targetFile   解压文件存放的目标地址
     * @throws Exception 解压失败
     */
    public static void unzipFile(String srcFile,String targetFile) throws Exception {
        FileInputStream fileInputStream = new FileInputStream(srcFile);

        FileOutputStream fileOutputStream = new FileOutputStream(targetFile);

        ObjectInputStream objectInputStream = new ObjectInputStream(fileInputStream);

        //压缩后的byte[]数组
        byte[] bytes = (byte[]) objectInputStream.readObject();

        //编码表
        Map<Byte,String> codeTable = (Map<Byte,String>)objectInputStream.readObject();


        //解码
        byte[] decode = HuffmanCode.decode(codeTable, bytes);
        fileOutputStream.write(decode);

        System.out.println("解码成功");

    }
}

public class Test {
    public static void main(String[] args) {
        String str = "i like like like java do you like a java sss";

        byte[] bytes = str.getBytes();

        HuffmanCode.huffmanZip(str);

        Map<Byte, String> codeTable = HuffmanCode.codeTable;

        System.out.println("编码表："+codeTable);

        //生成压缩后的Huffman数组
        byte[] zip = HuffmanCode.zip(bytes, codeTable);
        System.out.println("压缩后数组："+Arrays.toString(zip));

        byte[] decode = HuffmanCode.decode(codeTable, zip);

        System.out.println("原文："+new String(decode));

    }
}
```运行结果：
编码表：{32=01, 97=001, 100=10100, 101=1101, 105=100, 106=11001, 107=1110, 108=1111, 111=0000, 115=1011, 117=10101, 118=0001, 121=11000}
压缩后数组：[7, -113, -50, -41, -25, 107, -13, -75, -55, 18, -48, 28, 5, 95, -99, -87, 114, 68, -73, 59]
原文：i like like like java do you like a java sss

```压缩文件测试（没有问题，图片，中文文字，表格都可以还原）
public class FileCompressTest {
    public static void main(String[] args) throws Exception {
                //压缩文件
                HuffmanCode.zipFile("C:\\MyCode\\code.txt","F:\\file\\code.zip");
                //解压文件
                HuffmanCode.unzipFile("F:\\file\\code.zip","F:\\file\\code.txt");
    }
}

前言

文件压缩的概念在生活中已经屡见不鲜，在这个信息化的时代，我们每天的生活基本上离不开手机电脑，在手机或电脑上下载软件，应用，基本上都能接触到文件压缩。对于文件压缩来讲，有许多种不同的方式，每种方式也有各自的优缺点，这篇文章，就主要介绍以哈夫曼编码的方式来实现文件压缩。

以下是本篇文章正文内容，下面案例可供参考，如有问题，还请大佬及时指正，交流学习！！！

一、什么是文件压缩？

文件压缩是指在不丢失有用信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率，或按照一定的算法对文件中数据进行重新组织，减少数据的冗余和存储的空间的一种技术方法。

二、为什么需要文件压缩

1. 紧缩数据存储容量，减少存储空间
2. 可以提高数据传输的速度，减少带宽占用量，提高通讯效率
3. 对数据的一种加密保护，增强数据在传输过程中的安全性

三、怎样实现文件压缩

实现压缩的方式，大体上主要分为两类：有损压缩和无损压缩。
无损压缩：简单来将，就是压缩之后的文件经过还原后与源文件相同。常用于对文件的压缩
有损压缩：压缩过程中损失一定的信息，常用于图片或视频的压缩，有损压缩的压缩比率要比无损压缩高。
而对于文件的压缩，常用的方式有：
①专有名词采用的固定短语
②缩短文件中重复的数据
③给文件中每个字节找一个更短的编码
其中，给文件中每个字节找一个更短的编码这种方式较为常用。因为，文件中的数据在磁盘中都是以字节的方式来进行存储的，1字节=8比特位，可以给每个字节找一个更短的比特位编码来表示，这样就可以达到压缩(减小文件所占空间)的目的。
下图是使用等长的二进制编码来对源文件进行改写：

使用等长的编码来对文件进程改写，不一定能达到最好的压缩率。
但使用不等长的编码来改写文件的话，压缩率往往会更好，这种方式是使用出现频率高的字符采用更短的编码进行表示。
下图是使用了不等长编码方法：

四、创建哈夫曼树

基于哈夫曼编码的文件压缩方式就是使用不等长的编码来对原文件进行改写的。使用Huffman编码来进行文件压缩要经过四个步骤：
1.获取原文件中每个字节出现的次数
2.根据字节出现的频次信息构建Huffman树
3.获取Huffman编码
4.使用Huffman编码来改写文件

1.哈夫曼编码的方式

前面介绍用不等长编码的方式来对文件进行改写，但这些编码是怎么来的呢？为什么A：100 ，B：101， C：11， D：0
这中编码方式是通过哈夫曼树来进行编排的：

2.构建一棵哈夫曼树

知道了哈夫曼编码的方式之后，到底该如何构建一棵哈夫曼树呢？
从二叉树的根结点到二叉树中所有叶结点的路径长度与相应权值的乘积之和为该二叉树的带权路径长度WPL，将带权路径最小的二叉树称为Huffman树。
下图展示了哈夫曼树的构建方法：

关于具体哈夫曼树的创建代码，请参考：
(https://gitee.com/zhang-yucheng329/c-file-compression)

五、压缩

压缩过程需要要经过四个步骤：

1.获取原文件中每个字节出现的次数

对于获取文件中每个字节出现的次数，采用一个含有256个结构体类型的数组来保存较为方便。因为文件在磁盘中都是以字节的方式来进行存储的，可以用每个字符对应的ASCII码值来作为数组的下标，只需遍历文件中的每一个字节，遇到对应ASCII码的元素对结构体中的count进行++即可。
如下图，数组的下标与字符的ASCII码值一一对应：

2.根据字节出现的频次信息构建Huffman树

在构建哈夫曼树时，直接调用之前写过的创建树的方式即可，但需要注意一点：
哈夫曼树每个节点类型为结构体类型，因此在定义结构体的地方，需要对运算符(+,>,!=,==)进行重载，让编译器知道count之间的比较方式。
下图是创建Huffman树时需要注意的点：

3.获取Huffman编码

我们现在已经有了根据频次信息创建的Huffman树，现在只需要遍历Huffman树来获取编码即可。对于编码的获取方式，可以从根节点遍历到叶子节点来获取，也可以从叶子节点向上找到根节点获取。
这里采用第二种方式来获取编码，需要给节点中增加双亲的指针域，让Huffman树的表示方法为孩子双亲表示法。通过这种方式获取的编码最后需要进行逆置才是最终结果，下图是获取编码后的结果，与期望的编码相同：

4.使用Huffman编码来改写文件(压缩)

前三个步骤进行完之后，只需改写文件即可。还是需要循环读取文件内容，采取位操作按位或的方式将Huffman编码放置到比特位当中。
步骤：1.定义ch = 0，先让ch左移一位，再判断Huffman编码的每个比特位是否为1，为1则让ch与Huffman编码为1比特位进行或操作，这样就能将文件按照编码的方式改写。
最终改写结果：

关于具体文件压缩的代码，请参考：
(https://gitee.com/zhang-yucheng329/c-file-compression/tree/master/Compress)

六、解压缩

1.获取解压缩用到的信息

解压缩过程与压缩过程相反，需要将压缩文件还原成原文件。但使用解压缩进行还原是需要条件的，不能凭空还原，需要根据原文件信息进行。
因此，在压缩过程中就需要将解压缩需要的信息重新保存一下。解压缩还原有很多种方法，但每种方法的还原效率不一样，这里选择用哈夫曼树的方式来进行还原：通过原文件字节出现的频次信息，还原出一棵哈夫曼树，再从根节点遍历，读取压缩数据，当读到0往左子树走，读到1往右子树走，直到走到叶子节点的位置即还原了原数据，再回到根节点循环遍历压缩数据。
在解压缩过程中用到的信息：
1.原文件后缀
2.统计频次信息的总行数(方便对数据进行操作)
3.获取原文件字节出现的频次信息
4.压缩数据
往文件中写入信息后：

2.恢复哈夫曼树

有了这些信息，就可以对哈夫曼树进行恢复，继续进行解压缩的过程了,恢复哈夫曼树的过程相对简单，基于之前写过的构建哈夫曼树的方法，只需对文件中压缩信息做相对应的处理

3.恢复原文件(解压缩)

解压缩过程就是：根据压缩数据来遍历恢复的哈夫曼树，压缩数据为1就往右子树走，为0就往左子树走，知道走到叶子节点。通过以上所有步骤就能够完成压缩与解压缩的所有过程了。
这里还有一个小问题，压缩方法不能处理文件中的汉字，因为汉字是采用UTF-8编码进行编排的，它的编码不在ASCII码表中。因此需要将所有的char类型改变为unsigned char类型！！！
下面为原文件与解压缩之后的结果：

关于具体解压缩的代码(最终代码)，请参考：
(https://gitee.com/zhang-yucheng329/c-file-compression)

总结

以上就是今天要讲的内容，本文简单介绍了基于哈夫曼编码的文件压缩方法，我收获很多。在写代码途中，不免遇到很多bug调试半天还解决不了，但最终还是解决了出来，这也是写代码必经的一个过程。
以下是我总结完成过程中注意的一些问题：
①创建哈夫曼树时，使用优先级队列来保存字符出现的频次信息时，优先级队列的比较方式需要自己进行给出，使用仿函数的方法让比较方式为每个节点中的权值
②在使用结构体来创建哈夫曼树时，需要对+，>，==，!=，进行重载，重载的目的:让编译器知道权值中的count之间的比较方式
③在构建哈夫曼树时，发现其他节点构建正确，但是值域为1的节点不是叶子节点，是因为数组中还存放着许多字符出现次数为0的节点，需要进行过滤，设置第三个参数invalid来过滤权值为0的节点
④再次读取文件时，需要将文件指针的位置重置到文件头部，使用fseek函数或者rewind函数
⑤在解压缩时，不一定是8个比特位都需要解压缩，因此需要增加判定条件，只要解压缩后的字节数与原文件相等就停止解压缩
⑥压缩和解压缩代码写完后，需要讲char类型改成unsigned char类型，因为原文件可能出现汉字，汉字对应的是utf-8编码，不在ASCII码表中
⑦在测试多行数据压缩时，又出现了问题，原因是当读取到\n换行使，并没有将换行所在的数据GetLine，因此解压缩时数据少了一行。
⑧在进行大量数据测试时出现问题，发现解压缩一部分内容就停止了，部分数据丢失，但已经解压缩的部分内容与原文件一样。原因是解压缩文件是二进制文件(即压缩结果是二进制数字)，二进制文件中可能会
出现-1(FF)，当为-1时就默认读到了文件末尾就结束解压缩过程了。
改进方法是：
将所有打开文件(fopen)中文件的读写方式由"r",“w"改为二进制读写式"rb”“wb”
⑨经过测试，发现对不同的文件(文本文件，二进制文件)，图片，视频都能够进行压缩，但哈夫曼编码的文件压缩对不同种类的压缩率是不同的。
对于txt/c/cpp类后缀的文本文件，压缩率较高在30%~50%
对于png/jpg类后缀的图片，压缩率一般在70%~90%
对于exe类后缀的可执行文件，压缩率较低在80%~90%
⑩在对文件进行多次压缩时，压缩结果的大小不是每次会减少，有一个限度。
同时，哈夫曼编码的压缩方法也是可能会出现压缩结果变大的可能性。当文件中字节的种类偏多，并且字节出现的次数比较平均的情况下，压缩效率就会变差，因为统计字节出现的频次信息时，各个字节出现的次数差不多，构建出来的哈夫曼树就接近平衡二叉树，效果就会不理想。
当然，也会出现压缩后文件变大的情况：当哈夫曼编码的平均长度大于8字节时，压缩文件就会变大

原理就是统计带压缩文件字符频率，构建哈夫曼树，然后求哈夫曼编码，将字符频率(解压的时候通过字符频率建树)和哈夫曼编码写入文件，完成压缩。

压缩代码：

//获取一个文件的每个字符的频率
void get_frequency(string filename, int frequency[256])
{
    ifstream fin(filename);
    
    if (!fin.is_open())
    {
        return ;
    }
    
    memset(frequency, 0, sizeof(int) * 256);
    
    while (!fin.eof())
    {
        unsigned char temp = fin.get();
        if (fin.eof())
        {
            break;
        }
        frequency[temp]++;
    }

    fin.close();
}

//哈夫曼树的节点
struct node
{
    unsigned char ch;
    int w;
    node *rch, *lch;
};
//获取一个行自定义属性的节点
node* new_node(unsigned char ch, int w, node* lch = NULL, node* rch = NULL)
{
    node* temp = (node*)malloc(sizeof(node));
    temp->ch = ch;
    temp->w = w;
    temp->rch = rch;
    temp->lch = lch;
    return temp;
}
//优先级队列比较大小的方法
struct cmp
{
    bool operator () (node* x, node* y)
    {
        return x->w > y->w;
    }
};
//建树，返回根节点
node* build_haffman(int frequency[256])
{
    priority_queue<node*, vector<node*>, cmp> q;
    for (int i = 0; i < 256; i++)
    {
        if (frequency[i] != 0)
        {
            node* temp = new_node((unsigned char)i, frequency[i]);
            q.push(temp);
        }
    }
    while (q.size() > 1)
    {
        node* x = q.top();
        q.pop();
        node* y = q.top();
        q.pop();
        
        node* temp = new_node(0, x->w + y->w, x, y);
        q.push(temp);
    }
    return q.top();
}

//后跟遍历销毁树
void destory_haffman(node **root)
{
    if (*root)
    {
        destory_haffman(&(*root)->lch);
        destory_haffman(&(*root)->rch);
        free(*root);
    }
}

//获取字符的哈夫曼编码
void get_haffman_code(node* root, vector<char>& v, string code[256])
{
    if (root)
    {
        if (root->lch == NULL && root->rch == NULL)
        {
            string temp = "";
            for (int i = 0; i < v.size(); i++)
            {
                temp += v[i];
            }
            code[root->ch] = temp;
        }
        v.push_back('0');
        get_haffman_code(root->lch, v, code);
        v.pop_back();
        v.push_back('1');
        get_haffman_code(root->rch, v, code);
        v.pop_back();
    }
}

//将8位01码表示为一个unsigned char
unsigned char create_uchar(string haff_code, int index)
{
    unsigned char ch = 0;
    unsigned char flag = 128;
    for (int i = index; i < index + 8; i++)
    {
        ch += flag * (haff_code[i] - '0');
        flag /= 2;
    }
    return ch;
}
//压缩文件的流程
void compress_to_file(string src_file, string dst_file)
{
    ifstream fin(src_file);
    ofstream fout(dst_file, ios::binary);
    
    if (!fin.is_open() || !fout.is_open())
    {
        return;
    }
    
    int frequency[256];
    string code[256];
    vector<char> v;
    get_frequency("/Users/Rubik/Desktop/123.txt", frequency);
    node* root = build_haffman(frequency);
    get_haffman_code(root, v, code);
    
    string haff_code = "";
    unsigned char ch;
    while (!fin.eof())
    {
        ch = fin.get();
        if (fin.eof()) break;
        haff_code += code[ch];
    }
    int len = (int)haff_code.length();
    cout << len << endl;
    fout.write((const char*)frequency, sizeof(int) * 256);
    fout.write((const char*)&len, sizeof(int));
    
    while (haff_code.length() % 8 != 0)
    {
        haff_code += '0';
    }
    
    for (int i = 0; i < haff_code.length(); i += 8)
    {
        unsigned char temp = create_uchar(haff_code, i);
        fout.write((const char*)&temp, sizeof(char));
    }
    
    fout.close();
    fin.close();
    destory_haffman(&root);
}

解压部分比较简单，获取字符频率，建树，获取unsigned char，遍历树，遇到叶子节点就输出到解压文件

//通过一个unsigned char遍历haffman树，存到s[]里，s长度为slen， cnt为已走长度，len为有效长度
node* get_res(node* root, node* pos, unsigned char temp, char* s, int &slen, int &cnt, int len)
{
    slen = 0;
    for (int i = 128; i > 0 && cnt < len; i >>= 1)
    {
        if (i & temp)
        {
            pos = pos->rch;
        }
        else
        {
            pos = pos->lch;
        }
        cnt++;
        if (pos->lch == pos->rch && pos->lch == NULL)
        {
            s[slen++] = pos->ch;
            pos = root;
        }
    }
    return pos;
}

void decompress_to_file(string src_file, string dst_file)
{
    ifstream fin(src_file);
    ofstream fout(dst_file, ios::binary);
    
    int frequency[256];
    fin.read((char*)frequency, sizeof(int) * 256);
    
    node* root = build_haffman(frequency);
    
    vector<char> v;
    string code[256];
    get_haffman_code(root, v, code);
    
    for (int i = 0; i < 256; i++)
    {
        if (code[i].length() > 0)
        {
            cout << code[i] << endl;
        }
    }
    
    int len;
    fin.read((char*)&len, sizeof(int));
    
    unsigned char temp;
    node *pos = root;
    char s[8];
    int slen, cnt = 0;
    while (!fin.eof())
    {
        fin.read((char*)&temp, sizeof(char));
        pos = get_res(root, pos, temp, s, slen, cnt, len);
        for (int i = 0; i < slen; i++)
        {
            fout << s[i];
        }
    }
    
    destory_haffman(&root);
    
    fin.close();
    fout.close();
}

int main()
{
    compress_to_file("/Users/Rubik/Desktop/123.txt", "/Users/Rubik/Desktop/out.txt");
    decompress_to_file("/Users/Rubik/Desktop/out.txt", "/Users/Rubik/Desktop/456.txt");
    return 0;
}

效果如下