离散数学-教案 -第7章7.2 7.2 根树和7.3 应用

课堂教学设计24章节（专题）第7章树计划学时2课题（内容）7.2根树和7.3应用教育教学目的1.掌握有向树、根数、有序树等概念2.掌握根数与有序树的分类3.掌握最优2叉树及其算法4.思政目标：根树具有明确的层级结构，从根节点到各分支节点，每个节点都承担着特定的角色与功能，如同社会分工中不同岗位的责任。在讲解家族树、组织架构树等应用实例时，引导学生理解在集体和社会中，每个人都应明确自身责任，发挥好自己的作用，层级间相互协作才能保障整体有序运行，从而强化学生的责任担当意识和团队协作精神，树立正确的职业价值观。教学重点及难点1.重点：Huffman算法、根树2.难点：Huffman、根树的应用教学方法及手段1.讲授法2.互动式教学3.多媒体辅助教学教学互动环节设计1.课程回顾导入新课（无向树及生成树）2.启发式提问引发课堂讨论（最优2叉树的解法）课后总结与反思7.2根数及其应用有向树的定义有向树：一个有向图D，如果省略去有向边的方向所得无向图为一棵无向树，则称D为有向树。一棵平凡的有向树，如果有一个顶点的入度为0，其余顶点的入度均为1，则称此有向树为根数。入度为0的顶点称为树根，入度为1、出度为0的顶点称为树叶，入度为1、出度大于0的顶点称为内点，内点和树根统称为分支点。顶点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为根的根子树.思政目标：根树具有明确的层级结构，从根节点到各分支节点，每个节点都承担着特定的角色与功能，如同社会分工中不同岗位的责任。在讲解家族树、组织架构树等应用实例时，引导学生理解在集体和社会中，每个人都应明确自身责任，发挥好自己的作用，层级间相互协作才能保障整体有序运行，从而强化学生的责任担当意识和团队协作精神，树立正确的职业价值观。根树的分类有序树:将根树同层上的顶点规定次序r叉树:根树的每个分支点至多有r个儿子r叉正则树:根树的每个分支点恰有r个儿子r叉完全正则树:树叶层数相同的r元正则树r叉有序树:有序的r叉树r叉正则有序树:有序的r叉正则树r叉完全正则有序树:有序的r叉完全正则树最优二叉树定义设定义设2叉树T有t片树叶v1,v2,…,vt,树叶的权分别为w1,w2，wt,称T的权,其中l(vi)是vi的层数.在所有权为w1,w2,…,wt的t片树叶的2叉树中,权最小的2叉树称为最优2叉树.例如：求最优二叉树的算法HuffmanHuffman算法:给定实数w1,w2,…,wt,①作t片树叶,分别以w1,w2,…,wt为权。②在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点,添加一个新分支点,以这2个顶点为儿子,其权等于这2个儿子的权之和。③重复②,直到只有1个入度为0的顶点为止。W(T)等于所有分支点的权之和。实例：求权为1,3,4,5,6的最优树.解：上图中给出了用Huffman算法求最优2叉树的计算过程。图e是最优2叉树T，W(T)=42，根据这个计算结果，图c所示