赫夫曼树及赫夫曼编码

1.前言

在1952年美国数学家发明了赫夫曼编码，当时是为了解决远距离通信（主要是电报）的数据传输最优化问题，节约存储和传送的成本。后人为纪念他的成就，就把他在编码中用到的二叉树称为赫夫曼树，别名最优二叉树。他的编码方法称为赫夫曼编码。我们平时所用的压缩和解压缩技术也是基于赫夫曼的研究之上而来。

2.赫夫曼树定义及原理

路径长度：从树中一个结点到另一个结点的分支构成两个节点之间的路径，路径上的分支长度称为路径长度。比如说在下图中的根节点到D结点的路径长度为2.

树的路径长度：树根到每一结点的路径长度之和。比如说下图中树的路径长度为：1+1+24+32=16

带权路径长度：结点的带权路径长度为从该结点到根结点之间的路径长度与结点上权的乘积。比如说D结点的带权路径长度为60.树的带权路径长度为树中所有叶子结点的带权路径长度之和。比如说下图中整棵树的带权路径长度WPL为：220.其中树的带权路径长度（WPL）最小的二叉树称为赫夫曼树。既然要使得树的路径长度最小，那么权值越大的节点理应离根节点越近

示例二叉树.png

知道了赫夫曼树的定义后，那么如果给定一串权值，我们如何构建一颗赫夫曼树呢？构造赫夫曼树的算法描述：
1.根据给定的n个权值{w1,w2,...,wn}构成n棵二叉树（只含一个节点）的集合F= {T1，T2，...,Tn}.,其中每颗二叉树Ti中只有一个带权为Wi的根节点，其左右子树为空。
2.在F中选取两颗根节点的权值最小的树作为左右子树构造一颗新的二叉树，并且新的二叉树的根节点的权值为左右子树根节点上的权值之和。
3.在F中删除这两棵树，将新的到的二叉树加入F中。
4.重复二三，直到F中只剩下一棵树为止，这就是赫夫曼树。

简单实现根据权值构建赫夫曼树案例如下：

#pragma once
#ifndef _HUFFMAN_H
#define _HUFFMAN_H

//结点结构
typedef struct
{
    size_t weight;                  //权值
    size_t parent, rchild, lchild;  //某个结点的双亲，左孩子，右孩子在数组中的下标
}HuffManTree;

//创建赫夫曼树
void  createHuffManTree(HuffManTree ** ht,size_t weiNum);
//在含有权值的集合中挑选权值最小的两个
void select(HuffManTree * ht, int end, size_t* s1, size_t* s2);
//遍历数组
void traverseHuff(HuffManTree * ht, size_t weiNum);
#endif

#include "HuffmanTree.h"
#include <cstdlib>
#include <cassert>
#include <cstdio>

void  createHuffManTree(HuffManTree** ht, size_t weiNum)
{
    //如果权值为 <= 1则创建赫夫曼树是无意义的
    if (weiNum <= 1)
    {
        return;
    }
    //权值数即为叶子结点的数量，因此可得整颗赫夫曼树的结点的数量
    //allNum为树的总结点数
    size_t allNum = 2 * weiNum - 1;
    //为了方便，数组下标为0的位置不存储结点，故多分配一块内存
    *ht = (HuffManTree *)malloc(sizeof(HuffManTree) * (allNum + 1));
    assert(*ht != nullptr);
    //初始化所有结点
    for (size_t i = 1 ; i <= allNum  ; i ++)
    {
        (*ht)[i].lchild = (*ht)[i].rchild = (*ht)[i].parent = (*ht)[i].weight = 0;
    }
    //输入weiNum个叶子结点的权值,前weiNum个内存块存储叶子节点
    for (size_t i = 1 ; i <= weiNum ; i ++)
    {
        printf("请输入第%d个叶子节点的权值:",i);
        scanf("%d",&((*ht)[i].weight));
    }

    for (size_t i = weiNum + 1 ; i <= allNum ; i ++)
    {
        //s1,s2为权值最小的两个结点在数组中的下标
        size_t s1, s2;  
        select(*ht,i - 1,&s1,&s2);
        (*ht)[s1].parent = (*ht)[s2].parent = i;
        (*ht)[i].lchild = s1;
        (*ht)[i].rchild = s2;
        (*ht)[i].weight = (*ht)[s1].weight + (*ht)[s2].weight;

    }
}

//ht数组中存放的哈夫曼树，end表示ht数组中存放结点的最终位置，s1和s2传递的是ht数组中权重值最小的两个结点在数组中的位置
void select(HuffManTree * ht, int end, size_t * s1, size_t* s2)
{
    int min1, min2;
    //遍历数组初始下标为 1
    int i = 1;
    //找到第一个还没构建树的结点
    while (ht[i].parent != 0 && i <= end)
    {
        i++;
    }
    min1 = ht[i].weight;
    *s1 = i;
    i++;
    //找到第二个还没构建树的结点
    while (ht[i].parent != 0 && i <= end)
    {
        i++;
    }
    //对找到的两个结点比较大小，min2为大的，min1为小的
    //第一种情况找到的第二个还没建树的结点的权值比第一个还小
    if (ht[i].weight < min1)
    {
        min2 = min1;
        *s2 = *s1;
        min1 = ht[i].weight;
        *s1 = i;
    }
    else
    {
        min2 = ht[i].weight;
        *s2 = i;
    }
    //两个结点和后续的所有未构建成树的结点做比较
    for (int j = i + 1; j <= end; j++)
    {
        //如果有父结点，直接跳过，进行下一个
        if (ht[j].parent != 0)
        {
            continue;
        }
        //如果比最小的还小，将min2=min1，min1赋值新的结点的下标
        if (ht[j].weight < min1)
        {
            min2 = min1;
            min1 = ht[j].weight;
            *s2 = *s1;
            *s1 = j;
        }
        //如果介于两者之间，min2赋值为新的结点的位置下标
        else if (ht[j].weight >= min1 && ht[j].weight < min2)
        {
            min2 = ht[j].weight;
            *s2 = j;
        }
    }
}

//打印各个结点的权值
void traverseHuff(HuffManTree * ht, size_t weiNum)
{
    for (size_t i = 1 ; i <= 2 * weiNum - 1 ; i++)
    {
        printf("%d\n",ht[i].weight);
    }
}

测试：

#include <iostream>
#include "HuffManTree.h"

int main()
{
    HuffManTree* node = nullptr;
    //创建一颗赫夫曼树
    createHuffManTree(&node,5);
    //打印各个结点的权值
    traverseHuff(node,5);
    return 0;
}

输入权值集合{5，15，10，30，40}结果可得到下图所示的最优二叉树：

结果.png

因为赫夫曼树中给定叶子节点数是可以知道赫夫曼树节点总数的，所以选择分配一段连续的空间来存储赫夫曼树。

3.赫夫曼编码

赫夫曼编码：假设有一段需要编码的字符集{c1,c2,c3,...,cn},求得各个字符在电报中出现的频率集合为{w1,w2,w3,...,wn},以c1,c2,c3,...,cn作为叶子节点，以w1,w2,w3,...,wn作为相应叶子节点的权值来构造一颗赫夫曼树。并且规定好赫夫曼树的左分支代表0，右分支代表1（即一个结点的左孩子为0，右孩子为1），则一个字符的编码就是从根节点到叶子节点所经过的路径分支组成的0和1的序列。这就是赫夫曼编码。比如说A字符的编码为01.这样就可以得到比原来编码更短的二进制串，压缩了数据，节约了存储成本。

通俗来说，就是给你一段字符，按照何种方式或者规则编码可以使得编码后所得的二进制串最短呢？赫夫曼就提出了赫夫曼编码规则。

赫夫曼树.png