lecture24(根树及其应用).ppt
《lecture24(根树及其应用).ppt》由会员分享,可在线阅读,更多相关《lecture24(根树及其应用).ppt(25页珍藏版)》请在三一文库上搜索。
1、1,离散数学 Lecture 25 主讲:陈义明 信息科学技术学院,2/22,信息科学技术学院,有向树,如果一个有向图在不考虑边的方向时是一棵树,那么,这个图称为有向树。,3/22,信息科学技术学院,学习内容,1 根树及其分类 2 最优树与哈夫曼算法 3 最佳前缀码,4/22,信息科学技术学院,学习目标,理解根树及其相关概念。 掌握最优树的定义及哈夫曼算法。 掌握最佳前缀码的定义及求法。,5/22,信息科学技术学院,根树的定义,根树: 有一个顶点入度为0, 其余的入度均为1的非平凡的有向树。 树根: 有向树中入度为0的顶点 树叶: 有向树中入度为1, 出度为0的顶点 内点: 有向树中入度为1,
2、 出度大于0的顶点 分支点: 树根与内点的总称,6/22,信息科学技术学院,根树的定义,顶点v的层数: 从树根到v的通路长度,记作 l() 树高: 有向树中顶点的最大层数。记作h(),7/22,信息科学技术学院,实例,右图中 a是树根 b,e,f,h,i是树叶 c,d,g是内点 a,c,d,g是分支点 a为0层;1层有b,c; 2层有d,e,f; 3层有g,h; 4层有i. 树高为4,8/22,信息科学技术学院,家族树,设v为根树的一个顶点且不是树根, 称v及其所有后代的导出子图为以v为根的根子树。 将根树每一层上的顶点规定次序后称作有序树。,把根树看作一棵家族树: 若顶点a邻接到顶点b, 则
3、称b是a的儿子, a是b的父亲。 若b和c为同一个顶点的儿子, 则称b和c是兄弟。 若ab且a可达b, 则称a是b的祖先, b是a的后代。,9/22,信息科学技术学院,根树的分类,r元树:根树的每个分支点至多有r个儿子 r元正则树: 根树的每个分支点恰有r个儿子 r元完全正则树: 所有树叶层数相同的r元正则树 r元有序树: 有序的r元树 r元正则有序树: 有序的r元正则树 r元完全正则有序树: 有序的r元完全正则树,10/22,信息科学技术学院,最优2元树,定义7.10 设2元树T有t片树叶v1, v2, , vt, 树叶的权分别为 w1, w2, , wt, 称 为T的权, 记作W(T),
4、其中 l(vi)是vi的层数. 在所有有t片树叶, 带权w1, w2, , wt 的 2元 树中, 权最小的2元树称为最优2元树。,11/22,信息科学技术学院,求最优2元树的算法,哈夫曼(Huffman)算法 给定实数w1, w2, , wt 作t片树叶, 分别以w1, w2, , wt为权 在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点, 添加一个新分支点, 以这2个顶点为儿子, 其权等于这2个儿子的权之和 重复, 直到只有1个入度为0 的顶点为止 W(T)等于所有分支点的权之和。,12/22,信息科学技术学院,实例,例1 求以1,3,4,5,6为权的最优2元树, 并计算它的权
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- lecture24 及其 应用
链接地址:https://www.31doc.com/p-2145794.html