13哈夫曼树_图文

夫曼编码Р1、课题导入Р问题:请编制一个将百分制转换成五级分制的程序Рif (score<60) b=“bad”;?else if (score<70) b=“pass”;? else if (score<80) b=“general”;? else if (score<90) b=“good”; ? else b=“excellent”;Р图aР如果反复使用,且每次输入量很大,就应该考虑时间问题Р语句频度Р在实际生活中,学生的成绩在五个等级上的分布是不均匀的。假如其分布规律如下表所示:Р怎样使大部分的数据经过较少的比较次数得出结果并且使总的比较次数最少呢?Р图aР哈夫曼树Р路径:? 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。Р2、相关概念Р路径长度:? 路径上的分支数目。Р树的路径长度:? 树中每个结点的路径长度之和。?(完全二叉树是路径长度最短的二叉树)Р结点的路径长度:? 从根结点到该结点的路径上分支? 的数目。РAРBРDРEРCР如:B、C、D、E路径长度分别为:1、1、1、2Р如:树的路径长度为:1+1+1+2Р结点的权值:?对结点赋予的一个有意义的数值量。Р结点的带权的路径长度:? 该结点到根结点之间的路径长度?与该结点权值的乘积。Р如:E的带权路径长度=5*2РAРBРDРEРCР2Р3Р4Р5Р树的带权路径长度:? 树中所有叶子结点的带权路径长度之和РWPL=РåР=РnРkРkРkРlРwР1Р第k个叶子的权值Р从根结点到第k个叶子的路径长度РAРBРDРEРCР2Р3Р4Р5Р如:WPL=2*1+3*1+5*2Р在所有含 n 个叶子结点、并带相同权值的 m 叉树中,必存在一棵其带权路径长度取最小值的树,称为“最优树”。Р最优二叉树Р给定一组具有确定权值的叶子结点,带权路径长度最小的二叉树,称为最优二叉树。Р赫夫曼树/哈夫曼树/霍夫曼