赫夫曼(Huffman)树又称最优树，是1类带权路径长度最短的树，有着广泛的利用。
1 基本概念
① 结点路径：从树中1个结点到另外一个结点的之间的分支构成这两个结点之间的路径。
② 路径长度：结点路径上的分支数目称为路径长度。
③ 树的路径长度：从树根到每个结点的路径长度之和。
④ 结点的带权路径长度：从树的根结点到该结点的的路径长度与结点的权(值)的乘积。
权(值)：各种开消、代价、频度等的抽象称呼。
⑤ 树的带权路径长度：树中所有叶子结点的带权路径长度之和，记做：
WPL=w1?l1+w2?l2+?+wn?ln=∑wi?li (i=1,2,?,n)
其中：n为叶子结点的个数；wi为第i个结点的权值； li为第i个结点的路径长度。
⑥ Huffman树：具有n个叶子结点(每一个结点的权值为wi) 的2叉树不止1棵，但在所有的这些2叉树中，一定存在1棵WPL值最小的树，称这棵树为Huffman树(或称最优树) 。
根据n个权值 {w1, w2, ?,wn}，构造成n棵2叉树的集合F={T1, T2, ?,Tn}，其中每棵2叉树只有1个权值为wi的根结点，没有左、右子树；
② 在F当选取两棵根结点权值最小的树作为左、右子树构造1棵新的2叉树，且新的2叉树根结点权值为其左、右子树根结点的权值之和；
③ 在F中删除这两棵树，同时将新得到的树加入F中；
④ 重复②、③，直到F只含1颗树为止。
构造Huffman树时，为了规范，规定：
F={T1,T2, ?,Tn}中权值小的作为新构造的2叉树的左子树，权值大的作为右子树； 在取值相等时，深度小的作为新构造的2叉树的左子树，深度大的作为右子树。
例：构造权值集合为W={8, 3, 4, 6, 5, 5}的 Huffman树。
1 Huffman编码
在电报收发等数据通讯中，常需要将传送的文字转换成由2进制字符0、1组成的字符串来传输。为了使收发的速度提高，就要求电文编码要尽量地短。
要设计长短不等的编码，须保证任意字符的编码都不是另外一个字符编码的前缀，这类编码称为前缀编码。
Huffman树可以用来构造编码长度不等且译码不产生2义性的编码。
设电文中的字符集C={c1,c2, ?,ci, ?,cn}，各个字符出现的次数或频度集W={w1,w2, ?,wi, ?,wn}。
Huffman编码方法
以字符集C作为叶子结点，次数或频度集W作为结点的权值来构造 Huffman树。规定Huffman树中左分支代表“0”，右分支代表“1” 。
从根结点到每一个叶子结点所经历的路径分支上的“0”或“1”所组成的字符串，为该结点所对应的编码，称之为Huffman编码。
由于每一个字符都是叶子结点，不可能出现在根结点到其它字符结点的路径上，所以1个字符的Huffman编码不多是另外一个字符的Huffman编码的前缀。
若字符集C={a, b, c, d, e, f}所对应的权值集合为W={8, 3, 4, 6, 5, 5}，如图6⑵5所示，则字符a,b, c,d, e,f所对应的Huffman编码分别是：10，010，011，00 ，110，111。
(1) 数据结构设计
Huffman树中没有度为1的结点，有n个叶子结点的Huffman树共有2n⑴个结点，则可存储在大小为2n⑴的1维数组中。实现编码的结点结构如图6⑵6所示。
缘由：
◆ 求编码需从叶子结点动身走1条从叶子到根的路径；
◆ 译码需从根结点动身走1条到叶子结点的路径。
结点类型定义：
#define MAX_NODE 200 /* Max_Node>2n⑴ */
typedef struct
{ char elem; // 待编码字符
unsigned int Weight ; /* 权值域 */
unsinged int Parent , Lchild , Rchild ;
} HTNode, *HuffmanTree ;
typedef char **HuffmanCode;
typedef struct Node
{
char elem;
unsigned int m_weight;
}Node; // 字符及其权值
(2) Huffman树的生成
算法实现
待编码字符的输入：
cout<<"输入要编码字符个数:" ;
cin>>n;
w=(Node *)malloc(n*sizeof(Node));
cout<<"输入字符及其对应的权值："<<endl;
for(i=0;i<n;i++)
{
cin>>c>>wei;
w[i].elem=c;
w[i].m_weight=wei;
}
从前n个结点中，选取权值比较小的两个：最小的下标为s1，次小的下标s2
void Select(HuffmanTree HT,int n,int &s1,int &s2)
{ int i; s1=s2=0;
for(i=1;i<=n;i++)
{ if((HT[i].m_weight<HT[s2].m_weight)&&(HT[i].parent==0)&&(s2!=0))
{ if(HT[i].m_weight<HT[s1].m_weight)
{ s2=s1; s1=i; }
else s2=i;
}
if((s1==0||s2==0)&&HT[i].parent==0)
{ if(s1==0) s1=i;
else if(s2==0)
{ if(HT[i].m_weight<HT[s1].m_weight)
{ s2=s1; s1=i; }
else s2=i;
} // end of else if
} // end of if
} // end of for
return;
}
新结点的构造
for(i=n+1;i<=m;++i)
{
Select((*HT),i-1, s1,s2);
(*HT)[s1].parent=i; (*HT)[s2].parent=i;
(*HT)[i].lchild=s1;
(*HT)[i].rchild=s2;
(*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
}
(3) Huffman编码算法
根据出现频度(权值)Weight，对叶子结点的Huffman编码有两种方式：
① 从叶子结点到根逆向处理，求得每一个叶子结点对应字符的Huffman编码。
② 从根结点开始遍历整棵2叉树，求得每一个叶子结点对应字符的Huffman编码。
由Huffman树的生成知，n个叶子结点的树共有2n⑴个结点，叶子结点存储在数组HT中的下标值为1∽n。
① 编码是叶子结点的编码，只需对数组HT[1…n]的n个权值进行编码；
② 每一个字符的编码不同，但编码的最大长度是n。
编码
(*HC)=(HuffmanCode)malloc(n*sizeof(char*));
cd = (char *)malloc(n*sizeof(char));
cd[n-1]=' ';
for(i=1;i<=n;++i)
{
start=n⑴;
for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)
{
if((*HT)[f].lchild==(unsigned int)c)
cd[--start]='0';
else cd[--start]='1';
}
(*HC)[i]=(char *)malloc((n-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]);
}