哈夫曼树编码长度怎么求_哈夫曼树编码长度怎么算

经典算法: 哈夫曼编码
　　1.哈夫曼树的基本概念

　　从A结点到B结点所经过的分支序列叫做从A结点到B结点的路径；从A结点到B结点所经过的分支个数叫做从A结点到B结点的路径长度；从二叉树的根结点到二叉树中所有叶结点的路径长度之和称作该二叉树的路径长度。设二叉树有n个带权值的叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和称作该二叉树的带权路径长度（WPL），即：

　　其中，wi为第i个叶结点的权值，li为从根结点到第i个叶结点的路径长度。

　　（a）WPL = 1×2+3×2+5×2+7×2 = 32

　　（b）WPL = 1×2+3×3+5×3+7×1 = 33

　　（c）WPL = 7×3+5×3+3×2+1×1 = 43

　　（d）WPL = 1×3+3×3+5×2+7×1 = 29

　　具有最小带权路径长度的二叉树称作哈夫曼（Huffman）树（或称最优二叉树）。图（d）的二叉树是一棵哈夫曼树。

　　定义：由给定的n个叶结点权值可以构造很多棵形态不同的二叉树，WPL值最小的二叉树称为哈夫曼树。

　　要使一棵二叉树的带权路径长度WPL值最小，必须使权值越大的叶结点越靠近根结点。哈夫曼树构造算法为：

　　（1）由给定的n个权值{w1,w2,…,wn}构造n棵只有根结点的二叉树，从而得到一个二叉树森林F={T1,T2,…,Tn}。

　　（2）在二叉树森林F中选取根结点的权值最小和次小的两棵二叉树作为新的二叉树的左右子树构造新的二叉树，新的二叉树的根结点权值为左右子树根结点权值之和。

　　（3）在二叉树森林F中删除作为新二叉树左右子树的两棵二叉树，将新二叉树加入到二叉树森林F中。

　　（4）重复步骤（2）和（3），当二叉树森林F中只剩下一棵二叉树时，这棵二叉树就是所构造的哈夫曼树。

　　2.哈夫曼编码问题

　　将传送的文字转换为二进制字符0和1组成的二进制串的过程为编码。

　　例：假设要传送的电文为ABACCDA，电文中只有A,B,C,D四种字符，若这四个字符采用表(a)所示的编码方案，则电文的代码为00 01 00 10 10 11 00，代码总长度为14。若这四个字符采用表(b)所示的编码方案，则电文的代码为0 110 0 10 10 111 0，代码总长度为13。

　　哈夫曼树可用于构造代码总长度最短的编码方案。具体构造方法如下：设需要编码的字符集合为{d1,d2,…,dn}，各个字符在电文中出现的次数集合为{w1,w2,…,wn}，以d1,d2,…,dn作为叶结点，以w1,w2,…,wn作为各叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。代码总长度最短的不等长编码称之为哈夫曼编码。

　　不等长编码不允许存在前缀码。前缀码的一个例子如：A为01，B为010。如编码存在前缀码，则译码会出现二义性。

　　3.哈夫曼编码的实现

　　一、哈夫曼编码的数据结构设计

　　为了在构造哈夫曼树时能方便的实现从双亲结点到左右孩子结点的操作，在进行哈夫曼编码时能方便的实现从孩子结点到双亲结点的操作。设计哈夫曼树的结点存储结构为双亲孩子存储结构。采用仿真指针实现，每个结点的数据结构设计为：

　　从哈夫曼树求叶结点的哈夫曼编码实际上是从叶结点到根结点路径分支的逐个遍历，每经过一个分支就得到一位哈夫曼编码值。存放哈夫曼编码的数据元素结构为：

　　二、哈夫曼编码的算法实现

　　typedef struct //哈夫曼树的结点结构

　　{        int weight;                //权值

　　int flag;  //标记

　　int parent;                //双亲结点下标

　　int leftChild;  //左孩子下标

　　int rightChild;  //右孩子下标

　　} HaffNode;

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

　　{        int bit[MaxN];  //数组

　　int start;               //编码的起始下标

　　int weight;               //字符的权值

　　} Code;

　　哈夫曼树构造算法如下：

　　void Haffman(int weight[], int n, HaffNode haffTree[])

　　//建立叶结点个数为n权值为weight的哈夫曼树haffTree

　　{        int j, m1, m2, x1, x2;

　　//哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-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].parent = -1;

　　haffTree[i].flag   = 0;

　　haffTree[i].leftChild = -1;

　　haffTree[i].rightChild = -1;

　　}

　　//构造哈夫曼树haffTree的n-1个非叶结点

　　for(i = 0;  i < n-1;  i++)

　　{        m1 = m2 = MaxValue;         x1 = x2 = 0;

　　for(j = 0;   j < n+i;  j++)

　　{        if(haffTree[j].weight < m1 && haffTree[j].flag == 0)

　　{        m2 = m1;

　　x2 = x1;

　　m1 = haffTree[j].weight;

　　x1 = j;

　　}

　　else if(haffTree[j].weight < m2 && haffTree[j].flag == 0)

　　{

　　m2 = haffTree[j].weight;

　　x2 = j;

　　}

　　}

　　//将找出的两棵权值最小的子树合并为一棵子树

　　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;

　　}

　　}

　　哈夫曼编码算法如下：

　　void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])

　　{

　　Code *cd = (Code *)malloc(sizeof(Code));

　　int i, j, child, parent;

　　//求n个叶结点的哈夫曼编码

　　for(i = 0; i < n; i++)

　　{

　　cd->start = n-1;

　　cd->weight = haffTree[i].weight;

　　child = i;

　　parent = haffTree[child].parent;

　　//由叶结点向上直到根结点

　　while(parent != -1)

　　{

　　if(haffTree[parent].leftChild == child)

　　cd->bit[cd->start] = 0;

　　else                     cd->bit[cd->start] = 1;

　　cd->start–;

　　child = parent;

　　parent = haffTree[child].parent;

　　}

　　for(j = cd->start+1; j < n; j++)

　　haffCode[i].bit[j] = cd->bit[j];

　　haffCode[i].start  = cd->start + 1;

　　haffCode[i].weight = cd->weight;

　　}

　　}

　　最后是测试用例

　　设有字符集{A, B, C, D}，各字符在电文中出现的次数集为{1, 3, 5, 7}，设计各字符的哈夫曼编码。

　　#include <stdio.h>

　　#include <stdlib.h>

　　#define MaxValue 10000

　　#define MaxBit 4

　　#define MaxN 100

　　void main(void)

　　{        int i, j, n = 4;

　　int weight[] = {1,3,5,7};

　　HaffNode *myHaffTree = (HaffNode *)malloc(sizeof(HaffNode)*(2*n-1));

　　Code *myHaffCode = (Code *)malloc(sizeof(Code)*n);

　　if(n > MaxN)

　　{        printf("给出的n越界，修改MaxN值!

　　");

　　exit(0);

　　}

　　Haffman(weight, n, myHaffTree);

　　HaffmanCode(myHaffTree, n, myHaffCode);

　　//输出每个叶结点的哈夫曼编码

　　for(i = 0; i < n; i++)

　　{        printf("Weight = %d   Code = ", myHaffCode[i].weight);

　　for(j = myHaffCode[i].start; j < n; j++)

　　printf("%d", myHaffCode[i].bit[j]);

　　printf("

　　");

　　}

　　}