【精品数据结构】哈夫曼树及其应用.ppt

《【精品数据结构】哈夫曼树及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、在此幻灯片插入公司的徽标从“插入”菜单选择图片找到徽标文件单击“确定”重新设置徽标大小单击徽标内任意位置。徽标外部出现的方框是“调整控点”使用这些重新设置对象大小如果在使用尺寸调整控点前按下shift键，则对象改变大小但维持原比例。DATA1065865姓名学号成绩班级李红976105995机97.6ABCDEFG数据结构2.5.3哈夫曼树及其应用1、哈夫曼树树的路径长度的概念：从一个结点到另一个结点之间的分支数目称为这对结点之间的路径长度。树的路径长度是从树的根到每一结点的路径长度之和。7/22/20212124536

2、7PL=0+1+1+2+2+2+2=10树的路径长度用PL表示。7/22/202131245367PL=0+1+1+2+2+2+2=101245C67PL=0+1+1+2+2+3+3=12树的路径长度用PL表示。7/22/20214结点带权的路径长度：从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中叶子结点带权路径长度之和。abcd7524WPL=7*2+5*2+2*2+4*2=367/22/20215树的带权路径长度记作：其中：Wk为树中每个叶子结点的权；Lk为每个叶子结点到根的路径长度。abcd7

3、524WPL=7*2+5*2+2*2+4*2=36WPL最小的二叉树就称作最优二叉树或哈夫曼树。7/22/20216abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35哈夫曼树（最优树）加权路径长度最小的二叉树就是哈夫曼树。公式：7/22/20217675cd(b)11b57cd(c)18a711cdb5624(d)abcd7524(a)2、哈夫曼树的构造例：给定权值{7，5，2，4}，构造哈夫

4、曼树。方法：（1）由原始数据生成森林；(2)在森林中选取两棵根结点权值最小的和次小的二叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。规定左子树根结点的权值小于右子树根结点的权值。（3）将新的二叉树加入到森林F中，去除原两棵权值最小的树；（4）重复2、3步骤，直至F中只剩一棵树为止。注意：参看书中P53的例子。7/22/202183、哈夫曼树的应用（1）判定树在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。例1将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的，可用图（a)二叉树

5、结构来实现。a<60a<70a<80a<90不及格中等良好优秀及格YNYNYNYN(a)输入10000个数据，则需进行31500次比较。7/22/20219分数0—5960—6970—7980—8990—99比例0.050.150.40.30.1070≤a≤80a<60及格中等良好80≤a<9060≤a<70不及格优秀YNYYYNNN(b)不及格Ya<90a<80a<70a<60优秀中等及格良好YNNN(c)YYY学生成绩分布不是均匀的情况：以比例数为权构造一棵哈夫曼树，如（b)判断树所示。再将每一比较框的两次比较改为一

6、次，可得到（c)判定树。输入10000个数据，仅需进行22000次比较。7/22/202110146833442200001111T;ACS各字符编码是T；ACS000110110111上述电文编码：11010111011101000011111000011000方法：（1）用{2，4，2，3，3}作为叶子结点的权值生成一棵哈夫曼树，并将对应权值wi的叶子结点注明对应的字符；（2）约定左分支表示字符“0”，右分支表示字符‘1’（3）从叶子结点开始，顺着双亲反推上去，直到根结点，路径上的‘0’或‘1’连接的序列就是结点对应

7、的字符的二进制编码的逆序。（2）哈夫曼编码-----利用哈夫曼树构造通讯中电文编码（前缀码）例2：要传输的电文是{CAS；CAT；SAT；AT}要传输的字符集是D={C，A，S，T，；}每个字符出现的频率是W={2，4，2，3，3}注意：编码的总长度恰好为哈夫曼树的带权路径长。7/22/20211111月1日上机作业：折半查找顺序查找选择排序快速排序7/22/2021122.6.1图的基本概念2.6图BACD63215顶点:图中的数据元素V表示顶点的非空有限集合。VR表示两个顶点之间关系的集合。7/22/202113图有

8、向图无向图在有向图中，表示从V1到V3的一条弧。V1为弧尾或初始点，V3为弧头或终端点。在无向图中，(V1，V3)表示V1和V3之间的一条边。V1V3V2V4V1V3V2V47/22/202114V1V3V2V4V1V3V2V4顶点集合V={V1，V2，V3，V4}弧的集合G={,