数据结构--哈夫曼树讲解学习.ppt

《数据结构--哈夫曼树讲解学习.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构--哈夫曼树二、哈夫曼树（最优二叉树）1．定义哈夫曼树是带权路径长度最小的二叉树，也称为最优二叉树。2.根据已知权值求哈夫曼树（1）方法1)权值由小到大排序。2)取出两个最小的权值Wi和Wi+i构造二叉树。其中：W=Wi＋Wi+1第五节哈夫曼树及其应用23)从权值序列划去Wi和Wi+1。若序列空，则哈夫曼树已形成；否则，将W加入权值序列，反复作1-3。（2）举例例10-8求图10-20给出的四个权值9、5、2、4的哈夫曼树及带权路径长度WPL。WPL＝9＊1＋5＊2＋（2＋4）＊3＝37第五节哈夫曼树及其应用33.哈夫曼树的性质由以上哈夫曼树的生成过程可看出有如下性质：

2、1)给定权值的哈夫曼树不唯一（这是因为在构造过程中不要求子树的顺序），但是WPL为定值。2)权值越大的节点离根节点就越近。3)哈夫曼树中无度为1的节点（n1=0）。4）哈夫曼树节点总个数n=2*叶子节点个数-1=2*权值个数-1=2n0-1。第五节哈夫曼树及其应用4三、哈夫曼树的应用树结构的应用极其广泛，哈夫曼树只是其中的一种应用方式，下面通过两个实例进行说明。例10-9某工厂对其产品质量进行自动检测，并根据检测结果划分产品的质量等级。等级标准如图10-22所示。如何由产品的检测结果d值确定其质量等级，试设计最优算法。第五节哈夫曼树及其应用5这是一个产品分类问题，当产品的件数很

3、多时，不同的分类方法其时间性能大不一样。如何求得最优的分类方法是本题的目的。具体是：以各等级出现的百分数为权值，构造哈夫曼树，所求最优分类算法如图10-23所示。第五节哈夫曼树及其应用6例10-10已知一串电文内容如下：AACBDADACBAADCADCADA。试为电文中各字符设计最优的二进制电文编码—哈夫曼编码。其最小长度的二进制串电文编码称为哈夫曼编码。求哈夫曼编码的方法是：1)以电文中各字符出现的次数为权值，构造哈夫曼树，该树的叶子节点表示电文中的一个字符。第五节哈夫曼树及其应用7上述电文中A、B、C、D四个字符出现的次数依次为9,2,4,50所构造的哈夫曼树第五节哈夫曼

4、树及其应用2)给哈夫曼树左子树边上置0，右子树边上置1。电文中各字符的哈夫曼编码为：从根到叶子（字符）节点路径上的二进制序列。此树称为哈夫曼编码树，也称为哈夫曼编码译码树。如图10-24b所示。可以看出，上述四个字符的哈夫曼编码为：A-1、B-010、C-011、D-008此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢