哈夫曼树的概念以及构造(共2页).docx
《哈夫曼树的概念以及构造(共2页).docx》由会员分享,可在线阅读,更多相关《哈夫曼树的概念以及构造(共2页).docx(2页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上哈夫曼树(最优二叉树)的概念以及构造哈夫曼树产生的背景在实际生活和生产应用中,我们往往会遇到综合比较一系列的离散量的问题;比如说车站根据包裹的重量以及旅途的长短来确定携带行李的价格,或者我们根据一定的重量范围来给一箱铁球进行分类。这一类问题的解决思路是:1、 根据实际需要划分出分类的标准;2、 按一定的顺序(算法)将实际的数据归到相应的类别里。一般情况下,我们所确定的分类标准并不能保证每一类的数据量是平均分配的;也就是说,由于每一类数据出现的概率不同,造成当采用不同的算法时所需的运算次数的不同。当然,在实际生产生活中,我们更希望得到一种最快,最简洁同时也不会产生歧义的
2、算法。在这个背景下,哈夫曼树以及哈夫曼算法应运而生。准备概念森林:森林由n(n=2)个二叉树组成,它的遍历可以归结为二叉树的遍历,即以其中一棵二叉树的根结点为森林的“根结点”,之后每一个二叉树的根结点都依次相连,由此组成了一个大的二叉树森林向二叉树的转化。路径和路径的长度:从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称作路径长度。对于一个二叉树,其在第n层上的结点到根结点的路径长度为n-1。结点的权:根据应用的需要给树的结点赋的权值。结点的带权路径长度:从根结点到该结点的路径长度与该几点权的乘积。树的带权路径长度(WPL):树中所有叶子的带权路径长度之和。哈
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼树 概念 以及 构造
限制150内