封面画师: あずーる

twitter：@azure_0608_sub

什么是哈夫曼树

哈夫曼树，清华大学严蔚敏版《数据结构》翻译为赫夫曼树，是在带权路径长度最短的树。

翻译成人话，路径长度就是叶子结点（leaf）离根结点（root）的距离，带权路径长度就是给每一条路径赋予特定值，使其相加最短。

常见的哈夫曼树长这样：

以图中的红线路径为例，路径长度为4，R的权为1，所以该结点的带权路径长度为4。

树的带权路径长度（WPL）具有以下计算公式：

w_i为第i个叶子结点所带的权值，l_i是该叶子结点到根结点的路径长度。

则该树的WPL为(2 + 2 + 1 + 1 + 1 + 1 + 1 + 1) × 4 + (3 + 2) × 3 + 4 × 2 = 63

哈夫曼树有什么实际应用

实际应用是算法的归宿，在学习哈夫曼树之前也要了解哈夫曼编码的应用场景。

比如，在计算机显示英语字符的编码方法中，常见的有ASCII码，但是ASCII码编码一个英文字母要用到1byte的内存，在少量文字的时候不会存在大量问题，如果是要存储大量文字，在没有进行压缩的情况下，势必会造成空间的浪费。

英语中26个字母各个字母在文本材料中出现的频率是不一样的，这个理论也常用在密码学上，如康奈尔大学数学探索项目（http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html）在统计40000个单词后得到了以下的字母频率表：

可以看出，一部分的字母使用频率极高，但也有一部分字母不常用到，如果都进行一视同仁的等大小编码的话，势必会造成一定的空间浪费。

那么，有没有存在一个能将出现频率高的字母缩短编码，降低存储空间占用，还能保证排他性，不会存在解码错误的算法呢。

当然是有了。

"this is an example of a huffman tree"，这句话如果用ASCII码编码，需要36 × 8 = 288 bit，但如果以频率出现高低不同进行变长编码，则可以降到135 bit，这就是哈夫曼编码的优势之处。

因此，哈夫曼编码常用与通信和储存领域，以优化传输所需的网络流量和降低储存空间。

哈夫曼树的构造

某百科是这么解释的

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

通俗的话来讲，就是每一步都选最小的两个结点合成一个二叉树，并将这个二叉树当作一个新的结点， 再选最小的两个 结点合成一个二叉树，直到最后只有一个大的二叉树，注意，一个节点下的左右子树的位置并不影响最终结果，所以哈夫曼树并不唯一。

哈夫曼树具有以下特点：

1. 每个初始结点都会成为叶子结点，并且权值越小的结点离根结点越远
2. 构造过程中会新产生n - 1个结点（双分支结点），因此哈夫曼树共有2n - 1个结点（n + n - 1）
3. 因为每次构造都会选择2棵树作为新结点的子树，所以哈夫曼树只有度为0或2的结点，不存在度为1的结点（即要么是叶子结点，要么这个结点必有左右子树）

以下是清华大学出版社 邓俊辉《数据结构（C++语言版）》 中权值为{623, 99, 239, 290, 906, 224}的哈夫曼树构造

• (a) 选择最小的99和224合成一个树，将该树看成323的新结点
• (b) 选择最小的239和290合成一个树，将该树看成529的新结点
• (c) 选择最小的323和529合成一个树，将该树看成852的新节点
• (d) 选择最小的623和852合成一个树，将该树看成1475的新节点
• (e) 选择1475和906合成一个树，完成哈夫曼树的构造

哈夫曼树的代码实现

C语言

#include<stdio.h>
#include<stdlib.h>
#define MAXVALUE 32767

typedef struct { //哈夫曼树结构体
    int weight;                       //输入权值
    int parent,lchild,rchild;        //双亲节点，左孩子，右孩子
}HNodeType;
typedef struct{ //哈夫曼编码结构体
    int bit[8];     //存放当前结点的哈夫曼编码
    int start;      //bit[start]-bit[8]存放哈夫曼编码
}HCodeType;
HNodeType HuffNode[8];  //定义全局变量数组HuffNode存放哈夫曼树
HCodeType HuffCode[8];  //定义全局变量数组HuffCode存放哈夫曼编码
int n;       //定义全局变量n表示叶子结点个数

void CreateHuffTree(){//构造哈夫曼树
    int i,j,a,b,x1,x2;
    scanf("%d",&n);        //输入叶子节点个数
    for(i=1;i<2*n;i++) {
        //HuffNode 初始化
        HuffNode[i].weight=0; //初始化权重为0
        HuffNode[i].parent=-1; //初始化父节点
        HuffNode[i].lchild=-1; //初始化左孩子结点
        HuffNode[i].rchild=-1; //初始化右孩子结点
    }
    printf("输入%d个节点的权值\n",n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",& HuffNode[i].weight);//输入N个叶子节点的权值
    }
    for(i=1;i<n;i++){
        //构造哈夫曼树 
        a=MAXVALUE;
        b=MAXVALUE;
        x1=0;
        x2=0;
        for(j=1;j<n+i;j++){
            //选取最小和次小两个权值
            if(HuffNode[j].parent==-1&&HuffNode[j].weight<a){
                //如果该节点没有父节点，并且权值小于a
                b=a;
                x2=x1;
                a=HuffNode[j].weight;
                x1=j;
            }
            else if(HuffNode[j].parent==-1&&HuffNode[j].weight<b)
            {
                b=HuffNode[j].weight;
                x2=j;
            }
        }
        HuffNode[x1].parent=n+i;
        HuffNode[x2].parent=n+i;
        HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
        HuffNode[n+i].lchild=x1; //设置左孩子
        HuffNode[n+i].rchild=x2; //设置右孩子
    }
}

void PrintHuffTree() {
    //输出哈夫曼树
    int i;
    printf("\n哈夫曼树各项数据如下表所示:\n");
    printf("        结点i weight parent    lchid    rchild\n");
    for(i=1;i<2*n;i++) printf("\t%d\t%d\t%d\t%d\t%d\n",i,HuffNode[i].weight,HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild);
    printf("\n");
}

int main() {
    printf("输入叶子节点个数: "); 
    CreateHuffTree();   //构造哈夫曼树
    PrintHuffTree();   //输出哈夫曼树
    return 0;
}