哈夫曼树平均码长(霍夫曼树)
前言zgdhm树是二叉树的一种特殊形式，也称为最优二叉树，其主要作用是数据压缩和码长优化。
重要的概念路径和路径长度是在一棵树中，可以从一个节点到达下面的儿孙节点之间的路径，被称为路径。 分支的数量被称为路径长度。 设根节点的层数为1，则从根结点到第l层节点的路径长度为L-1。
图2.1图2.1中所示的二叉树从节点a到节点d的路径长度为2，并且从节点a到节点c的路径长度为1。
对节点的权重和加权路径长树中的节点赋予有意义的值后，将该值称为该节点的权重。 节点的加权路径长度是从根结点到该节点的路径长度与该节点的权重的积。
图2.2显示了拥有权利的二叉树
图2.2树的授权路径长度
树的加权路径长度被规定为所有叶节点的加权路径长度之和，被标记为WPL。
图2.2所示二叉树的WPL :
WPL=6 * 2 3 * 2 8 * 2=34；
zgdhm树定义作为n个叶的节点给出的n个权重，制作一棵二叉树。 如果加权路径长度最小，这种二叉树也称为最佳二叉树，也称为zgdhm树(Huffman Tree )。
如图3.1所示，两根二叉树
图3.1
叶的节点为a、b、c、d，对应的权重分别为7、5、2、4。
3.1.a树中的WPL=7 * 2 5 * 2 2 * 2 4 * 2=36
3.1.b树中的WPL=7 * 1 5 * 2 2 * 3 4 * 3=35
用ABCD构成叶节点的二叉树的形态有很多种类，但WPL最小的树只有3.1.b所示的形态。 3.1.b树为zgdhm树。
构建zgdhm树构建zgdhm树主要用于编码，称为zgdhm编码。 这里，考虑使用3.1中的ABCD节点及其对应的权重，构成以下长度的代码。
AACBCAADDBBADDAABB。 从编码规则:根节点出发，左侧标记0，右侧标记1。
使用上述编码规则，如图3.1所示对图3.2进行编码。
图3.2结构流程：
3.1.a所示的二叉树被称为等长码，由于共有4个节点，需要用2位的码来表示，编码结果如下。
对于节点代码A00B01C10D11，启用AACBCAADDBBADDAABB的代码如下所示：
00 00 10 01 10 00 00 11 11 01 01 00 11 11 00 00 01 01
长度是36。
3.1.b结构过程如下。
1 )选择节点权重最小的两个节点制作二叉树，如图3.3所示。
图3.3 )2)中，现在可以看作从T1、a、b构建了zgdhm树，继续步骤1。
选择由b和T1构成的二叉树如图3.4所示。
图3.4 3 )当前，只有T2和a两个节点继续执行步骤1。
选择a和T2构成二叉树的话如图3.5所示。
图3.5经过上述步骤，可以制作一棵zgdhm树。 通过观察发现，zgdhm树权重越大的节点越接近根节点。
图3.5zgdhm树编码结果：
节点代码A0B10C110D111对应于AACBCAADDBBADDAABB，编码如下：
0 0 110 10 110 0 0 111 111 10 10 0 111 111 0 0 10 10
代码长度是35。
因此，通过使用二叉树能够适当地缩短编码长度，特别是在编码长度长、权重分布不均匀的情况下，通过使用zgdhm编码能够大幅缩短编码长度。
代码实现# include iostream # include stdlib.husingnamespacestd； 常数最大值=10000； //初始设定权重的最大值const int MaxBit=4； //初始设定的最大编码位数const int MaxN=10； //默认的最大节点数struct HaffNode//哈夫曼树的节点结构{ int weight； //权重int flag； 标记int parent； //父母节点的下标int leftChild； //左旁注int rightChild； //右边孩子的下标； 存储结构代码//霍夫曼编码的数据元素结构{ int bit[MaxBit]； //序列int start； //编码开始下标int weight； //文字权重}； voidhaffman(intweight (，int n，HaffNode haffTree[] ) ) /建立叶节点数n权重为weight的霍夫曼树hafftree(intj，m1，m2，x1，x2； //霍夫曼树haffTree初始化。 n个叶节点的霍夫曼树共有2n-1个节点for(intI=0； I
2 * n - 1; i++) { if (i<n) haffTree[i].weight = weight[i]; else haffTree[i].weight = 0; //注意这里没打else那{}，故无论是n个叶子节点还是n-1个非叶子节点都会进行下面4步的初始化 haffTree[i].parent = 0; haffTree[i].flag = 0; haffTree[i].leftChild = -1; haffTree[i].rightChild = -1; } //构造哈夫曼树haffTree的n-1个非叶结点 for (int i = 0; i<n - 1; i++) { m1 = m2 = MaxValue;//Maxvalue=10000;(就是一个相当大的数) x1 = x2 = 0;//x1、x2是用来保存最小的两个值在数组对应的下标 for (j = 0; j<n + i; j++)//循环找出所有权重中，最小的二个值--morgan { 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[])//由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode{ Code *cd = new Code; int child, parent; //求n个叶结点的哈夫曼编码 for (int i = 0; i<n; i++) { //cd->start=n-1;//不等长编码的最后一位为n-1, cd->start = 0;//,----修改从0开始计数--morgan cd->weight = haffTree[i].weight;//取得编码对应权值的字符 child = i; parent = haffTree[child].parent; //由叶结点向上直到根结点 while (parent != 0) { if (haffTree[parent].leftChild == child) cd->bit[cd->start] = 0;//左孩子结点编码0 else cd->bit[cd->start] = 1;//右孩子结点编码1 //cd->start--; cd->start++;//改成编码自增--morgan child = parent; parent = haffTree[child].parent; } //保存叶结点的编码和不等长编码的起始位 //for(intj=cd->start+1;j<n;j++) for (int j = cd->start - 1; j >= 0; j--)//重新修改编码，从根节点开始计数--morgan haffCode[i].bit[cd->start - j - 1] = cd->bit[j]; haffCode[i].start = cd->start; haffCode[i].weight = cd->weight;//保存编码对应的权值 }}int main(){ int i, j, n = 4, m = 0; int weight[] = { 2,4,5,7 }; HaffNode*myHaffTree = new HaffNode[2 * n - 1]; Code*myHaffCode = new Code[n]; if (n>MaxN) { cout << "定义的n越界，修改MaxN!" << endl; exit(0); } Haffman(weight, n, myHaffTree); HaffmanCode(myHaffTree, n, myHaffCode); //输出每个叶结点的哈夫曼编码 for (i = 0; i<n; i++) { cout << "Weight=" << myHaffCode[i].weight << " Code="; //for(j=myHaffCode[i].start+1;j<n;j++) for (j = 0; j<myHaffCode[i].start; j++) cout << myHaffCode[i].bit[j]; m = m + myHaffCode[i].weight*myHaffCode[i].start; cout << endl; } cout << "huffman's WPL is:"; cout << m; cout << endl; return 0;} 结语本文主要介绍了zgdhm树的实际意义和如何构造一棵二叉树。学习zgdhm树主要是掌握zgdhm树的构造思想以及构造过程，至于代码实现则是次要的，而且zgdhm编码实现过程中运用到了贪心算法。