哈夫曼树的编码与解码

我又要开更一些比较低端的玩意了，作为自己学习的笔记

今天来说一下如何建立一棵哈夫曼树以及如何利用哈夫曼树对字符串进行编码和解码。

在这之前首先应该了解一下什么是哈夫曼树（最优二叉树）：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

带权路径长度：为所有叶子结点的带权路径长度之和。这么说或许还是有点抽象，带权路径长度简单可以这么理解：

一条路的路程长度为2，一条路的路程长度为6，那么从根节点到第一个叶子结点的带权路径长度为2+6=8，以此类推其他的带权路径长度也可以知道

哈夫曼树被称为最优二叉树，究其原因就是带权路径长度最短。所以它在一些编码方面使用的比较广泛。

在使用哈夫曼树进行编码解码的时候我们需要把这个问题拆解成几个小问题来处理

1.构造哈夫曼编码表

2.建立哈夫曼树

3.利用哈夫曼树进行编码

4.利用哈夫曼树进行解码

首先来解决第一个问题构造哈夫曼编码表：

首先是一个接受到一个字符串要计算出字符串中个元素的权值，并保存起来。这里我选用了一种比较弱智的方法来解决，我这里使用的是直接由指针带回结果

void searchElem(char *str,char *result){
    int nowStation = 0,i = 0;
    for(;i < strlen(str);i++){
        int flag = 0;
        for(int j = 0;j < strlen(result);j++){
            if(str[i] == result[j]){
                flag = 1;
                break;
            }
        }
        if(flag == 0){
            result[nowStation++] = str[i];
        }
    }

这样就得到了哈夫曼编码表的各个元素的权值部分，接下来就是构建哈夫曼编码表，这个就简单多了（虽然我认为我写的依旧很麻烦），我这里使用的是直接由指针带回结果

void setHuffmanTable(char *str,char *result){
    pointer = (huffmanTC)calloc(strlen(result),sizeof(HTC));
    for(int i = 0;i < strlen(result);i++)
        pointer[i].character = result[i];
    for(int i = 0;i < strlen(str);i++){
        for(int j = 0;j < strlen(result);j++){
            if(str[i] == pointer[j].character){
                pointer[j].num++;
                break;
            }
        }
    }
}

现在哈夫曼编码表已经构造好了，现在要来建立哈夫曼树，因为哈夫曼树是最有二叉树，所以我们按照带权路径最小的规则，首先应该从刚才的编码表中找到最小的，然后将两个最小的叶子结点组合成一棵树，给父节点计算新的权值，然后把父节点作为一个新元素加入查找表中。然后继续从查找表中找到两个最小的元素，进行上面的动作

void makeTree(huffmanTree p1,huffmanTree p2,huffmanTree *result,int nowStation){
    (*result) = (huffmanTree)calloc(1,sizeof(HTNode));
    (*result)->weigth = p2->weigth + p1->weigth;
    p2->parent = p1->parent = (*result);
    (*result)->lchild = p1;
    (*result)->rchild = p2;
    pointer[nowStation].num = (*result)->weigth;
    pointer[nowStation].flag = 0;
    pointer[nowStation].character = (*result)->character;
    pointer[nowStation].pointer = (*result);
}

huffmanTree huffmanEncode(int allCount){
    huffmanTree p1,p2,result;
    int flagL = 1,flagR = 1,length = allCount - 1;
    while(length){
        int temp;
        temp = findMinInTable(allCount);
        if(!pointer[temp].pointer){
            p1 = (huffmanTree)calloc(1,sizeof(HTNode));
            p1->character = pointer[temp].character;
            p1->weigth = pointer[temp].num;
        }else{
            p1 = pointer[temp].pointer;
        }
        temp = findMinInTable(allCount);
        if(!pointer[temp].pointer){
            p2 = (huffmanTree)calloc(1,sizeof(HTNode));
            p2->character = pointer[temp].character;
            p2->weigth = pointer[temp].num;
        }else{
            p2 = pointer[temp].pointer;
        }
        makeTree(p1,p2,&result,temp);
        length--;
    }
    return result;
}

这里对于如何将result带回查找表，如果只是将权值带回，那么就会把makeTree()生成的树弄丢，因此在原数组上加入保存指针指向的地址

既然编码这个问题解决了，解码就很好解决了，默认左子树的索引为0，右子树为1，搜索到叶子结点停止，然后再重新搜索

void huffmanUncode(char *str,huffmanTree root){
    huffmanTree pointer = root;
    for(int i = 0;i < strlen(str);){
        while(pointer->lchild){
            if(str[i] == '1'){
                pointer = pointer->rchild;
            }
            if(str[i] == '0'){
                pointer = pointer->lchild;
            }
            i++;
        }
        printf("%c",pointer->character);
        pointer = root;
    }
}

这样就解决了哈夫曼树的编码和解码问题，然而我。。。。把有BUG的程序当成作业给交了，心中无限的悔恨