- 1、本文档共69页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[工学]计算机软件技术基础课件-第2章 常用数据结构及其运算2非线性
1、先序遍历 算法思想: ①访问根结点; ②先序遍历左子树; ③先序遍历右子树。 例:对图所示二叉树, 先序遍历次序为: A B D G E C F H 2、中序遍历 算法思想: ①中序遍历左子树; ②访问根结点; ③中序遍历右子树 例:对右图所示二叉树, 中序遍历次序为: D G B E A F H C 3、后序遍历 算法思想 ①后序遍历左子树; ②后序遍历右子树; ③访问根结点 例:对右图所示二叉树, 后序遍历次序为: G D E B H F C A 后序遍历次序为: G D E B H F C A 2.5树与二叉树 2 2 2 4 4 4 5 5 5 7 7 7 WPL = 2*2+ WPL = 2*1+ WPL = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 = 35 带权路径长度达到最小 五、哈夫曼树 2.5树与二叉树 哈夫曼树 :带权路径长度最小的二叉树。 2 4 5 7 五、哈夫曼树 完全二叉树不一定是哈夫曼树 权值越大的结点离根越近 哈夫曼树不唯一,但WPL值一定相等。 2.5树与二叉树 (1) 由给定的 n 个权值 {w0, w1, w2, …, wn-1},构造具有 n 棵二叉树的森林 F = { T0, T1, T2, …, Tn-1 },其中每棵二叉树 Ti 只有一 个带权值 wi 的根结点, 其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止: ① 在 F 中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 ② 在 F 中删去这两棵二叉树。 ③ 把新的二叉树加入 F。 哈夫曼树的构造: 五、哈夫曼树 F : {7} {5} {2} {4} F : {7} {5} {6} F : {7} {11} 7 5 2 4 初始 合并{2} {4} 7 5 2 4 6 F : {18} 11 7 5 2 4 6 合并{5} {6} 5 合并{7} {11} 2 7 4 6 11 18 2.5树与二叉树 五、哈夫曼树 考试成绩分布表 2.5树与二叉树 五、哈夫曼树 哈夫曼树的应用-判定树 哈夫曼树的应用-判定树 不及格 及格 中 良 优 60? 70? 80? 90? 0.10 0.15 0.25 0.35 0.15 ≥ ≥ ≥ ≥ WPL = 0.10*1+0.15*2+0.25*3+0.35*4+0.15*4 = 3.15 2.5树与二叉树 五、哈夫曼树 最佳判定树 不及格 及格 中 良 优 60? 70? 80? 90? 0.10 0.15 0.25 0.35 0.15 ≥ ≥ ≥ ≥ WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2 = 0.3+0.45+0.5+0.7+0.3 = 2.25 2.5树与二叉树 五、哈夫曼树 主要用途是实现数据压缩。 设给出一段报文: CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T },各个字符出现的频度(次数)是 W={ 2, 7, 4, 5 }。 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36. 2.5树与二叉树 五、哈夫曼树 哈夫曼树的应用-哈夫曼编码 若按各个字符出现的概率不同而给予不等长编码,可望减少总编码长度。 各字符出现概率为{ 2/18, 7/18, 4/18, 5/18 },化整为 { 2, 7, 4, 5 }。以它们为各叶结点上的权值, 建立哈夫曼树。左分支赋 0,右分支赋 1,得哈夫曼编码(变长编码)。 2.5树与二叉树 五、哈夫曼树 7 2 5 4 0 1 0 0 1 1 A C T S A : 0 T : 10 C : 110 S : 111 它的总编码长度:7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。 总编码长度正好等于哈夫 曼树的带权路径长度WPL。 哈夫曼编码是一
您可能关注的文档
- [工学]计算机网络第2章.ppt
- [工学]计算机网络管理复习大纲答案.doc
- [工学]计算机网络授课课件第十一讲_网络层6.ppt
- [工学]计算机网络第4章.ppt
- [工学]计算机网络统考串讲习题部分.pdf
- [工学]计算机网络第4章 MAC层.ppt
- [工学]计算机网络技术实用教程第四版第12章 电子工业出版社.ppt
- [工学]计算机软件基础孟彩霞第7章 关系数据库系统.ppt
- [工学]计算机网络课件第02次CH1-5ed_概述02.ppt
- [工学]计算机过程控制-第一章.ppt
- J医药公司存货管理的内部控制问题研究共3篇.pdf
- 作品版权登记代理合同模板5篇.pdf
- 河南省南阳市卧龙区2022-2023学年八年级上学期期中调研测试地理试卷(含答案).pdf
- 江西省九江市2023学年中考三模英语试题含答案及点睛.pdf
- 水利工程知识点-隐蔽单元工程验收.pdf
- 医院办公室2023年度工作计划.pdf
- 公司项目到期模板合集(7篇).pdf
- 江苏省海门中学2022-2023学年高一第一学期期末测试英语含答案.pdf
- 江苏省扬州市高邮市校联考2023-2024学年七年级上学期期末语文试题(含答案).pdf
- 江苏开放大学实用法律基础第一次形成性考核作业第二单元作业第二单元练习题.pdf
最近下载
- 2024版 《全民所有自然资源资产核算通则》(报批稿).pdf VIP
- 人教部编版小学道德与法治 这些事我来做 第一课时 教案 教学设计.docx VIP
- 2024-2030年中国远红外线治疗仪行业市场发展趋势与前景展望战略分析报告.docx
- D--TDDownload-松下_AAD03010门机说明书(中文).pdf
- 专题11 导数中的双变量问题2023-2024学年新教材高中数学选择性必修第二册同步教学设计 (北师大版2019).docx
- 环氧车间分析方法标准汇编全解.doc
- 城市轨道交通工程质量安全检查指南(建质[2016]173号).doc
- 标准图集 - 12J003 室外工程.pdf VIP
- 节假日(春节)期间赶工措施.docx VIP
- 部编版一年级汉语拼音拼读练习.doc VIP
文档评论(0)