资源描述：
《9.2 根树及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、山东政法学院教案模版授课时间第十八周第1次课授课章节8.4平面图任课教师及职称唐新华讲师教学方法与手段板书和电子课件结合课时安排3课时使用教材和主要参考书1、教材：耿素云等，离散数学，清华大学出版社，20082.参考书左孝琳、李为槛、刘永才，离散数学（上海科技文献版）2006教学与目的要求：掌握根树，n叉树完全n叉树，二叉树完全二叉树的概念；会求完全二叉树。掌握求最优树的Huffman算法教学重点、难点:重点：根树定义，根树的分类，最优树，前缀码与最佳前缀码，Huffman算法难点：根树的分类，最优树，Huffman算法教学内容:9.2
2、根树及其应用一、本节主要内容有向树根树、树根、树叶、内点、分支点家族树、根子树、有序树r元树（r元有序树）r元正则树（r元有序正则树）r元完全正则树（r元有序完全正则树）最优2元树与Huffman算法前缀吗与最佳前缀吗中序行遍法、前序行遍法、后续行遍法波兰符号法与逆波兰符号法二、教学内容有向树与根树的定义有向树:基图为无向树的有向图根树:有一个顶点入度为0,其余的入度均为1的非平凡的有向树树根:有向树中入度为0的顶点树叶:有向树中入度为1,出度为0的顶点内点:有向树中入度为1,出度大于0的顶点山东政法学院教案模版分支点:树根与内点的总称
3、顶点v的层数:从树根到v的通路长度树高:有向树中顶点的最大层数根树(续)根树的画法:树根放上方,省去所有有向边上的箭头如右图所示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家族树定义把根树看作一棵家族树:(1)若顶点a邻接到顶点b,则称b是a的儿子,a是b的父亲;(2)若b和c为同一个顶点的儿子,则称b和c是兄弟;(3)若a¹b且a可达b,则称a是b的祖先,b是a的后代.设v为根树的一个顶点且不是树根,称v及其所有后代的导出子图为以v为根
4、的根子树.根树的分类有序树:将根树同层上的顶点规定次序r元树:根树的每个分支点至多有r个儿子r元正则树:根树的每个分支点恰有r个儿子r元完全正则树:树叶层数相同的r元正则树r元有序树:有序的r元树r元正则有序树:有序的r元正则树r元完全正则有序树:有序的r元完全正则树最优2元树求最优树Huffman算法:给定实数w1,w2,…,wt,①作t片树叶,分别以w1,w2,…,wt为权.②在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点,添加一个新分支点,以这2个顶点为儿子,其权等于这2个儿子的权之和.③重复②,直到只有1个入度为0的
5、顶点为止.山东政法学院教案模版W(T)等于所有分支点的权之和实例例求带权为1,1,2,3,4,5的最优树.解题过程由下图给出，W(T)=38前缀码设a=a1a2…an-1an是长度为n的符号串a的前缀:a1a2…ak,k=1,2,…,n-1前缀码:{b1,b2,…,bm},其中b1,b2,…,bm为非空字符串,且任何两个互不为前缀2元前缀码:只出现两个符号(如0与1)的前缀码如{0,10,110,1111},{10,01,001,110}是2元前缀码{0,10,010,1010}不是前缀码前缀码(续)一棵2元树产生一个二元前缀码:对每个
6、分支点,若关联2条边,则给左边标0,右边标1;若只关联1条边,则可以给它标0(看作左边),也可以标1(看作右边).将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处,所得的字符串构成一个前缀码.如右图所示最佳前缀码例在通信中，设八进制数字出现的频率如下：0：25%1：20%2：15%3：10%4：10%5：10%6：5%7：5%采用2元前缀码,求传输数字最少的2元前缀码(称作最佳前缀码),并求传输10n(n³2)个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的(长为3)的码字传输需要多少个二进制数字?解用Huffma
7、n算法求以频率(乘以100)为权的最优2元树.这里w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.最优2元树如图所示.山东政法学院教案模版编码:0---011---112---0013---1004---1015---00016---000007---00001传100个按比例出现的八进制数字所需二进制数字的个数为W(T)=285.传10n(n³2)个所用二进制数字的个数为2.85´10n,而用等长码(长为3)需要用3´10n个数字.波兰符号法与逆波兰符号法行遍(周游)根树T:对T的每个顶点访
8、问且仅访问一次.行遍2元有序正则树的方式：①中序行遍法:左子树、根、右子树②前序行遍法:根、左子树、右子树③后序行遍法:左子树、右子树、根例如,对图所示根树按中序、前序、后序行遍法访问结果分别为：ba(fd
