[数据结构] 哈夫曼树HuffmanTree、哈夫曼编码的c/c++语言实现 什么是哈夫曼树 先给出定义 定义 : 给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。 举个例子: 已知有4个叶子结点,他们的值分别是a=1, b=2, c=4, d=10; 用这4个叶子结点构建成一个二叉树 
这个27称为带权路径长度,即所有叶结点的权值(就是a,b,c,d的值)乘上其到根结点的路径长度(即经过了几条线) 当这个带权路径长度最小的时候,我们就称他为哈夫曼树,也称最优二叉树 数学方法构建哈夫曼树 构建方法描述 假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为： (1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。 例子 假设有5个叶子结点,权值由下图所示: 
第一步:先找出权值最小的两个结点 
第二步以这两个结点为叶子,构建一个二叉树,并且把这两个结点去除,再找出权值最小的两个结点 
这里有两个权值为8的结点,我们只需要任意取一个权值为8的结点就行; 从这里也可以看出,哈夫曼树是不唯一的,但是他们带权路径长度都相同; 第三步:重复以上步骤,直到只剩下最后一个结点为止 
这棵哈夫曼树到此构建完成,这棵树的带权路径长度为76. 用c/c++语言实现哈夫曼树 以下面的树为例 
首先定义下哈夫曼树的存储结构; 这里采用的是一个大小为2n-1的向量来存储哈夫曼树中的结点 “假设有n个叶子结点,哈夫曼树的总结点数为2n-1” 实现Select函数 哈夫曼树编码的实现 什么是哈夫曼编码 在远程通讯中，要将字符转换成二进制的字符串来传送 假如有一串字符ABACCDAAAC 常规的编码是 A = 00; B = 01 ;C = 10; D = 11; 00 01 00 10 10 11 00 00 00 00 01; 而如果采用哈夫曼编码的方式:A = 0;B = 110 ; C =10; D =111 ; 0 110 0 10 10 111 0 0 0 0 10; 这个差值会在字符变多,文本变长的情况越拉越大,而使用不等长编码的关键就在于采用 前缀编码,否者会使数据错乱,前缀编码可以采用二叉树设计; 哈夫曼编码就是使出现次数较多的字符采用尽可能短的编码方式; 哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。 哈夫曼编码的图示 如图所示 先将哈夫曼树画出来,左孩子为0,右孩子为1 
A的编码就是: 000 ; B为: 001; C为: 01; D为: 10; E为: 11; 哈夫曼编码的算法实现 这里我们仍然用创建哈夫曼树时的例子 首先创建两个数组,一个存放叶子结点的权值, 不用第 0 号位置,设为0; 
一个放叶子是其双亲的左孩子还是右孩子,左孩子为零,右孩子为1; 
完成代码即可创造如下的数组 
创建一个指向字符指针的指针,该数组存放每个叶子结点的哈夫曼编码 
测试哈夫曼编码 下面给出测试的主程序 测试结果 
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/88815.html
