定义及原理

定义

1.1 路径长度：从树的一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称为路径长度。

image.png
上图中，二叉树a中，根结点到结点D的路径长度为4，二叉树b中，根结点到结点D的路径长度为2。
1.2 树的路径长度：从树根到每一个结点的路径长度之和。
二叉树a的路径长度为1+1+2+2+3+3+4+4=20；
二叉树b的路径长度为1+1+2+2+2+2+3+3=16；
1.3 结点的带权路径长度：从该结点到根结点之间的路径长度与结点上权的乘积。
1.4 树的带权路径长度：所有叶子结点的带权路径长度之和。
1.5 哈夫曼树：带权路径长度WPL最小的二叉树，也称为最优二叉树。
二叉树a的WPL=51+152+403+304+104=315
二叉树b的WPL=53+153+402+302+102=220

原理

前面已经讲过了如何计算哈夫曼树的WPL，那如何才能构建一棵哈夫曼树呢？且上图中的二叉树b是不是最优二叉树呢？接下来我们就来讲一下哈夫曼树是如何构造出来的。我们仍然选择上图作为示例。
1、先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即：A5、E10、B15、D30、C40。
2、取头两个最小权值的结点（A5、E10）作为一个新的结点N₁，且A5、E10分别为N₁的左右孩子。按照相对较小的为左孩子，另一个为右孩子的原则，则A为N₁的左孩子，E为N₁的右孩子，新结点N₁的权值为两个叶子权值之和，即N₁=5+10=15。

image.png
3、将N₁替换A与E，插入有序序列中，保持从小到大的排列，即N₁15、B15、D30、C40。
4、重复步骤2，将N₁与B作为一个新结点N₂的两个子结点，N₂的权值为N₂=15+15=30。
image.png
5、将N₂替换N₁与B，插入有序序列中，保持从小到大的排列，即N₂30、D30、C40。
6、重复步骤2，将N₂与D作为一个新结点N₃的两个子结点，N₃的权值为N₃=30+30=60。
image.png
7、将N₃替换N₂与D，插入有序序列中，保持从小到大的排列，即C40、N₃60。
8、重复步骤2，将C与N₃作为一个新结点T的两个子结点，此时T就是根结点，至止完成了哈夫曼树的构造。
image.png
最后得到WPL=401+302+153+104+5*4=205
此时可以看出，WPL比之前树b的WPL还小，显然，此时构造的二叉树才是最优二叉树。

哈夫曼算法总结

1、根据给定的n个权值{W₁, W₂, ..., W_n}构成n棵二叉树的集合F={F₁, F₂, ..., F_n}，其中每棵二叉树T_i中只有一个带权为W_i的根结点，其左右子树均为空。
2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3、在F中删除这两棵树，同时将新得到的二叉树加入F中。
4、重复2和3步骤，直到F只含一棵树为止，这树便是哈夫曼树。

实现

哈夫曼的结点形式

image.png

哈夫曼树的存储表示

//哈夫曼树的结点结构
typedef struct HaffNode {
int weight;        //权值
 int flag;          //标记：是否已经合并到哈夫曼树中
 int parent;      //双亲结点下标
 int leftChild;    //左孩⼦子下标
 int rightChild;  //右孩⼦子下标
 }HaffNode;

存放哈夫曼编码的数据元素结构

typedef struct Code{//存放哈夫曼编码的数据元素结构
    int bit[MaxBit];//数组
    int start;  //编码的起始下标
    int weight;//字符的权值
}Code;

构建哈夫曼树

/*
 根据权重值,构建哈夫曼树;
 {2,4,5,7}
 n = 4;
*/
void Haffman(int weight[],int n,HaffNode *haffTree){
    //1 初始化哈夫曼树，因为叶子结点数为n，则根据二叉树的特性整个哈夫曼树的结点为2*n-1个。且使用顺序存储时通过索引访问结点更方便。
    for(int i = 0; i<2*n-1; i++){
        if(i<n){
            haffTree[i].weight = weight[i];
        }
        else{
            haffTree[i].weight = 0;
        }
        haffTree[i].flag = 0;
        haffTree[i].parent = 0;
        haffTree[i].leftChild = -1;
        haffTree[i].rightChild = -1;
    }
    
    //2 开始按照哈夫曼算法构造最优二叉树
    //由于整个哈夫曼树的结点数为：2*n-1，叶子结点数为：n；则非叶子结点的个数为2*n-1-n=n-1
    for(int i = 0; i<n-1; i++){
        int m1, m2;//用于记录两个最小权重值
        int x1, x2;//用于记录对应于两个最小权重值的结点
        m1=m2=MaxValue;
        for(int j = 0; j <n+i; j++){//每次增加双亲结点后，数组的长度会+1，因此遍历数组时，遍历的长度会增加
            if(haffTree[j].weight<m1 && haffTree[j].flag == 0){//current<m1
                m1=haffTree[j].weight;
                x1=j;
            }
            else if(haffTree[j].weight < m2 && haffTree[j].flag == 0){//current<m2
                m2=haffTree[j].weight;
                x2=j;
            }
        }
        
        /*
         1、找到两个权重最小且未加入到哈夫曼树中的两个结点，x1和x2；将这两个结点作为左右子树构造一个新的结点；
         2、将两个结点的双亲分别置为新结点；
         3、将两个结点的标志改成已经加入到哈夫曼树中，即flag=1；
         4、将新结点的权重设置为两个左右子树的权重之和；
         5、将新结点的左子树设置为较小权重的结点，此处即x1；
         6、将新结点的左子树设置为较大权重的结点，此处即x2；
         */
        haffTree[x1].parent = n+i;
        haffTree[x2].parent = n+i;
        haffTree[x1].flag = 1;
        haffTree[x2].flag = 1;
        haffTree[n+i].weight = haffTree[x1].weight+haffTree[x2].weight;
        haffTree[n+i].leftChild = x1;
        haffTree[n+i].rightChild= x2;
    }
}

哈夫曼编码

/*
 哈夫曼编码
 由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode
 //{2,4,5,7}
 */
void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[]){
    Code* cd = (Code*)malloc(sizeof(Code));
    
    int child;
    int parent;
    for(int i = 0; i<n; i++){
        cd->start = 0;
        cd->weight = haffTree[i].weight;
        child = i;
        parent = haffTree[i].parent;
        
        //哈夫曼编码，即结点的左孩子编码为0，右孩子编码为1
        while(parent != 0){
            if(haffTree[parent].leftChild == child){
                cd->bit[cd->start]=0;
            }
            else{
                cd->bit[cd->start]=1;
            }
            cd->start++;
            child = parent;
            parent = haffTree[child].parent;
        }
        
        int temp = 0;
        //由于存进去的时候是按逆序的，所以需要将顺序颠倒一下
        for(int j = cd->start-1; j>=0; j--){
            temp = cd->start-1-j;
            haffCode[i].bit[temp] = cd->bit[j];
        }
        haffCode[i].weight = cd->weight;
        haffCode[i].start = cd->start;
    }
}

测试

int main(int argc, const char * argv[]) {
    printf("Hello, 哈夫曼编码!\n");
    int i, j, n = 4, m = 0;
    
    //权值
    int weight[] = {2,4,5,7};
    
    //初始化哈夫曼树, 哈夫曼编码
    HaffNode *myHaffTree = malloc(sizeof(HaffNode)*2*n-1);
    Code *myHaffCode = malloc(sizeof(Code)*n);
    
    //当前n > MaxN,表示超界. 无法处理.
    if (n>MaxN)
    {
        printf("定义的n越界，修改MaxN!");
        exit(0);
    }
    
    //1. 构建哈夫曼树
    Haffman(weight, n, myHaffTree);
    //2.根据哈夫曼树得到哈夫曼编码
    HaffmanCode(myHaffTree, n, myHaffCode);
    //3.
    for (i = 0; i<n; i++)
    {
        printf("Weight = %d\n",myHaffCode[i].weight);
        for (j = 0; j<myHaffCode[i].start; j++)
            printf("%d",myHaffCode[i].bit[j]);
        m = m + myHaffCode[i].weight*myHaffCode[i].start;
         printf("\n");
    }
    printf("Huffman's WPS is:%d\n",m);
    return 0;
}
/*结果：
Hello, 哈夫曼编码!
Weight = 2
110
Weight = 4
111
Weight = 5
10
Weight = 7
0
Huffman's WPS is:35
*/