哈夫曼树c_哈夫曼树select函数_哈夫曼树的构造

内容提要：哈夫曼编码

摘 要：字符编码与信息压缩是计算机应用的重要研究课题，许多学者对此作了很多非常有价值的研究。文章简单分析了二叉哈夫曼树的构造及编码，通过比较3种构造三叉哈夫曼树的算法，提出了构造任意K叉哈夫曼树及K进制的最优前缀编码的算法，并给出C语言源程序，使哈夫曼编码的应用范围变得更为广阔。

关键词： 哈夫曼树； 三叉哈夫曼树； K叉哈夫曼树；哈夫曼编码

中图分类号：TP312 文献标志码：A文章编号：1006-8228（2013）09-41-(）02

1 二叉哈夫曼树[1-2]的构造算法

对于给定的数据序列，要生成带权路径长度最小的二叉树，应让权值越大的叶结点越靠近树根，权值越小的叶结点越远离树根。哈夫曼树c哈夫曼最早给出了1个具有一般规律的算法，称之为哈夫曼算法。

根据给定的n个权值{W1，W2，W3，…，Wi，…，Wn}构成n棵二叉树的初始集合F={T1，T2，T3…，Ti，…，Tn}，其中每棵二叉树Ti中只有1个权值为Wi的根结点，它的左右子树均为空。

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

在F中删除这两棵树，同时将新得到的二叉树加入到集合F中。

重复和，直到集合F中只含有一棵树为止。这棵树便是哈夫曼树。

2 三叉哈夫曼树构造的扩展算法

与哈夫曼算法类似，可以每次取3个根结点权值最小的树作子树，构造一棵新的三叉树，算法思路如下。

根据给定的n个权值{W1，W2，W3，…，Wi，…，Wn}构成n棵三叉树的初始集合F={T1，T2，T3，…，Ti…，Tn}，其中每棵三叉树Ti中只有1个权值为Wi的根结点，它的左、中、右子树均为空。

在F中选取三棵根结点的权值最小的树作为左、中、右子树构造一棵新的三叉树，且新得到的三叉树的根结点的权值为其左、中、右子树的根结点的权值之和。哈夫曼树c

在F中删除这三棵树，同时将新得到的三叉树加入到集合F中。

重复和，直到集合F中只含有一棵树为止[3]。

此算法由二叉哈夫曼算法扩展而来，因而将它称为三叉哈夫曼树构造的扩展算法。

3 k叉哈夫曼树的构造

设有n个信源符号，在传输过程中的概率分别是W1，W2，W3，…，Wn，将概率设为权值。k0=（n-1）mod（k-1），当k0=0时，（n-1）/（k-1）为整数，哈夫曼树中只有度为0和k的结点；当k0≠0，即（n-1）/（k-1）不为整数时，需添加k-1-k0个权值为0的结点。算法思路如下。

作n棵树的集合F={T1，T2，T3，…，Ti，…，Tn}，每棵树Ti只有1个权值为Wi的根结点，且均无子女。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-36455-1.html