一，哈夫曼树的基本概念
路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径
结点的路径长度：两结点之间路径上的分支数
树的路径长度：从树根到每一个结点的路径长度之和．记作：ＴＬ
权（weight)：将树中结点赋给一个有着某种含义的数值，则这个数值秒针为该结点的权
结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积．
树的带权路径长度：树中所有叶子结点的带权路径长度之和．记作:WPL(Weighted Path Length)
哈夫曼树：最优树（带权路径长度（ＷＰＬ）最短的树）
注：＂带权路径长度最短＂是在＂度相同＂的树中比较而得的结果，因此有最优二叉树，最优三叉树之称等等．
哈夫曼树：最优二叉树（带权路径长度最短的二叉树）
特点：
１满二叉树不一定是哈夫曼树．
２哈夫曼树中权越大的叶子离根越近．
３具有相同带权结点的哈夫曼树不惟一．
二，哈夫曼树的构造算法
因为哈夫曼树权越大的叶子离根越近的特点，所以，构造哈夫曼树时首先选择权值小的叶子结点．
哈夫曼算法（构造哈夫曼树的方法）
（１）根据n个给定的权值构成n棵二叉树的森林，森林中每一棵树只有一个带权的根结点（构造森林全是根）
（２）在森林中，选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根结点的权值之和．（选用两小造新树）
（３）在森林中删除这两棵树，同时将新得到的二叉树加入到森林中．（删除两小添新人）
（４）重复（２）和（３），直到森林中只有一棵树为止，这棵树即为哈夫曼树．（重复２，３剩单根）
例：有４个结点a,b,c,d，权值分别人8,6,3,5,构造哈夫曼树
１，构造森林全是根
２，选用两小造新树
３，删除两小添新人
４，重复２，３剩单根
当最后森林只剩下一个根时，这棵树就是哈夫曼树
哈夫曼树当中：
１，只有度为0或２的结点，没有度为１的结点
２，包含n个叶子结点的哈夫曼树中共有2n-1个结点
三，哈夫曼树构造算法的实现
这里采用顺序存储结构－－－一维结构数组
结点类型定义：(包含４个成员的结构体）
typedef struct{
int weight;//权重
int parent,lch,rch;//双亲，左孩子，右孩子
}HTNode,*HuffmanTree;
有n个叶子结点的哈夫曼树中共有2n-1个结点，这里为了方便，不使用0下标，数组大小为2n
先定义一个数组ＨuffmanTree H(H是一个指针，也可以是一个数组）
具体的实现如下：
四，哈夫曼树的应用（哈夫曼编码）
前缀编码：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀
什么样的前缀码能使得电文总长最短？－－－－－哈夫曼编码
１,统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）．
２,利用哈夫曼树的特点：权越大的叶子离根越近;将每个字符的概率值作为权值，构造哈夫曼树．则概率越大的结点，路径越短．
３,在哈夫曼树的每个分支上标上0或１：结点的左分支标0，右分支标１．把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码．
例：要传输的字符集Ｓ＝｛Ｄ，Ｉ，Ｃ，Ｔ，；｝
字符出现频率 Ｗ＝｛２，４，２，３，３｝
那么构造出来的哈夫曼树就是：
然后在哈夫曼树的每个分支上标上0或１，结点的左分支标0，右分支标１
把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码．
那么Ｔ的编码为：00，；的编码为01，Ｉ的编码为10，Ｄ的编码为110，Ｃ的编码为111
如果这个字符集中有一段电文是｛ＤＩＴ；ＤＩＣ；ＴＤＩ；｝那么它的编码就可以写成：
001001
相反，如果收到的编码是，那么翻译过来就是ＩＴＤ；
哈夫曼编码能够保证是前缀码，即每个编码都不是另一个编码的前缀
哈夫曼编码能够保证字符编码总长最短
所以，哈夫曼编码的性质有：
１，哈夫曼编码是前缀码
２，哈夫曼编码是最优前缀码
五，哈夫曼编码的算法实现
1,字符串翻译成哈夫曼编码
（１）首先以字符集对应的字符权重，创建哈夫曼树
（２）依次从每个叶子结点，往上回溯，如果有双亲，判断该叶子结点是双亲的左孩子还是右孩子，如果是左孩子，记录0，如果是右孩子，记录１，直到回溯到根结点，这些组合起来的0和１就是哈夫曼的编码，我们用一个指针数组存储每个叶子结点的哈夫曼编码
例：已知｛a,b,o,u,t}对应的出现频率为{3,4,5,6,7}
那么a,b,o,u,t分别对应的哈夫曼编码是多少？
＂aoutbabtoutbaotubatobatu"对应的哈夫曼编码是多少？
２,哈夫曼编码翻译成字符串
（１）首先以字符集对应的字符权重，创建哈夫曼树
（２）从根结点开始，对应着编码，如果编码是0，则指向根结点的左孩子，如果编码是１，则指向根结点的右孩子，然后把左孩子或右孩子当成根结点，根据提供的哈夫曼编码继续向下推，直到找到的结点没有左右孩子，为叶子的时候，就可以得到该结点的权值和字符．
注意：哈夫曼树对应的数组ＨＴ中，叶子结点是在数组最前面下标１开始，依次排列．根结点在数组的最后也就是下标为２n（n个叶子结点，下标从１开始）
例：以上面例子，继续
已知｛a,b,o,u,t}对应的出现频率为{3,4,5,6,7}
那么110对应的字符串是什么？
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/13288.html