有哪些信誉好的足球投注网站- 1、本文档共28页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
- 5、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
- 6、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
数据结构第6章树和二叉树4赫夫曼树及其应用ppt课件
数据结构
Data Structures
张 凯
计算机学院 软件工程系
2011年3月12日
树和森林
第6章 树和二叉树
树的基本概念
二叉树
遍历二叉树和线索二叉树
赫夫曼树及其应用
基本术语
§6.5 赫夫曼(Huffman)树及其应用
路 径
路径长度
树的路径长度
带权路径长度
树的带权路径长度
霍 夫 曼 树
基本术语
§6.5 赫夫曼(Huffman)树及其应用
路径：由一结点到另一结点间的分支所构成
路径长度：路径上的分支数目
a→e的路径长度＝
2
树的路径长度：从树根到每一结点的路径长度之和
树长度＝
10
基本术语
§6.5 赫夫曼(Huffman)树及其应用
结点带权路径长度：结点到根的路径长度与结点上权的乘积
树的带权路径长度：树中所有叶子结点的带权路径长度之和
3
7
9
8
结点F的路径长度为2，其WPL=2×9=18
其中n表示叶子结点的数目
wi表示叶子结点ki的权值
li表示根到ki之间的路径长度
基本术语
§6.5 赫夫曼(Huffman)树及其应用
赫夫曼树：带权路径长度最小的树, 又称最优二叉树
树的带权路径长度如何计算？
Weighted Path Length
例：有四个叶子结点a,b,c,d，分别带权为 7, 5, 2, 4，由它们构成三棵不同的二叉树
§6.5 赫夫曼(Huffman)树及其应用
WPL=36
WPL=46
WPL= 35
Huffman树
构造最优树(赫夫曼算法)
§6.5 赫夫曼(Huffman)树及其应用
(1) 由给定的 n 个权值{w0, w1, w2, …, wn-1}，构造具有 n 棵扩充二叉树的森林F = { T0, T1, T2, …, Tn-1 }，其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点，其左、右子树均为空。
(2) 重复以下步骤, 直到 F 中仅剩下一棵树为止：
① 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
② 在 F 中删去这两棵二叉树。
③ 把新的二叉树加入 F。
第一步：
a
b
c
d
9
2
5
4
第二步：
第三步：
第四步：
a
b
c
9
6
5
4
d
2
a
b
c
9
6
5
4
d
2
11
a
b
c
9
6
5
4
d
2
11
20
第一步：
5
6
2
9
第二步：
第三步：
第四步：
7
5
6
2
9
7
7
5
6
2
9
7
7
13
5
6
2
9
7
7
13
16
第五步：
5
6
2
9
7
7
13
16
29
第一步：
5
6
2
9
第二步：
第三步：
第四步：
7
5
6
2
9
7
7
5
6
2
9
7
7
9
7
16
第五步：
5
7
2
6
9
7
16
13
29
13
5
6
2
7
13
第一步：
5
6
2
9
7
5
7
2
6
9
7
16
13
29
5
6
2
9
7
7
13
16
29
判定树 (赫夫曼树的应用之一)
§6.5 赫夫曼(Huffman)树及其应用
分数
0—59
60—69
70—79
80—89
90—99
比例
0.05
0.15
0.4
0.3
0.1
输入10000个数据，则需进行31500次比较。
判定树 (赫夫曼树的应用之一)
§6.5 赫夫曼(Huffman)树及其应用
分数
0—59
60—69
70—79
80—89
90—99
比例
0.05
0.15
0.4
0.3
0.1
以比例数为权构造一棵哈夫曼树，如(b)判断树所示。
再将每一比较框的两次比较改为一次
判定树 (赫夫曼树的应用之一)
§6.5 赫夫曼(Huffman)树及其应用
分数
0—59
60—69
70—79
80—89
90—99
比例
0.05
0.15
0.4
0.3
0.1
输入10000个数据，仅需进行22000次比较。
赫夫曼编码(赫夫曼树的应用之二)
§6.5 赫夫曼(Huffman)树及其应用
1）二进制编码
通信中，可以采用0、1的不同排列来表示不同的字符，称为二进制编码。
发送端需要将电文中的字符序列转换成二进制的0、1序列，即编码；
接受端需要把接受的0、1序列转换成对应的字符序列，即译码。
赫夫曼编码(赫夫曼树的应用之二)
§6.5 赫夫曼(Huffman)树及其应用
等长编码
不等长编码
A B C D
00 01 10 11
发送：A B A C C C C D A B
00 01 00 10
文档评论（0）