3、有向数及其应用 最优二元树.ppt

1,树,9.1 无向树及生成树9.2 根树及其应用,2,9.2 根树及其应用,有向树根树、树根、树叶、内点、分支点家族树、根子树、有序树r元树（r元有序树）r元正则树（r元有序正则树）r元完全正则树（r元有序完全正则树）最优2元树与Huffman算法,3,有向树的定义,有向树: 基图为无向树的有向图树根: 有向树中入度为0的顶点树叶: 有向树中入度为1, 出度为0的顶点内点: 有向树中入度为1, 出度大于0的顶点分支点: 树根与内点的总称顶点v的层数: 从树根到v的通路长度树高: 有向树中顶点的最大层数,4,根树的定义 : 有一个顶点入度为0, 其余的入度均为1的非平凡的有向树,根树的画法:树根放上方,省去所有有向边上的箭头如右图所示 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,,5,家族树,定义 把根树看作一棵家族树:(1) 若顶点 a 邻接到顶点 b, 则称 b 是 a 的儿子, a 是 b 的父亲;(2) 若b和c为同一个顶点的儿子, 则称b和c是兄弟;(3) 若ab且a可达b, 则称a是b的祖先, b是a的后代.设v为根树的一个顶点且不是树根, 称v及其所有后代的导出子图为以v为根的根子树.,6,根树的分类,r元树:根树的每个分支点至多有r个儿子r元正则树: 根树的每个分支点恰有r个儿子r元完全正则树: 树叶层数相同的r元正则树,7,最优2元树,,定义 设2元树T有t片树叶v1, v2, …, vt, 树叶的权分别 为w1, w2, …, wt, 称 为T的权, 记作 W(T), 其中l(vi)是vi的层数. 在所有有t片树叶, 带权 w1, w2, …, wt 的 2元树中, 权最小的2元树称为最优 2元树.,8,求最优树,Huffman算法:给定实数w1, w2, …, wt, ① 作t片树叶, 分别以w1, w2, …, wt为权.② 在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点, 添加一个新分支点, 以这2个顶点为儿子, 其权等于这2个儿子的权之和.③ 重复②, 直到只有1个入度为0 的顶点为止. W(T)等于所有分支点的权之和,9,实例,例 求带权为1, 1, 2, 3, 4, 5的最优树. 解题过程由下图给出，W(T)=38,10,前缀码,设 =12…n-1n是长度为n的符号串的前缀: 12…k , k=1,2,…,n-1 前缀码: {1, 2, …, m}, 其中1, 2, …, m为非空字符串, 且任何两个互不为前缀2元前缀码: 只出现两个符号(如0与1)的前缀码如 {0,10,110, 1111}, {10,01,001,110}是2元前缀码 {0,10,010, 1010} 不是前缀码,11,前缀码(续),一棵2元树产生一个二元前缀码:对每个分支点, 若关联2条边, 则给左边标0, 右边标1; 若只关联1条边, 则可以给它标0(看作左边), 也可以标1(看作右边). 将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处, 所得的字符串构成一个前缀码.如右图所示,,12,最佳前缀码,例 在通信中，设八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前缀码), 并求传输10n(n2)个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字?解 用Huffman算法求以频率(乘以100)为权的最优2元树. 这里 w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 最优2元树如图所示.,13,编码: 0---01 1---11 2---001 3---100 4---101 5---0001 6---00000 7---00001传100个按比例出现的八进制数字所需二进制数字的个数为 W(T)=285.传10n(n2)个所用二进制数字的个数为2.8510n, 而用等长码(长为3)需要用 310n个数字.,,。