数据结构算法之树的应用.ppt

该【数据结构算法之树的应用 】是由【7489238】上传分享，文档一共【37】页，该文档可以免费在线阅读，需要了解更多关于【数据结构算法之树的应用 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。树的应用
CLICK TO ADD TITLE
单/击/此/处/添/加/副/标/题
汇报人姓名
二叉树遍历的应用
01
查找数据元素
单击此处添加文本具体内容
02
求二叉树的高度
单击此处添加文本具体内容
03
求叶子结点数
单击此处添加文本具体内容
一、问题的提出(判断树)
设有100个学生某门课程的考试成绩的分布如下表所示：
学生成绩数据分布情况表
*问题：现在要编写程序依次根据每个学生的成绩打印出该学生的成绩等级。
分数
0~59
60~69
70~79
80~89
90~100
学生比例数





学生成绩数据分布情况表
分数
0~59
60~69
70~79
80~89
90~100
学生比例数





方法1：
a<60
打印"bad"
yes
a<70
no
打印"pass"
yes
a<80
no
打印"general"
yes
a<90
no
打印"good"
yes
打印"excellent"
no
5%的学生
15%的学生
40%的学生
30%的学生
10%的学生
共做315次比较
读取一个学生成绩→a
循环一百次
学生成绩数据分布情况表
分数
0~59
60~69
70~79
80~89
90~100
学生比例数





方法2：
a<80
打印"bad"
yes
a<90
no
yes
no
a<70
yes
no
a<60
yes
no
打印“good"
打印"excellent"
打印"pass"
打印"general"
5%的学生
15%的学生
40%的学生
30%的学生
10%的学生
共做220次比较
读取一个学生成绩→a
循环一百次
思考：如何找到一棵最优的判断树使得编写出来的程序的运行时间是最高效的？
哈夫曼树的有关概念
哈夫曼树及其应用
①结点的路径长度：
从根结点沿某条路径到某结点途中所经历的边的条数称为该结点的路径长度。
②树的路径长度：
从根结点到每一个叶子结点的路径长度之和。
④树的带权路径长度(WPL)：
树中所有叶子结点的带权路径长度之和称为树的带权路径长度。
③结点的带权路径长度：
某结点的路径长度与该结点上的权值的乘积称为该结点的带权路径长度。
二、哈夫曼树及其应用

实例：已知某二叉树的四个叶子结点 a,b,c,d分别带权7，5，2，4，则可构造出有如下几种不同形式的二叉树：
a
a
a
7
7
7
b
5
b
5
c
2
d
4
c
2
d
4
b
5
c
2
d
4
树的带权路径长度为：
WPL=2*7+2*5+2*2+2*4=36
树的带权路径长度为：
WPL=2*4+3*7+3*5+1*2=46
树的带权路径长度为：
WPL=1*7+2*5+3*2+3*4=35
哈夫曼树的定义：
设有n个叶子结点的二叉树，其第i个叶子结点的权值为wi(i=1,2,3,...n),且第i个叶子结点的路径长度为li ,则使
WPL=∑wi*li最小的二叉树称为“最优
二叉树”或称为“哈夫曼树”。
i=1
1
2
3
n
4
二、哈夫曼树及其应用
哈夫曼树及其应用
01
问题：
02
已知n个叶子的权值为{w1,w2,...wn}，构造一棵最优二叉树。
03
哈夫曼树的求解过程