《哈夫曼树及其应用》PPT课件

《哈夫曼树及其应用》PPT课件

ID:36871259

大小:1.17 MB

页数:55页

时间:2019-05-10

《哈夫曼树及其应用》PPT课件_第1页
《哈夫曼树及其应用》PPT课件_第2页
《哈夫曼树及其应用》PPT课件_第3页
《哈夫曼树及其应用》PPT课件_第4页
《哈夫曼树及其应用》PPT课件_第5页
资源描述:

《《哈夫曼树及其应用》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第六章 (续)哈夫曼树及其应用设有10000个学生某门课程的考试成绩的分布如下表所示:一、问题的提出分数0~5960~6970~7980~8990~100学生比例数0.050.150.400.300.10学生成绩数据分布情况表*问题:现在要编写程序依次根据每个学生的成绩打印出该学生的成绩等级。分数0~5960~6970~7980~8990~100学生比例数0.050.150.400.300.10学生成绩数据分布情况表方法1:a<60打印"bad“yesa<70no打印"pass"yesa<80no打印"general"yesa<90no打印"good"yes打印

2、"excellent"no5%的学生15%的学生40%的学生30%的学生10%的学生共做31500次比较读取一个学生成绩→a循环一万次i=1i<=10000N结束i=i+1分数0~5960~6970~7980~8990~100学生比例数0.050.150.400.300.10学生成绩数据分布情况表方法2:a<80打印"bad"yesa<90noyesnoa<70yesnoa<60yesno打印“good"打印"excellent"打印"pass"打印"general"5%的学生15%的学生40%的学生30%的学生10%的学生读取一个学生成绩→a循环一万次i=1i

3、<=10000N结束分数0~5960~6970~7980~8990~100学生比例数0.050.150.400.300.10学生成绩数据分布情况表方法2:a<80打印"bad"yesa<90noyesnoa<70yesnoa<60yesno打印“good"打印"excellent"打印"pass"打印"general"5%的学生15%的学生40%的学生30%的学生10%的学生共做22000次比较读取一个学生成绩→a循环一万次i=1i<=10000N结束思考:如何找到一棵最优的判断树使得编写出来的程序的运行时间是最高效的?1.哈夫曼树的有关概念①结点的路径长度:从

4、根结点沿某条路径到某结点途中所经历的弧的条数称为该结点的路径长度。二、哈夫曼树及其应用②树的路径长度:从根结点到每一个叶子结点的路径长度之和。④树的带权路径长度(WPL):树中所有叶子结点的带权路径长度之和称为树的带权路径长度。③结点的带权路径长度:某结点的路径长度与该结点上的权值的乘积称为该结点的带权路径长度。1.哈夫曼树的有关概念二、哈夫曼树及其应用实例:已知某二叉树的四个叶子结点a,b,c,d分别带权7,5,2,4,则可构造出有如下几种不同形式的二叉树:aaa777b5b5c2d4c2d4b5c2d4树的带权路径长度为:WPL=2*7+2*5+2*2+2*

5、4=36树的带权路径长度为:WPL=2*4+3*7+3*5+1*2=46树的带权路径长度为:WPL=1*7+2*5+3*2+3*4=351.哈夫曼树的有关概念二、哈夫曼树及其应用⑤哈夫曼树的定义:设有n个叶子结点的二叉树,其第i个叶子结点的权值为wi(i=1,2,3,...n),且第i个叶子结点的路径长度为li,则使WPL=∑wi*li最小的二叉树称为“最优二叉树”或称为“哈夫曼树”。i=1nn2.哈夫曼树的求解过程二、哈夫曼树及其应用①问题:已知n个叶子的权值为{w1,w2,...wn},构造一棵最优二叉树。2.哈夫曼树的求解过程二、哈夫曼树及其应用②方法:步

6、骤1:构造一个具有n棵二叉树的森林F={T1,T2,......,Tn},其中Ti是只有一个根结点且根结点的权值为wi的二叉树。步骤2:在F中选取两棵其根结点的权值最小的二叉树,从F中删除这两棵树,并以这两棵二叉树为左右子树构造一棵新的二叉树添加到F中,该新的二叉树的根结点的权值为其左右孩子二叉树的根结点的权值之和。步骤3:判断F中是否只有唯一的一棵二叉树。若是,则求解过程结束;否则,转步骤2。2.哈夫曼树的求解过程二、哈夫曼树及其应用③实例:已知有5个叶子结点的权值分别为:5,15,40,30,10;试画出一棵相应的哈夫曼树。a40b30c5d10e15152

7、.哈夫曼树的求解过程二、哈夫曼树及其应用③实例:已知有5个叶子结点的权值分别为:5,15,40,30,10;试画出一棵相应的哈夫曼树。a40b30c5d10e15152.哈夫曼树的求解过程二、哈夫曼树及其应用③实例:已知有5个叶子结点的权值分别为:5,15,40,30,10;试画出一棵相应的哈夫曼树。a40b30c5d10e1515302.哈夫曼树的求解过程二、哈夫曼树及其应用③实例:已知有5个叶子结点的权值分别为:5,15,40,30,10;试画出一棵相应的哈夫曼树。a40b30c5d10e151530602.哈夫曼树的求解过程二、哈夫曼树及其应用③实例:已知

8、有5个叶子结点的权值分别

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。