本文主要介绍使用C语言详细讲解霍夫曼树的数据结构，包括一个AMC相关的例子。需要演示的朋友可以参考一下。
1、基本概念
一、路径和路径长度
如果存在节点序列k1，k2，kj在一棵树上，这样ki就是ki 1的父(1=ij)，那么这个节点序列就叫做k1到kj的路。
从k1到kj的分支数称为这两点之间的路径长度，等于路径上的节点数减1。
b、结点的权和带权路径长度
在很多应用中，树中的一个节点往往会被赋予一个具有一定含义的实数，我们称之为节点的权重(比如下面树中的蓝色数字表示节点的权重)。
节点的加权路径长度被定义为从根节点到该节点的路径长度与该节点上的权重的乘积。
c、树的带权路径长度
树的加权路径长度定义为树中所有叶节点的加权路径长度之和，公式为：
其中n表示叶节点的数量，wi和li分别表示叶节点ki的权重和从根节点到ki的路径长度。
下图中树的加权路径长度WPL=9X212X215X26X3X45X4=122
霍夫曼树
哈夫曼树也叫最优二叉树。它是由N个加权叶节点组成的所有二叉树中加权路径长度WPL最小的二叉树。
下面是一个霍夫曼树的示意图。
2、构造哈夫曼树
假设有n个权重，构造的霍夫曼树有n个叶节点。n个权重被设置为w1、w2，wn，霍夫曼树的构造规则如下：
(1) w1、w2、wn被认为是有n棵树的森林(每棵树只有一个节点)；
(2)从待合并的森林中选择根节点权重最小的两棵树作为新树的左右子树，新树的根节点权重为其左右子树的根节点权重之和；
(3)从林中删除所选的两棵树，并向林中添加新树；
(4)重复步骤(2)和(3)，直到森林中只剩下一棵树，这就是得到的霍夫曼树。
例如，要构建下图中具有六个加权叶节点的Huffman树，步骤如下：
注意：为了使霍夫曼树的结构尽可能唯一，通常规定生成的霍夫曼树中每个节点的左子树的根节点的权重小于或等于右子树的根节点的权重。
具体算法如下：
//2.根据数组A中的n个权值构建霍夫曼树，返回根指针。
struct b treenode * create Huffman(elem type a[]，int n)
{
int i，j；
struct BTreeNode **b，* q；
b=malloc(n * sizeof(struct b treenode))；
for(I=0；I n；I) //初始化B指针数组，使每个指针元素指向A数组中对应的元素节点。
{
b[I]=malloc(sizeof(struct b treenode))；
b[I]-data=a[I]；
b[I]-左=b[I]-右=空；
}
for(I=1；I n；I )//不进行n-1次循环来构建霍夫曼树。
{
//k1表示林中权重最小的根节点的下标，k2是下一个最小的下标。
int k1=-1，k2；
for(j=0；j n；J )//让k1最初指向森林中的第一棵树，k2指向第二棵树
{
if (b[j]！=空k1==-1)
{
k1=j；
继续；
}
if (b[j]！=空)
{
k2=j；
打破；
}
}
for(j=k2；j n；J )//从当前森林中找到最小权重树和第二个最小值
{
if (b[j]！=空)
{
if(b[j]-数据b[k1]-数据)
{
k2=k1
k1=j；
}
否则if(b[j]-数据b[k2]-数据)
k2=j；
}
}
//从最小权值树和次最小权值树构建新树，Q指向根节点。
q=malloc(sizeof(struct b treenode))；
q-data=b[k1]-data b[k2]-data；
q-left=b[k1]；
q-right=b[k2]；
b[k1]=q；//将指向新树的指针赋给指针数组b中的k1位置。
b[k2]=空；//k2位置为空
}
免费(b)；//删除动态创建的数组b。
返回q；//返回整个霍夫曼树的根指针
}
3、哈夫曼编码
在电报通信中，消息以0和1的二进制序列传输，每个字符对应一个二进制代码。为了缩短消息的总长度，使用不等长编码来构造霍夫曼树。
在从根节点到每个叶子节点的路径上，每个字符的出现频率被赋予叶子节点作为字符节点的权重，每个分支节点的左右分支分别用0和1编码。
分支的0和1编码序列等于叶节点的二进制码。如上图所示的霍夫曼编码如下：
A的代码是：00。
B的代码是：01
C的代码是：100。
D的代码是：1010
E的代码是：1011。
f的代码是：11
4、哈夫曼树的操作运算
以上文章中的哈夫曼树作为一个具体的例子，用一个详细的程序来说明哈夫曼树的操作。
# includestdio.h
#includestdlib.h
typedef int ElemType
结构树节点
{
元素类型数据；
struct BTreeNode * left
struct BTreeNode * right
};
//1.输出二叉树，可以在之前遍历的基础上修改。采用广义表格式，元素类型为int。
void print btree _ int(struct BTreeNode * BT)
{
如果(BT！=空)
{
printf('%d '，BT-data)；//输出根节点的值
如果(BT-左！=NULL | | BT-对！=空)
{
printf('(')；
print btree _ int(BT-left)；//输出左边的子树
如果(BT-对！=空)
printf('，')；
print btree _ int(BT-right)；//输出右边的子树
printf(')')；
}
}
}
//2.根据数组A中的n个权值构建霍夫曼树，返回根指针。
struct b treenode * create Huffman(elem type a[]，int n)
{
int i，j；
struct BTreeNode **b，* q；
b=malloc(n * sizeof(struct b treenode))；
for(I=0；I n；I) //初始化B指针数组，使每个指针元素指向A数组中对应的元素节点。
{
b[I]=malloc(sizeof(struct b treenode))；
b[I]-data=a[I]；
b[I]-左=b[I]-右=空；
}
for(I=1；I n；I )//不进行n-1次循环来构建霍夫曼树。
{
//k1表示林中权重最小的根节点的下标，k2是下一个最小的下标。
int k1=-1，k2；
for(j=0；j n；J )//让k1最初指向森林中的第一棵树，k2指向第二棵树
{
if (b[j]！=空k1==-1)
{
k1=j；
继续；
}
if (b[j]！=空)
{
k2=j；
打破；
}
}
for(j=k2；j n；J )//从当前森林中找到最小权重树和第二个最小值
{
if (b[j]！=空)
{
if(b[j]-数据b[k1]-数据)
{
k2=k1
k1=j；
}
否则if(b[j]-数据b[k2]-数据)
k2=j；
}
}
//从最小权值树和次最小权值树构建新树，Q指向根节点。
q=malloc(sizeof(struct b treenode))；
q-data=b[k1]-data b[k2]-data；
q-left=b[k1]；
q-right=b[k2]；
b[k1]=q；//将指向新树的指针赋给指针数组b中的k1位置。
b[k2]=空；//k2位置为空
}
免费(b)；//删除动态创建的数组b。
返回q；//返回整个霍夫曼树的根指针
}
//3.求霍夫曼树的加权路径长度。
elem type weightpathlength(struct b treenode * fbt，intlen)//len最初为0。
{
If (FBT==NULL) //空树返回0
返回0；
其他
{
if(fbt-left==null fbt-right==null)//访问叶节点
返回FBT-数据*长度；
Else //访问非叶节点，进行递归调用，返回左右子树的加权路径长度之和，len递增。
返回权重路径长度(FBT-左，镜头1)权重路径长度(FBT-右，镜头1)；
}
}
//4、霍夫曼编码(可以基于霍夫曼树加权路径长度的算法进行修改)
Void Huffman编码(struct b treenode * fbt，intlen)//len初始值为0
{
静态int a[10]；//定义一个静态数组A，保存每片叶子的代码。数组的长度至少是树深度减1。
如果(FBT！=NULL)//访问叶节点时，输出数组a中存储的0和1的序列码。
{
如果(FBT-左==空FBT-右==空)
{
int I；
printf('结点权值为%d的编码：'，FBT-数据);
for(I=0；我低输入联网（low-entry networking的缩写）我)
printf('%d '，a[I])；
printf(' \ n ')；
}
else//访问到非叶子结点时分别向左右子树递归调用，并把分支上的0、1编码保存到数组a
{ //的对应元素中，向下深入一层时低输入联网(低入门网络的缩写)值增一
a[len]=0；
赫夫曼科丁(FBT-左透镜1)；
a[len]=1；
赫夫曼科丁(FBT-右透镜1)；
}
}
}
//主函数
void main()
{
int n，I；
elem类型* a；
结构b树节点* fbt
printf('从键盘输入待构造的哈夫曼树中带权叶子结点数n:')；
while(1)
{
scanf('%d '，n)；
如果(北^ 1)
打破；
其他
printf('重输n值：');
}
a=malloc(n * sizeof(elem类型))；
printf('从键盘输入%d个整数作为权值：'，n)；
for(I=0；I n；我)
scanf(' %d '，a[I])；
fbt=CreateHuffman(a，n)；
printf('广义表形式的哈夫曼树：');
print btree _ int(fbt)；
printf(' \ n ')；
printf('哈夫曼树的带权路径长度：');
printf('%d\n '，WeightPathLength(fbt，0))；
printf('树中每个叶子结点的哈夫曼编码：\ n’)；
HuffManCoding(fbt，0)；
}
运行结果：
下面来看一道ACM题目
题目描述：
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即体重，题目需要输出所有结点的值与权值的乘积之和。
输入：
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2=n=1000)。
输出：
输出权值。
样例输入：
5
1 2 2 5 9
样例输出：
37
交流电代码
链表构建哈夫曼树（插入排序)
#包含标准视频
#包含标准库
#定义最大值1001
结构树
{
（同Internationalorganizations）国际组织重量；
结构htree * lchild
结构htree * rchild
结构htree *下一步
};
void addNode(struct htree *，struct htree *)；
struct htree* createHfmtree(int *，int)；
int getWpl(struct htree *，int)；
int main()
{
int w[max]；
int i，n，wpl
结构树* ht
while(scanf('%d '，n)！=EOF)
{
for(I=0；I n；我)
{
scanf('%d '，w[I])；
}
ht=createHfmtree(w，n)；
wpl=getWpl(ht，0)；
printf('%d\n '，wpl)；
}
返回0;
}
struct htree * createHfmtree(int * w，int n)
{
int I；
struct htree * head *、pl *、pr *、proot
head=(struct htree *)malloc(sizeof(struct htree))；
head-next=NULL；
for(I=0；I n；我)
{
struct htree * pnode=malloc(sizeof(struct htree))；
pnode-weight=*(w I)；
pnode-l child=pnode-r child=pnode-next=NULL；
addNode(head，pnode)；
}
while(head-next)
{
if(head-next-next==NULL)
打破；
pl=head-next；
pr=pl-next；
head-next=pr-next；
proot=(struct htree *)malloc(sizeof(struct htree))；
proot-weight=pl-weight pr-weight；
proot-l child=pl；
proot-rchild=pr；
addNode(head，proot)；
}
返回head-next；
}
void addNode(struct htree *head，struct htree *pnode)
{
结构htree * t=head
while(t-next t-next-weight pnode-weight)
t=t-next；
pnode-next=t-next；
t-next=pnode；
}
int getWpl(struct htree *ht，int level)
{
if(ht==NULL)
返回0;
如果(!ht-l孩子！ht-rchild)
{
返回ht-重量*级别；
}
返回getWpl(ht-lchild，一级)getWpl(ht-rchild，一级);
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。