树和二叉树(5哈夫曼树及其应用).ppt
111页1、6 6哈夫曼树及其应用 1 相关概念路径 从树中一个结点到另一个结点所经过的分支序列或者说结点序列 如结点A到结点F的路径为 A B E F A B C D E F G 6 6 1最优二叉树 路径长度 路径上面的分支个数 如A F的路径长度为3 A B C D E F G 树的路径长度 从树根到每一个结点的路径长度之和 如左边树的路径长度为 Len A B Len A C Len A D Len A E Len A F Len A G 1 1 2 2 3 3 12 A B C D E F G 结点的权值 在某些应用中 树中结点往往要和一定的数值联系起来 那么这个数值通常称为该结点的权值 简称权 如左图 A B C D E F G 4 1 2 5 3 7 结点的带权路径长度 该结点到根结点的路径长度与该结点上权的乘积 如结点E的带权路径长度为 Len E A 3 2 3 6 A B C D E F G 4 1 2 5 3 7 树的带权路径长度 树中所有叶子结点的带权路径长度之和 记作 WPL w1 L1 w2 L2 wn Ln A B C D E F G w1 w2 w3 w4 最优二叉
2、树 哈夫曼树 给定n个权值 w1 w2 wn 试构造一棵有n个叶子结点的二叉树 每个叶子结点带权为wi 构造出来的二叉树的形态可以有多个 我们把其中带权路径长度WPL最小的二叉树称作最优二叉树或者哈夫曼树 A B C D E F G w1 w2 w3 w4 2 哈夫曼算法 1 如何构造一棵哈夫曼树 我们首先通过一个例子来演示一下构造过程 当权值为 7 5 2 4 时 构造哈夫曼树 7 5 2 4 当权值为 7 5 2 4 时 构造哈夫曼树 7 5 2 4 6 当权值为 7 5 2 4 时 构造哈夫曼树 7 2 4 6 5 当权值为 7 5 2 4 时 构造哈夫曼树 7 2 4 6 5 11 当权值为 7 5 2 4 时 构造哈夫曼树 7 2 4 6 5 11 当权值为 7 5 2 4 时 构造哈夫曼树 7 2 4 6 5 11 18 2 哈夫曼算法的语言描述 根据给定的n个权值 w1 w2 wn 构成n棵二叉树的集合F T1 T2 Tn 其中每棵二叉树Ti中只有一个带权为wi的根结点 其左右子树为空 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树 且置新的二叉树的根结
3、点的权值为其左右子树上根结点的权值之和 在F中删除这两棵树 同时将新得到的二叉树加入F中 重复 和 直到F只含一棵树为止 这棵树便是哈夫曼树 6 6 2哈夫曼编码 对于字符串 ABACCDA 共有7个字符 4种字符 其中A B C D出现的次数分别为3 1 2 1 现在要对字符串进行0 1编码 有哪些方法 哪一种编码的长度最短 1 各种编码方式 1 定长编码 根据出现的字符种数进行编码字符串 ABACCDA 中共出现4种字符 那么可以用2位表示 那么字符串 ABACCDA 的编码将为 00010010101100 总长度为7 2 14位 1 各种编码方式 1 定长编码 根据出现的字符种数进行编码这种编码方式可以对应到二叉树 如右图所式 A B C D 0 0 0 1 1 1 1 各种编码方式 2 变长编码当A B C D按照如下形式进行编码时 那么字符串 ABACCDA 的编码将为 0110010101110 总长度为13位 比第二种方式又要短 采取这种变长编码方式 需要遵循一个原则 即每一个字符的编码都不应该是另一个字符编码的前缀 否则就会出现二义性 1 各种编码方式 2 变长编码这
4、种编码方式也可以对应到二叉树 如右图所式 A B C 0 0 1 1 D 0 1 1 各种编码方式 2 变长编码如当A B C D按照如下形式进行编码时 请将 0111 翻译成字符串 试一试 有哪些翻译方式 之所以会出现二义性 是因为出现了A的编码是C的编码的前缀 B的编码是D的编码的前缀 1 各种编码方式 2 变长编码这样 这些编码恢复成二叉树的形式时 不会形成A B C D恰好为二叉树的叶子结点 如右图 A C B 0 1 1 1 D 1 1 各种编码方式 从上面的分析可以看出 一个可用的编码必须满足每个字符的编码不能是其他编码的前缀 也可以看出 每一个可用的编码都可以转化成二叉树的形式 这样编码理论便可以与二叉树的一些性质结合起来 就可以应用二叉树的理论知识来解决编码问题 1 各种编码方式 3 哈夫曼编码假设编码过程中有以下对应关系 那么总的编码长度为 WPL w1 L1 w2 L2 w3 L3 w4 L4那么如何选择L1 L2 L3 L4的值 使得WPL最小呢 1 各种编码方式 3 哈夫曼编码 可以看出 该公式与哈夫曼树满足的公式一模一样 那么我们可以采取构造哈夫曼树的方式来求
《树和二叉树(5哈夫曼树及其应用).ppt》由会员灯火****19分享,可在线阅读,更多相关《树和二叉树(5哈夫曼树及其应用).ppt》请在金锄头文库上搜索。
《MySQL数据库基础实例教程(微版)》读书笔记
Oracle视图和索引操作
MBTI职业性格测验量表
SQL数据库教程4讲
2019年湘阴县第三中学高考生物简单题专项训练(含解析)
2019年耿马县民族中学高考生物简单题专项训练(含解析)
2019年楚雄师院附中高考生物简单题专项训练(含解析)
2019年桥梁工程师年终总结
2019年枣庄东方国际高考生物简单题专项训练(含解析)
2018年一级建造师公路工程实务考点归纳
2019年赣榆县高考生物简单题专项训练(含解析)
2019年春湾中学高考生物简单题专项训练(含解析)
高考地理复习汇总
2019年朝鲜中学高考生物简单题专项训练(含解析)
2019年沧州市运河区派尼中学高考生物简单题专项训练(含解析)
2018年甘肃公务员《行政职业能力测验》试题(网友回忆版)
宾语从句 (解析卷)---2023年中考英语考点详解+专项训练
2018年一级建造师通信与广电实务考点
2019年湖北省襄阳市中考数学试卷(解析版)
文言文阅读(解析版)
2024-04-29 40页
2024-04-28 29页
2024-04-09 29页
2024-04-08 25页
2024-04-08 13页
2024-04-08 17页
2024-04-08 17页
2024-04-08 11页
2024-04-08 14页
2024-04-08 17页