lecture24(根树及其应用)课件

1、lecture24(根树及其应用)1离散数学离散数学Lecture 25主讲：陈义明主讲：陈义明信息科学技术学院信息科学技术学院2lecture24(根树及其应用根树及其应用)有向树有向树如果一个有向图在不考虑边的方向时是一棵树，那么，这如果一个有向图在不考虑边的方向时是一棵树，那么，这个图称为有向树。个图称为有向树。 3lecture24(根树及其应用根树及其应用)学习内容学习内容1 根树及其分类根树及其分类2 最优树与哈夫曼算法最优树与哈夫曼算法3 最佳前缀码最佳前缀码4lecture24(根树及其应用根树及其应用)学习目标学习目标n理解根树及其相关概念。理解根树及其相关概念。n掌握最优树

2、的定义及哈夫曼算法。掌握最优树的定义及哈夫曼算法。n掌握最佳前缀码的定义及求法。掌握最佳前缀码的定义及求法。5lecture24(根树及其应用根树及其应用)根树的定义根树的定义根树根树: 有一个顶点入度为有一个顶点入度为0, 其余的入度均为其余的入度均为1的非平凡的的非平凡的有向树。有向树。树根树根: 有向树中入度为有向树中入度为0的顶点的顶点树叶树叶: 有向树中入度为有向树中入度为1, 出度为出度为0的顶点的顶点内点内点: 有向树中入度为有向树中入度为1, 出度大于出度大于0的顶点的顶点分支点分支点: 树根与内点的总称树根与内点的总称6lecture24(根树及其应用根树及其应用)根树的定义

3、根树的定义顶点顶点v的层数的层数: 从树根到从树根到v的通路长的通路长度，记作度，记作 l( )树高树高: 有向树中顶点的最大层数。有向树中顶点的最大层数。记作记作h( )7lecture24(根树及其应用根树及其应用)实例实例右图中右图中 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. 树高为树高为48lecture24(根树及其应用根树及其应用)家族树家族树设设v为根树的一个顶点且不是树根为根树的一个顶点且不是树根, 称称v及其所有后代的导及

4、其所有后代的导出子图为以出子图为以v为根的为根的根子树。根子树。将根树每一层上的顶点规定次序后称作将根树每一层上的顶点规定次序后称作有序树。有序树。把根树看作一棵把根树看作一棵家族树家族树:若顶点若顶点a邻接到顶点邻接到顶点b, 则称则称b是是a的的儿子儿子, a是是b的的父亲。父亲。若若b和和c为同一个顶点的儿子为同一个顶点的儿子, 则称则称b和和c是是兄弟。兄弟。若若a b且且a可达可达b, 则称则称a是是b的的祖先祖先, b是是a的的后代。后代。9lecture24(根树及其应用根树及其应用)根树的分类根树的分类r元树元树:根树的每个分支点至多有根树的每个分支点至多有r个儿子个儿子r元正

5、则树元正则树: 根树的每个分支点恰有根树的每个分支点恰有r个儿子个儿子r元完全正则树元完全正则树: 所有树叶层数相同的所有树叶层数相同的r元正则树元正则树r元有序树元有序树: 有序的有序的r元树元树r元正则有序树元正则有序树: 有序的有序的r元正则树元正则树r元完全正则有序树元完全正则有序树: 有序的有序的r元完全正则树元完全正则树10lecture24(根树及其应用根树及其应用)最优最优2元树元树定义定义7.10 设设2元树元树T有有t片树叶片树叶v1, v2, , vt, 树叶的权分别为树叶的权分别为w1, w2, , wt, 称称 为为T的权的权, 记作记作W(T), 其中其中l(vi)

6、是是vi的层数的层数. 在所有有在所有有t片树叶片树叶, 带权带权w1, w2, , wt 的的 2元元树中树中, 权最小的权最小的2元树称为元树称为最优最优2元树。元树。)()(1itiivlwtW 例如例如134 561345613456W(T1)=47W(T2)=54W(T3)=4311lecture24(根树及其应用根树及其应用)求最优求最优2元树的算法元树的算法哈夫曼哈夫曼(Huffman)算法算法给定实数给定实数w1, w2, , wt 作作t片树叶片树叶, 分别以分别以w1, w2, , wt为权为权 在所有入度为在所有入度为0的顶点的顶点(不一定是树叶不一定是树叶)中选出两个权

7、最小中选出两个权最小的顶点的顶点, 添加一个新分支点添加一个新分支点, 以这以这2个顶点为儿子个顶点为儿子, 其权等于其权等于这这2个儿子的权之和个儿子的权之和 重复重复, 直到只有直到只有1个入度为个入度为0 的顶点为止的顶点为止 W(T)等于所有分支点的权之和。等于所有分支点的权之和。12lecture24(根树及其应用根树及其应用)实例实例例例1 求以求以1,3,4,5,6为权的最优为权的最优2元树元树, 并计算它的权并计算它的权解解134(a)13448(b)134456811(c)1344 5681119(d)W(T)=4+8+11+19=4213lecture24(根树及其应用根树

8、及其应用)实例实例14lecture24(根树及其应用根树及其应用)通信编码通信编码从编码通信的过程来看，编码要满足什么要求？从编码通信的过程来看，编码要满足什么要求？使总编码串最短。使总编码串最短。要能正确地译码。要能正确地译码。设设H，E，L，O使用编码使用编码 0, 10, 010, 1010 即即 H=0, E=10, L=010, O=1010,则则HELLO=10，能否正确译码？，能否正确译码？15lecture24(根树及其应用根树及其应用)最佳前缀码最佳前缀码定义定义7.11 设设 = 1 2 n-1 n是长度为是长度为n的符号串的符号串, 1 2 k称作称作 的长度为的长度为

9、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 不是前缀码不是前缀码16lecture24(根树及其应用根树及其应用)用用2元树产生元树产生2元前缀码的方法元前缀码的方法对每个分支点对每个分支点, 若关联若关联2条边条边, 则给左边标则给左边标0,

10、右边标右边标1; 若只若只关联关联1条边条边, 则可以给它标则可以给它标0(看作左边看作左边), 也可以标也可以标1(看作右看作右边边). 将从树根到每一片树叶的通路上标的数字组成的字将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处符串记在树叶处, 所得的字符串构成一个前缀码所得的字符串构成一个前缀码.例如例如前缀码前缀码 00, 11, 011, 0100 17lecture24(根树及其应用根树及其应用)通信编码通信编码从编码通信的过程来看，编码要满足什么要求？从编码通信的过程来看，编码要满足什么要求？使总编码串最短。使总编码串最短。要能正确地译码。要能正确地译码。设设H，E，L

11、，O使用编码使用编码00, 0100, 011,11 ，则，则HELLO的编码长度为多少？的编码长度为多少？18lecture24(根树及其应用根树及其应用)实例实例例例2 在通信中在通信中,设八进制数字出现的频率设八进制数字出现的频率(%)如下如下: 0: 25, 1: 20, 2: 15, 3: 10, 4: 10, 5: 10, 6: 5, 7: 5采用采用2元前缀码元前缀码, 求传输数字最少的求传输数字最少的2元前缀码元前缀码 (称作称作最佳最佳前缀码前缀码), 并求传输并求传输100个按上述比例出现的八进制数字需个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的要多少个二进

12、制数字？若用等长的 (长为长为3) 的码字传输需的码字传输需要多少个二进制数字要多少个二进制数字?解解 用用Huffman算法求以频率算法求以频率(乘以乘以100)为权的最优为权的最优2元树元树. 这里这里w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.19lecture24(根树及其应用根树及其应用)实例实例(续续)编码编码:0-01 1-112-0013-1004-1015-00016-000007-00001传传100个按比例出现的八进制数字需个按比例出现的八进制数字需W(T)=285个二进制数个二进制数字字, 用等长码用等长码(长为长为3)需

13、要用需要用 300个数字个数字.lecture24(根树及其应用根树及其应用)5.6 树树-根树根树 例题例题 汉字汉字“一地在要工上是中国同和的有一地在要工上是中国同和的有”出现频率依次为出现频率依次为“2,3,5,7,11,13,17,19,23,29,31,37,41”，为这些汉字设计编码。译出，为这些汉字设计编码。译出“10101111”对应的汉字对应的汉字 。 lecture24(根树及其应用根树及其应用)5.6 树树-根树根树原则原则：左小右大、组合优先、左0右1、不足补0 编码编码：一、地、在101010、要10100、工0100、上0101、是1011、中1110、国1111、同011、和100、的110、有00lecture24(根树及其应用根树及其应用)5.6 树树-根树根树原则：原则：左小右大、组合优先、左左小右大、组合优先、左0右右1、不足补、不足补0 译码译码：10101111，每次从根结点开始，每次从根结点开始，100(和和)0101(上上) ，110(的的)，100(和和)，1011(是是)，11