哈夫曼树学习资料

哈夫曼树 1、（哈夫曼（Huffman）树又称最优二叉树或最优搜索树，是一类带权路径长度最短的树。） ★什么是哈夫曼树？为了说明清楚，我们先举一个具体的实例。

★例：将学生的百分制成绩表转换为五分制成绩，大于或等于90分者表为\，80～90分为\，

70～79分为\，60～69为\，小于60分为\。

★转换过程的程序用分支结构是很容易实现的。如果每次的输入量很大，则应考虑程序的操作时间。

在实际问题中，学生的成绩在这五个等级上的分布是不均匀的，现假设其分布规律如下表所示。 分数 分布情况 90～100 10％ 80～89 30％ 70～79 40％ 60～69 15％ 0～59 5％ ★学生的成绩数据共10000个， 判定过程如下图所示（一种分支结构）

★如按此过程判断，则5％的数据需1次比较，15％的数据需2次比较，40％的数据需3次比较，40％的数据需4次

比较，因此10000个数据比较的次数为10000（5％＋2×15％＋3×40％＋4×40％）＝31500次 ★也即按如上图所示的分支结构与程序段，则10 000个数据需执行判断31500次。如果换一种分支结构，如下图所示，

则需比较的次数应为10000（3×20％＋2×80％）＝22000次，很明显，两种判断方法的效率是不一样的。那么能不能找到一种效率最高的判定方法呢？哈夫曼树就是一种最优的搜索方法。 另一种分支结构

★为了引入哈夫曼树，先介绍二叉树路径长度的概念。

★树中一个结点到另一个结点之间的路径长度是这两个结点之间的分支所构成的路径上的分支数。 ★由树的定义可知，从根结点到达树的每个结点有且仅有一种路径。我们规定根的层数为1，如果 树中某个结点的层次为k，则从根到该点的路径长度为（k－1）。

★如下图为三棵二叉树，其中图（a）所示的二叉树中，从根A到B，C，D，E，F，G，H，I的路径 长度分别为1，1，2，2，3，3，4，4。

三棵二叉树

★树的路径长度是从树的根结点到树的各个结点的路径长度之和，记作TL，例如上图所示的三棵二叉

树的路径长度分别为：

TL（a）＝0＋1＋1＋2＋2＋3＋3＋4＋4＝20 TL（b）＝0＋1＋1＋2＋2＋2＋2＋3＋3＝16 TL（c）＝0＋1＋1＋2＋2＋2＋2＋3＋3＝16

★若将上述概念推广到一般情况，考虑带权的结点，则某结点的带权路径长度是指该结点的路径长度 与该结点上权的乘积，二叉树的带权路径长度是指所有带权叶子结点的带权路径长度之和。

★如果假定一个有n个权值的集合{w1，w2，…，wn}，其中wi≥0（1≤i≤n），若T是一个有n个叶子 的二叉树，而且将权w1，w2，…，wn分别赋给树的n个叶子，则n个叶子的二叉树带权路径长度定义为：

★其中wi为叶子i的权，li为根结点到叶子i之间路径长度，在权w1，w2，w3，…，wn的二叉树中， WTL最小的二叉树称为哈夫曼树或最优树

★哈夫曼树又称最优二叉树。它是ｎ个带权叶子结点构成的所有二叉树中，带权路径长度WTL最

小的二叉树。因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称为哈夫曼树， 相应的算法称为哈夫曼算法。

★如何构造一棵带权路径长度最短的哈夫曼二叉树呢？哈夫曼提出了如下算法：

（1）根据n个权值{w1，w2，…，wn}构成n棵二叉树的森林T＝{T1，T2，…，Tn}，其中Ti只有一个带权为 wi的根结点，且左右子树均为空。

（2）在T中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

（3）在T中删除这两棵树，同时将新得到的二叉树加入森林中。

（4）重复（2）和（3），直到森林中只有一棵树为止，这棵树即为哈夫曼树。

★例如，给定权值集合{5，15，40，30，10}构造哈夫曼树的过程如下图所示，其中最优的 带权路径长度为：WTL＝（5＋10）×4＋15×3＋30×2＋40＝205由下图可以看出，哈夫 曼树的结点的度数为0或2，没有度为1的结点。

构造哈夫曼

树的过程

★现在我们来讨论如何实现哈夫曼树的算法。 设二叉树的结点结构为：

★其中w为该结点的权值，lchild，rchild分别为指向左、右孩子的指针。另外， 我们和一个带表头结点的单链表来表示森林中各树的根指针，它的初始状况如下图所示。 ★哈夫曼树构造完毕后，这个单链表除表头结点外，只有一个结点。单链表中的 结点结构为：

用链表结构表示的哈夫曼树构造的初始状态

★哈夫曼树的构造算法描述如下： # include \# include \# include \#define m 100

struct ptree // 定义二叉树结点类型 { int w; //定义结点权值

struct ptree * lchild; //定义左子结点指针 struct ptree * rchild; //定义右子结点指针 };

struct pforest // 定义链表结点类型 { struct pforest * link; struct ptree * root; };

int WTL=0; //初始化WTL为0 main( )

{struct ptree * hafm( ); void travel( );

struct ptree * head;

int n,i,w[m];

printf (\提示输入结点数 scanf (\输入结点数

printf (\提示输入每个结点的权值 for (i=1;i<=n;i++)

scanf (\输入每个节点权值 head=hafm(w,n); travel (head, 0);

printf (\输出最佳路径权值之和} void travel (head, n) //为了验证harfm算法的正确性进行的遍历 struct ptree * head; int n;

{struct ptree * p; p=head;

if (p!=NULL) {

if ((p->lchild)= =NULL&& (p->rchild) = =NULL) //如果是叶子结点 {

printf (\

printf (\WTL=WTL+n* (p->w); //计算权值 }

travel (p->lchild, n+1); travel (p->rchild, n+1); } }

struct ptree * hafm (w, n) int n;

int w[m]; {

struct pforest * inforest ( ); struct pforest * p1, * p2, * f;

struct ptree * ti, * t, * t1, * t2; int i;

f=(struct pfores * )malloc(sizeof(struct pforest)); f->link=NULL;

for (i=1;i<=n;i++) // 产生n棵只有根结点的二叉树

{ti= (struct ptree *)malloc(sizeof(struct ptree)); //开辟新的结点空间 ti->w=w[i]; //给结点赋权值 ti->lchild=NULL; ti->rchild=NULL; f=inforest (f, ti); }

while(((f->link)->link)!=NULL) // 至少有二棵二叉树 {p1=f->link; p2=p1->link;

f->link=p2->link; // 取出前两棵树 t1=p1->root; t2=p2->root;

free(p1); //释放p1 free(p2); //释放p2

t=(struct ptree *)malloc (sizeof(struct ptree)); //开辟新的结点空间 t->w=t1->w+t2->w; // 权相加 t->lchild=t1;

t->rchild=t2; // 产生新二叉树 f=inforest (f, t); }

p1=f->link; t=p1->root;

return(t); //返回t

}struct pforest * inforest (f, t) struct pforest * f; sturct ptree * t;

{struct pforest * p, * q, * r; struct ptree * ti;

r=(struct pforest *) malloc(sizeof(struct pforest)); //开辟新的结点空间 r->root=t; q=f;

p=f->link; //

while (p!=NULL) // 寻找插入位置 {ti=p->root;

if (t->w>ti->w) //如果t的权值大于ti的权值 {q=p;

p=p->link; //p向后寻找 }else

p=NULL; // 强迫退出循环 }r->link=q->link;

q->link=r; //r接在q的后面 return (f); //返回f }

哈夫曼编码的应用

★哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应用之一。在电讯通信业务中，通

常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。例如，如果在电文 中只用到A，B，C，D四种字符，它的二进制编码分别为00，01，10，11，此时若需要传送电文 \，则实际传送的电文为\，译码员按两位进行分组译码，恢复原来的电文。

★在编码过程通常要考虑两个问题，一是数据的最小冗余编码问题，二是译码的惟一性问题。 因为在实际应用中，各个签字的出现频度是不尽相同的，有些字符出现的频率较高，有些字符 出现的频率较低，我们希望用较短的编码来表示那些出现频率大的字符，用较长的编码来表示 出现频率少的字符，从而使得编码序列的总长度最小，使所需总空间量最少。这就是最小冗余 编码问题。字符的不同长度编码还应考虑到译码的惟一性，这就要求任意一个字符的编码都不 能是另外一个字符编码的前缀。利用最优二叉树可以很好地解决这两个问题。

★假定要编码的字符集为{c1，c2，…，cn }，设各个字符的文本中出现的次数（或频率）为 集合{ w1，w2，…，wn }。显然，可以把提出的问题归结为构造一棵有n个叶子的哈夫曼叶子 中的权值代表字符ci（1≤i≤n）的出现次数wi。最优编码的标准是使下面的带权路径长度具 有最小值。

这里l是字符ci的编码长度，即从根结点到叶子wi的路径长度。

★例如，设有一文本的字符序列是： DATA TRERTER ARE AREA ART

上面的文本里面字符集为{A，D，T，R，E}，各字母出现的次数为{6，1，4，6，4}。 现设计每个字母的最优编码。

可以选用{6，1，4，6，4}作权构造一棵最优树，如下图所示。

最优编码示例

★ 规定从各非终端结点发出的左分支上标上0，右分支上标上1，于是，从根结点到叶子的路径 上的0和1组成的序列，就是该叶子所对应的字母编码，本例中各字母的哈夫曼码为 字母 编码 A 10 D 010 T 011 R 11 E 00 ★可以看出，根据权值集合构造的哈夫曼树得出的哈夫曼码，确实使得出现次数（或频率）与码 长有一个相反的关系，使得电文的总码长最短，同时，每一个字符的编码又避免了是另一个字符 编码的前缀，保证了译码的惟一性。当然，在实际应用中，由于字符的编码长度不一致，会给译 码带来困难，通常还是采用固定长度的字符编码。

最优编码示例

★ 规定从各非终端结点发出的左分支上标上0，右分支上标上1，于是，从根结点到叶子的路径 上的0和1组成的序列，就是该叶子所对应的字母编码，本例中各字母的哈夫曼码为 字母 编码 A 10 D 010 T 011 R 11 E 00 ★可以看出，根据权值集合构造的哈夫曼树得出的哈夫曼码，确实使得出现次数（或频率）与码 长有一个相反的关系，使得电文的总码长最短，同时，每一个字符的编码又避免了是另一个字符 编码的前缀，保证了译码的惟一性。当然，在实际应用中，由于字符的编码长度不一致，会给译 码带来困难，通常还是采用固定长度的字符编码。

本文来源：https://www.bwwdw.com/article/dcwo.html