七、二叉树(七)、赫夫曼树&赫夫曼编码

数据结构目录

一、赫夫曼树的定义

下面是一个例子

if (a < 60) {
   printf("不及格");
} else if (a < 70){
   printf("及格");
} else if (a < 90){
   printf("良好");
} else {
   printf("优秀");
}

这段代码的树结构如下

二叉树

如图所示，每个阶段的学生所占比例不同，但我们的二叉树并没有对这方面进行优化，我们将树结构改为如下，效率可能有明显的改善

优化后的二叉树

1.定义

我们将两棵二叉树简化为叶子结点带权的二叉树(树结点间的连线相关的数叫做权)，这就是赫夫曼树

带权二叉树

下面是一些概念

• 结点的路径长度
   从根节点到该结点的路径上的连接数，如上图中左边树中结点C的路径长度为3(有3个连接)

• 树的路径长度
   树中每个叶子结点的路径长度之和，如上图中左边树的路径长度为1+2+3+3=9

• 结点带权路径长度
   结点的路径长度与结点权值的乘积，如上图中左边树中结点C的带权路径长度为3*70=210

• 树的带权路径长度
   WPL(Weighted Path Length)是树中所有叶子结点的带权路径长度之和，如上图中左边树中为1*5+2*15+3*70+3*10=275

WPL的值越小，说明构造出来的二叉树性能越优。

2.赫夫曼树的构造

如上面的所讲，赫夫曼树的构造算法如下：

① 根据给定的n个权值{W1,W2,...,Wn}构成n课二叉树的集合F={T1,T2,...,Tn}，其中每棵二叉树Ti中只有一个带权为Wi的结点，其左右子树为空。
② 在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且将新的二叉树的根节点的权值设置为其左右子树上根节点的权值之和。
③ 在F中删除这两棵树，同时将新得到的二叉树加入F中。
④ 重复②和③步骤，直到F只含一棵树为止，这棵树便是赫夫曼树。

二、赫夫曼编码

赫夫曼编码可以很有效的压缩数据(通常可以节省20%~90%的空间，具体压缩率依赖于数据的特性)

名词解释

• 定长编码：像ASCII编码，长度是一定的
• 变长编码：单个编码的长度不一致，可以根据整体出现频率来调节
• 前缀码：所谓的前缀码，就是没有任何码字是其他码字的前缀

赫夫曼编码最早目的是为了解决当年远距离通信(主要是电报)的数据传送的最优化问题。

我们以网络传输一段文字内容为“BADCADFEED”为例。如果用二进制的数字（0和1）来表示，

数据

真正传输的数据是编码后的“001 000 011 010 000 011 101 100 100 001”。

实际上，如果传输一篇很长的文章，这个二进制串就非常大，同时不同字母的出现频率是不相同的。假设这六个字母的频率为:

出现频率

下图左边为赫夫曼树的构造过程。右边将权值左分支改为0，右分支改为1后的赫夫曼树。

权值左0右1的赫夫曼树

此时，我们对这六个字母用其从树根到叶子所经过路径的0或1来编码，得到下表:

赫夫曼编码

再次编码为“1001 01 00 101 01 00 1000 11 11 00”。

编码压缩比较

对比结果节约了大约17%的数据空间。如果解码呢，必须用到赫夫曼树，即发送方和接收方必须约定好同样的赫夫曼编码规则。

以上面新编码二进制串为例，从树根结点出发，按二进制数表示的路径到达叶子节点，解码出字母。后面的二进制再从树根结点出发，以此循环。1001走到叶子节点B，后面的01走到叶子节点A，以此类推。

三、赫夫曼编码代码实现

算法思路：

1. 创建一个队列queue，分别存储字符的出现次数，这个队列中每个结点的权值是按照从小到大的顺序存储的。
2. 按照赫夫曼树的构造方式，先取出两个权值最小的结点a和b，将它们的权值相加，创建一个新结点，新节点的权值是两个权值最小结点之和，left和right指向a和b，将新节点按照权值从小到大的顺序插入队列中，并在队列中删除a和b，循环第2步，最后队列queue中只剩下一个结点时，这个结点就是赫夫曼树的根节点，也就是说，这个结点指向一个赫夫曼树
3. 我们通过遍历赫夫曼树的结果，为左子树加一个0，右子树加一个1，一直到叶子结点，我们加一个'\0'，这样我们就得到了每个字符的编码，并将结果存入一个表格中
4. 解码的过程，我们拿到编码后，在赫夫曼树上，为0则往左走一步，1往右走一步，这样就找到了叶子，把它的字符写出来

实现代码有点长，我们分为两个文件，分别为Huffman文件和PriorityQueue文件，代码如下所示:

Huffman文件

Huffman.h

#ifndef Huffman_h
#define Huffman_h

#include <stdlib.h>
#include <stdio.h>

//赫夫曼树结点
typedef struct HuffmanNode{
    char symbol;//字符
    struct HuffmanNode *left,*right;//左子树，右子树
}HuffmanNode;

//赫夫曼树
typedef struct HuffmanTree{
    HuffmanNode *root;//根节点
}HuffmanTree;

///编码表结点
typedef struct HuffmanTableNode{
    char symbol;//字符
    char *code;//编码
    struct HuffmanTableNode *next;//指向
}HuffmanTableNode;

///编码表,一个单链表结构
typedef struct HuffmanTable{
    HuffmanTableNode *first;//首个结点
    HuffmanTableNode *last;//最后一个结点
}HuffmanTable;

///创建赫夫曼树
HuffmanTree *buildTree(char *inputString);
///创建编码表
HuffmanTable *buildTable(HuffmanTree *tree);
///进行编码
void encode(HuffmanTable *table,char *stringToEncode,char *stringEncoded);
///进行解码
void decode(HuffmanTree *tree,char *stringToDecode,char *stringDecoded);


#endif /* Huffman_h */

Huffman.c

#include "Huffman.h"
#include "PriorityQueue.h"
#include <string.h>

///创建赫夫曼树
HuffmanTree *buildTree(char *inputString){
    //创建一个含有所有字符的数组，来记录每个字符出现的次数
    int *probability = (int *)malloc(sizeof(int)*256);
    //初始化
    for (int i = 0; i < 256; i++) {
        probability[i] = 0;
    }
    //统计待编码的字符串各个字符出现的次数
    for (int i = 0; inputString[i] != '\0'; i++) {
        //看到有出现，则将这个位置的出现次数加1
        probability[(unsigned char)(inputString[i])]++;
    }
    
    //队列
    PQueue *queue;
    //初始化队列(分配头结点空间与初始化)
    initQueue(&queue);
    
    for (int i = 0; i < 256; i++) {
        //如果这个字符出现过
        if (probability[i] != 0) {
            //初始化一个树结点
            HuffmanNode *node = (HuffmanNode *)malloc(sizeof(HuffmanNode));
            //左右子树置空
            node->left = NULL;
            node->right = NULL;
            //将int转化为ASCII码
            node->symbol = (char)i;
            //插入队列
            addQueue(&queue, node, probability[i]);
        }
    }
    //释放可能性数组
    free(probability);
    
    //队列元素只剩1，则构建完成了赫夫曼树
    while (queue->size > 1) {
        int priority = queue->first->priotity;
        priority += queue->first->next->priotity;
        
        HuffmanNode *left = getQueue(&queue);
        HuffmanNode *right = getQueue(&queue);
        
        //创建新的结点，加入到队列中
        HuffmanNode *newNode = (HuffmanNode *)malloc(sizeof(HuffmanNode));
        newNode->left = left;
        newNode->right = right;
        
        addQueue(&queue, newNode, priority);
    }
    
    //赫夫曼树的根节点就得到了，而队列也没有用了
    HuffmanTree *tree = (HuffmanTree *)malloc(sizeof(HuffmanTree));
    tree->root = getQueue(&queue);
    
    //销毁队列
    destroyQueue(&queue);
    
    return tree;
}

void travalTree(HuffmanNode *treeNode,HuffmanTable **table,int k,char code[256]);
///创建编码表
HuffmanTable *buildTable(HuffmanTree *tree){
    //初始化
    HuffmanTable *table = (HuffmanTable *)malloc(sizeof(HuffmanTable));
    table->first = NULL;
    table->last = NULL;
    
    //编码数组
    char code[256];
    int k = 0;//下标
    travalTree(tree->root, &table, k, code);
    
    return table;
}

void travalTree(HuffmanNode *treeNode,HuffmanTable **table,int k,char code[256]){
    if (treeNode->left == NULL && treeNode->right == NULL) {
        //遍历到了叶子结点
        code[k] = '\0';//添加\0作为终止符
        HuffmanTableNode *node = (HuffmanTableNode *)malloc(sizeof(HuffmanTableNode));
        node->code = (char *)malloc(sizeof(char) * (strlen(code) + 1));
        strcpy(node->code, code);//赋值
        node->symbol = treeNode->symbol;//赋值字符
        node->next = NULL;
        if ((*table)->first == NULL) {
            (*table)->first = node;
            (*table)->last = node;
        } else {
            (*table)->last->next = node;
            (*table)->last = node;
        }
    }
    if (treeNode->left) {
        //遍历到左边，则添加0
        code[k] = '0';
        travalTree(treeNode->left, table, k+1, code);
    }
        
    if (treeNode->right){
        //遍历到右边，则添加1
        code[k] = '1';
        travalTree(treeNode->right, table, k+1, code);
    }
}


HuffmanTableNode *visitHuffmanTableNode(HuffmanTableNode *node,char code);
///进行编码
void encode(HuffmanTable *table,char *stringToEncode,char *stringEncoded){
    char result[512];
    memset(result, 0, sizeof(result));
    //因为得到了这个字符串的赫夫曼编码表，那么我们只需要遍历这个字符串的每个字符即可进行编码
    for (int i = 0; stringToEncode[i] != '\0'; i++) {
        char code = stringToEncode[i];
        //找到对应的编码表结点
        HuffmanTableNode *traversal = visitHuffmanTableNode(table->first, code);
        //拼接到字符串中
        strcat(result, traversal->code);
    }
    strcpy(stringEncoded, result);
}
HuffmanTableNode *visitHuffmanTableNode(HuffmanTableNode *node,char code){
    if (node->symbol == code) {
        return node;
    }
    return visitHuffmanTableNode(node->next, code);
}
///进行解码
void decode(HuffmanTree *tree,char *stringToDecode,char *stringDecoded){
    HuffmanNode *traversal = tree->root;
    
    char result[512];
    memset(result, 0, sizeof(result));
    for (int i = 0; stringToDecode[i] != '\0'; i++) {
        //为0则往左走一步，为1则往右走一步
        if (traversal->left == NULL && traversal->right == NULL) {
            //如果到了叶子结点，则得到一个字符
            strcat(result, &(traversal->symbol));
            traversal = tree->root;
        }
        if (stringToDecode[i] == '0') {
            traversal = traversal->left;
        }
        if (stringToDecode[i] == '1') {
            traversal = traversal->right;
        }
        if (stringToDecode[i] != '0' && stringToDecode[i] != '1') {
            continue;
        }
    }
    
    if (traversal->left == NULL && traversal->right == NULL) {
        strcat(result, &(traversal->symbol));
        traversal = tree->root;
    }
    
    strcpy(stringDecoded, result);
}

PriorityQueue文件

PriorityQueue.h

#ifndef PriorityQueue_h
#define PriorityQueue_h

#include <stdlib.h>
#include <stdio.h>
#include "Huffman.h"


//队列结点
typedef struct PQueueNode{
    HuffmanNode *val;//指向赫夫曼树结点的指针
    unsigned int priotity;//权值
    struct PQueueNode *next;//指向下一个结点
}PQueueNode;

//队列，当队列只剩下1个元素时，则是我们的赫夫曼树
typedef struct PQueue{
    unsigned int size;//队列元素个数
    PQueueNode *first;//指向真正的结点
}PQueue;

///初始化队列
void initQueue(PQueue **queue);
///往队列中添加结点
void addQueue(PQueue **queue,HuffmanNode *val,unsigned int priority);
///获取队列的
HuffmanNode *getQueue(PQueue **queue);
///销毁对垒
void destroyQueue(PQueue **queue);

#endif /* PriorityQueue_h */

PriorityQueue.c

#define MAX_SIZE 256
#include "PriorityQueue.h"

///初始化队列
void initQueue(PQueue **queue){
    *queue = (PQueue *)malloc(sizeof(PQueue));
    (*queue)->first = NULL;
    (*queue)->size = 0;
}
///往队列中添加结点
void addQueue(PQueue **queue,HuffmanNode *val,unsigned int priority){
    //判断是否已满
    if ((*queue)->size == MAX_SIZE) {
        printf("\n queue is full.\n");
        return;
    }
    //生成一个队列结点
    PQueueNode *node = (PQueueNode *)malloc(sizeof(PQueueNode));
    node->next = NULL;
    node->priotity = priority;
    node->val = val;
    
    if ((*queue)->size == 0 || (*queue)->first == NULL) {
        //如果空队列，直接把新来的放在首结点位置
        (*queue)->first = node;
        (*queue)->size = 1;
    } else {
        if (priority <= (*queue)->first->priotity) {
            //如果权值小于等于首结点的权值，那么直接替换掉首节点(由于队列的权值是从小到大)
            node->next = (*queue)->first;
            (*queue)->first = node;
            (*queue)->size++;
        } else {
            //如果权值比首节点大，则需要查找到应该插入的位置，再进行插入
            PQueueNode *iterator = (*queue)->first;
            while (iterator->next) {
                if (priority <= iterator->next->priotity) {
                    //如果比当前结点的下一个结点的权值小，则插入在这个结点之后
                    node->next = iterator->next;
                    iterator->next = node;
                    (*queue)->size++;
                    break;
                }
                iterator = iterator->next;
            }
            
            //找到最后，直接插在最后面
            if (iterator->next == NULL) {
                iterator->next = node;
                (*queue)->size++;
            }
            
        }
    }
    
}
HuffmanNode *getQueue(PQueue **queue){
    HuffmanNode *returnNode = NULL;
    
    if ((*queue)->size > 0) {
        //依次从头取出树结点 并释放取出的队列结点
        PQueueNode *firstNode = (*queue)->first;
        returnNode = firstNode->val;
        (*queue)->first = (*queue)->first->next;
        (*queue)->size--;
        free(firstNode);
    } else {
        printf("\n queue is empty.\n");
    }
    
    return returnNode;
}

void destroyQueue(PQueue **queue){
    free(*queue);
    *queue = NULL;
}

代码验证

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Huffman.h"

int main(int argc, const char * argv[]) {
    char *inputString = "i am student";
    HuffmanTree *tree = buildTree(inputString);
    HuffmanTable *table = buildTable(tree);
    printf("inputString is %s\n",inputString);
    
    //进行编码
    char encodedString[512];
    memset(encodedString, 0, sizeof(encodedString));
    encode(table, inputString, encodedString);
    printf("encodedString is %s\n",encodedString);//结果:0101010011101101111110011100000111100100
    
    //进行解码
    char decodedString[512];
    memset(decodedString, 0, sizeof(decodedString));
    decode(tree, encodedString, decodedString);
    printf("decodedString is %s\n",decodedString);//结果:i am student
    
    return 0;
}

如上所示，我们输入字符串i am student，通过编码再解码，输出的字符串也是i am student，输入其它的字符串结果也是一致的，这说明我们的算法实现是正确的