lecture24(金根树及其应用).pptVIP

信息科学技术学院 * 离散数学 Lecture 25 主讲：陈义明 信息科学技术学院 */22 信息科学技术学院 有向树 如果一个有向图在不考虑边的方向时是一棵树，那么，这个图称为有向树。 */22 信息科学技术学院 学习内容 1 根树及其分类 2 最优树与哈夫曼算法 3 最佳前缀码 */22 信息科学技术学院 学习目标 理解根树及其相关概念。 掌握最优树的定义及哈夫曼算法。 掌握最佳前缀码的定义及求法。 */22 信息科学技术学院 根树的定义 根树: 有一个顶点入度为0, 其余的入度均为1的非平凡的有向树。 树根: 有向树中入度为0的顶点 树叶: 有向树中入度为1, 出度为0的顶点 内点: 有向树中入度为1, 出度大于0的顶点 分支点: 树根与内点的总称 */22 信息科学技术学院 根树的定义 顶点v的层数: 从树根到v的通路长度，记作 l(?) 树高: 有向树中顶点的最大层数。记作h(?) */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 */22 信息科学技术学院 家族树 设v为根树的一个顶点且不是树根, 称v及其所有后代的导出子图为以v为根的根子树。 将根树每一层上的顶点规定次序后称作有序树。 把根树看作一棵家族树: 若顶点a邻接到顶点b, 则称b是a的儿子, a是b的父亲。 若b和c为同一个顶点的儿子, 则称b和c是兄弟。 若a?b且a可达b, 则称a是b的祖先, b是a的后代。 */22 信息科学技术学院 根树的分类 r元树:根树的每个分支点至多有r个儿子 r元正则树: 根树的每个分支点恰有r个儿子 r元完全正则树: 所有树叶层数相同的r元正则树 r元有序树: 有序的r元树 r元正则有序树: 有序的r元正则树 r元完全正则有序树: 有序的r元完全正则树 */22 信息科学技术学院 最优2元树 定义7.10 设2元树T有t片树叶v1, v2, …, vt, 树叶的权分别为 w1, w2, …, wt, 称 为T的权, 记作W(T), 其中 l(vi)是vi的层数. 在所有有t片树叶, 带权w1, w2, …, wt 的 2元 树中, 权最小的2元树称为最优2元树。 例如 1 3 4 5 6 1 3 4 5 6 1 3 4 5 6 W(T1)=47 W(T2)=54 W(T3)=43 */22 信息科学技术学院 求最优2元树的算法 哈夫曼(Huffman)算法 给定实数w1, w2, …, wt ① 作t片树叶, 分别以w1, w2, …, wt为权 ② 在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点, 添加一个新分支点, 以这2个顶点为儿子, 其权等于这2个儿子的权之和 ③ 重复②, 直到只有1个入度为0 的顶点为止 W(T)等于所有分支点的权之和。 */22 信息科学技术学院 实例 例1 求以1,3,4,5,6为权的最优2元树, 并计算它的权 解 1 3 4 (a) 1 3 4 4 8 (b) 1 3 4 4 5 6 8 11 (c) 1 3 4 4 5 6 8 11 19 (d) W(T)=4+8+11+19=42 */22 信息科学技术学院 实例 */22 信息科学技术学院 通信编码 从编码通信的过程来看，编码要满足什么要求？ 使总编码串最短。 要能正确地译码。 设{H，E，L，O}使用编码{ 0, 10, 010, 1010 }即 H=0, E=10, L=010, O=1010,则HELLO=0100100101010，能否正确译码？ */22 信息科学技术学院 最佳前缀码 定义7.11 设?=?1?2…?n-1?n是长度为n的符号串, ?1?2…?k 称作?的长度为k的前缀, k=1,2,…,n?1. 若非空字符串?1, ?2, …, ?m中任何两个互不为前缀, 则称 {?1, ?2, …, ?m}为前缀码 只出现两个符号(如0与1)的前缀码称作2元前缀码 例如 { 0, 10, 110, 1111 }, { 10, 01, 001, 110 }是2元前缀码 { 0, 10, 010, 1010 } 不是前缀码 */22 信息科学技术学院 用2元树产生2元前缀码的方法 对每个分支点, 若关联2条边, 则给左边标0, 右边标1; 若只 关联1条边, 则可以给它标0(看作左边), 也可以标1(看作右 边). 将从树根到每一片树叶的通路上标的数字组成的字 符串记在树叶处, 所得的字符串构成一