关注网站怎么做,网络工程师教程,营销型网站设计网站,网络舆情监控文章目录 哈夫曼树#xff08;最优二叉树#xff09;定义举个#x1f330;#xff08;WPL的计算#xff09; 哈夫曼树的构造#xff08;最优二叉树的构造#xff09;举个#x1f330; 哈夫曼树的性质 哈夫曼编码定义构造 哈夫曼树#xff08;最优二叉树#xff09;
… 文章目录 哈夫曼树最优二叉树定义举个WPL的计算 哈夫曼树的构造最优二叉树的构造举个 哈夫曼树的性质 哈夫曼编码定义构造 哈夫曼树最优二叉树
在介绍哈夫曼树之前我们需要介绍一些概念 路径路径是指从一个结点到另一个结点的之间所经过的所有结点构成的序列。 路径长度路径长度是路径上所经过的边的个数 权在应用树的时候我们常常会将树的结点赋予一个表示某种意义的数值这个值称为权。 结点的带权路径长度从根结点到一个结点的路径长度 * 该结点的权值 该结点的带权路径长度。 树的带权路径长度WPL树中所有叶结点的带权路径长度之和称为树的带权路径长度
定义
在含有n个带权叶结点的二叉树中其中带权路径最小的二叉树称为哈夫曼树也称最优二叉树。
举个WPL的计算 第一棵树的 W P L 7 ∗ 2 5 ∗ 2 2 ∗ 2 4 ∗ 2 36 WPL7*25*22*24*236 WPL7∗25∗22∗24∗236
第二棵树的 W P L 4 ∗ 2 7 ∗ 3 5 ∗ 3 2 ∗ 1 46 WPL4*27*35*32*146 WPL4∗27∗35∗32∗146
第三棵树的 W P L 7 ∗ 1 5 ∗ 2 2 ∗ 3 4 ∗ 3 35 WPL7*15*22*34*335 WPL7∗15∗22∗34∗335 第三颗树的 WPL 恰好是所有含有n个带权叶结点的二叉树中最小的因此第三棵树为哈夫曼树。 注意证明一个树是否为哈夫曼树要看的是所有含有n个带权叶结点的WPL而不是给几个二叉树选其中WPL最小的。当然由于这种证明几乎不可能实现所以要证明一棵树为哈夫曼树我们只需要证明它的结构符合最优构造方法即可——因为哈夫曼树并不唯一例如把一颗哈夫曼树的左右子树交换它就构成了一棵新的哈夫曼树。 哈夫曼树的构造最优二叉树的构造
给定 n n n 个权值分别为 w 1 , w 2 , . . . , w n w_1,w_2,...,w_n w1,w2,...,wn 的结点构造最优二叉树的方法如下
将这 n n n 个结点视为 n n n 棵只有一个结点的二叉树它们构成了一个森林 F F F。在森林中选择两颗根节点权值最小的二叉树 T 1 , T 2 T_1,T_2 T1,T2新增一个结点 N N N把 T 1 , T 2 T_1,T_2 T1,T2 的根节点作为 N N N 的左、右孩子构成一棵新的二叉树 T 3 T_3 T3 N N N的权值等于 T 1 , T 2 T_1,T_2 T1,T2的根的权值之和。从 F F F 中删除 T 1 , T 2 T_1,T_2 T1,T2把 T 3 T_3 T3加入到 F F F 中。重复步骤 2 , 3 2,3 2,3直到 F F F 中只剩下一颗树。
如果对哈夫曼树的构造方法的正确性感兴趣的同学可以搜一搜哈夫曼树的构造方法的正确性证明。
举个 把这几个叶结点按权值的从小到大排列有 选择权值最小的两个结点构成新的二叉树有 继续选择两个最小的结点有 继续 这样我们就得到一颗哈夫曼树了
哈夫曼树的性质
初始结点最终都为叶结点并且权值越小的结点到根节点的路径长度越大。因此哈夫曼树的结点总数为 2 ∗ n − 1 2*n-1 2∗n−1因为构造的过程中新增了n-1个结点即新增了n-1个分支结点。哈弗曼树中不存在度为1的结点因为每次构造都是选择两颗树作为新结点的子节点。哈夫曼树的带权路径长度等于所有分支结点的权值之和。 哈夫曼编码
在了解哈夫曼编码前我们先了解一些相关的概念
定长编码长度固定的编码。变长编码长度不固定的编码。前缀编码没有一个编码是另一个编码的前缀这样的编码叫做前缀编码显然根据定义来说定长编码一定是前缀编码变长编码不一定是前缀编码。
对于前缀编码来说我们可以用树辅助构造前缀编码。
例如假设要为abcd四个字符设计二进制前缀编码那么我们可以用二叉树来辅助构造。
为了使编码能够符合前缀编码的要求显然a、b、c、d不会出现在分支结点上。
我们设从任意结点往左边走代表0从任意结点往右边走代表1即指向左子树的边代表0指向右子树的边代表1那么a、b、c、d的编码为从根节点到对应叶结点所经过的边代表的值的序列。
我们可以得到如下所示的二叉树 a的编码为0b的编码为10c的编码为110d的编码为111
显然没有一个编码是另一个编码的前缀这种编码是前缀编码。
定义
哈夫曼编码是一种变长的二进制前缀编码它利用哈夫曼树来辅助构造编码能够非常有效地压缩二进制数据。
构造
我们将每一个字符当做一个独立的结点其权值等于它出现的次数或频度构造一棵哈夫曼树。
设从任意结点指向左子树的边代表0指向右子树的边代表1或指向左子树的边表示1指向右子树的边表示0。则各个结点的编码为从根节点到对应结点所经过的边代表的值的序列。
上面的例子就是一个构造哈夫曼编码的案例。 注意相同结点构造出的哈夫曼树并不唯一因为它并没有限制到底是左大右小还是右大左小。但相同结点构造出的不同的哈夫曼树的WPL一定是相同的。 同理哈夫曼编码也是不唯一的。 全篇至此结束感谢观看。
