数据结构（Python Java）（微课版） 教案 -单元5树

教案课程名称数据结构与算法设计课程代码总学时64课程负责人任课教师

单元教案授课日期年月日—月日授课地点授课班级班级人数教学单元单元5树教学时数10教学目标AOB1:掌握计算机程序设计中的线性表、栈、队列、树和图的逻辑结构与存储结构。了解递归的数据逻辑组织结构；AOB2:掌握计算机程序设计中的线性表、栈、队列、树、图的数据增、删、改、查操作运算。了解递归的处理算法。掌握选择与排序处理算法；AOB3:掌握对算法的科学分析方法。BOB1:能根据实际问题中的数据特性选择适当的数据结构；BOB2:设计出适当的算法和程序。EOB1:掌握使用搜索引擎、论坛、帮助文档、课外书籍等方法解决学习中出现的问题；EOB2:能主动阅读书后拓展知识并进行实验验证；EOB3:能独立分析解决问题，能把自己的想法用代码实现。教学方式混合式教学评价方式课堂考勤（20%），课堂活动参与程度（20%）线上单元测试（40%）线下课堂教学参与程度（20%）教学资源1.算法与数据结构（Java语言描述），陈媛，清华大学大学出版社2.电脑50台（含eclips）;3.网络学习资源：/forums/ST_Arithmetic：课程平台网址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea单元教学设计第一次课（2学时）教学内容5.1普通树定义：树是由n（n≥0）个结点组成的有限集合，当n＝0时称为空树；否则，在任一非空树中必有一个称为根的结点；当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm；其中每一个集合本身又是一棵树，称为根的子树特点：非空树中至少有一个根结点；树中各子树是互不相交的集合树的表示树的基本术语结点：树中的元素，包括数据项及若干指向子树的分支结点的度：结点拥有的子树数叶子：度为0的结点，也叫终端结点分支结点：度不为0的结点，也叫非终端结点内部结点：除根结点之外，分支结点也称为内部结点孩子：结点子树的根称为该结点的孩子双亲：孩子结点的上层结点叫该结点的双亲兄弟：同一双亲的孩子之间互成为兄弟祖先：从根到该结点所经分支上的所有结点子孙：子树中的任一结点都是该结点的子孙树的度：一棵树中最大的结点度数结点的层次：从根结点算起，根为第一层，它的孩子为第二层……堂兄弟：其双亲在同一层的结点互称为堂兄弟深度：树中结点的最大层次数有序树：树中结点的各子树从左至右是有序的，最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子森林：m棵互不相交的树的集合树的逻辑特征纵向关系：祖先与子孙是纵向次序；任一结点都可以有零个或多个直接后继结点；但至多只有一个直接前趋结点；叶结点无后继；根结点无前趋横向关系有序树中，若k1和k2是兄弟，且k1在k2的左边，则k1的任一子孙都在k2的任一子孙的左边教学重点树的基本术语教学难点无教学流程教学环节教师活动学生活动讲评和考勤（5分钟）1.平台发布任务2.考勤1.考勤讲授（60分钟）1.树的定义（10分钟）2.树的表示（10分钟）3.树的基本术语（30分钟）4.树的逻辑特征（10分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动课堂练习（20分钟）1.树形结构（5分钟）2.树的基本术语（15分钟）1.认真思考2.积极回答问题总结与发布课后任务（5分钟）1.总结课堂内容以及在练习过程中出现的，问题。2.布置课后任务1.思考教师总结2.记录课后任务第二次课（2学时）教学内容二叉树定义：二叉树是结点的有限集合，或者是空树，或者由一个根结点和两棵二叉子树构成。左子树，右子树，子树不相交特点：每个结点至多有二棵子树；不存在度大于2的结点；子树有左、右之分，次序不能任意颠倒满二叉树深度为k的满二叉树，有2k-1个结点；2k-1是深度为K的二叉树所具有的最大结点个数特点：每层上的结点数都达到最大值；只有度为0的结点和度为2的结点；每个结点均有两棵高度相同的子树；叶子结点都在树的最下面一层上完全二叉树叶子结点只出现在最低两层上；对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次为L或L+1；除最低层外，每一层上的结点数均达到最大值；在最低层上只缺少右边的若干结点(也可不缺)。二叉树的性质性质1：在二叉树第i层上至多有2i-1个结点(i≥1)证明：当i=1时，只有一个根结点。显然，2i-1＝20＝１是对的。假设对所有的j(1≤j﹤i)，命题成立。即第j层上至多有2j-1个结点，那么可以证明j=i时命题成立。归纳假设：第i-1层上至多有2i-2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i-2＝2i-1。性质2：深度为k的二叉树至多有2k-１个结点(k≥1)证明：由性质１可见，深度为k的二叉树的最大结点数为：性质3：对任意二叉树T，如果其终端结点数为n0，度为2的结点数为n2,则n0=n2+1。证明：二叉树中结点总数为：n=n0+n1+n2 (5-1)二叉树的分支数为：n1+2*n2 (5-2)因此，结点总数为：n=n1+2*n2+1由(5-1)、(5-2)两式可得：n0=n2+1性质5：对一棵有n个结点的完全二叉树的结点按层序号编号(从第1层到log2n+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：如果i=1，则结点i是根结点，无双亲，否则，其双亲结点为：i/2如果2i>n，则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1二叉树的存储顺序存储：将任意二叉树“修补”成完全二叉树；利用顺序表对数据元素进行存储；原二叉树中空缺的结点在数组中相应单元置空。链式存储：二叉链表：结点包含3个域：数据域和指向左、右子树的指针域二叉树的遍历遍历：按一定的规则和次序走遍二叉树的所有结点；使每个结点都被访问一次，且只被访问一次，对结点进行各种操作遍历二叉树的目的：遍历是对数据进行操作的基础；得到二叉树中各结点的一种线性顺序；使非线性的二叉树线性化，简化有关的运算和处理先序遍历，中序遍历，后序遍历线索二叉树线索：指向前驱或后继结点的指针称为线索线索二叉树：加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树教学重点二叉树的遍历教学难点二叉树的性质教学流程教学环节教师活动学生活动考勤（5分钟）1.考勤1.考勤讲授（60分钟）1.二叉树树的定义（10分钟）2.二叉树的性质（20分钟）3.二叉树的存储（10分钟）4.二叉树的遍历（20分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动课堂练习（20分钟）1.完全二叉树（5分钟）2.二叉树的遍历（15分钟）1.认真思考2.积极回答问题总结与发布课后任务（5分钟）1.总结本次课程内容；2.布置课后任务1.思考教师总结，2.记录教师的任务要求并在课后完成。第三次课（2学时）教学内容技能训练-二叉树遍历1.创建二叉树结点类2.建立链式存储二叉树，结构如图。3.实现先序遍历方法。4.实现中序遍历方法。5.实现后序遍历方法。6.测试代码，核验结果。教学重点二叉树遍历的代码实现教学难点二叉树遍历的代码实现教学流程教学环节教师活动学生活动考勤（5分钟）1.考勤1.考勤技能训练（80分钟）1.布置技能训练任务（5分钟）2.在技能训练过程中巡视并启发学生解决遇到的问题。1.独立完成老师下发的课堂练习2.在遇到问题时与同学讨论。总结与发布课后任务（5分钟）1.总结本次课程内容；2.布置课后任务1.思考教师总结，2.记录教师的任务要求并在课后完成。第四次课（2学时）教学内容5.3树与二叉树树的存储结构二叉树与树的相互转换树转二叉树①加线：在兄弟之间加一连线②抹线：对每个结点，除了其第一孩子外，去除其与其余孩子之间的关系③旋转：以树的根结点为轴心，将整棵树顺时针转45°二叉树转树①加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来②抹线：抹掉原二叉树中双亲与右孩子之间的连线③调整：将结点按层次排列，形成树结构森林转二叉树①将各棵树分别转换成二叉树②将每棵树的根结点用线相连③以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构二叉树转森林①抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树②还原：将孤立的二叉树还原成树树的遍历先序遍历(与对应的二叉树先序遍历序列一致)。若树非空，则：访问根结点；依次先序遍历根的各个子树。后序遍历(与对应的二叉树中序遍历序列一致)。若树非空，则：依次后序遍历根的各个子树；访问根结点层次遍历：若树非空，访问根结点。若第1，…i(i≥1)层结点已被访问，且第i+1层结点尚未访问，则从左到右依次访问第i+1层。教学重点树与二叉树转换，二叉树与森林转换教学难点树与二叉树转换，二叉树与森林转换教学流程教学环节教师活动学生活动考勤（5分钟）1.考勤1.考勤讲授（60分钟）1.树的存储结构（10分钟）2.树与二叉树转换（15分钟）3.二叉树与森林转换（20分钟）4.树的遍历（10分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动课堂练习（25分钟）1.树转二叉树（5分钟）2.二叉树转森林（5分钟）3.森林转二叉树（5分钟）4.树的遍历（10分钟）1.认真思考2.积极回答问题总结与发布课后任务（5分钟）1.总结本次课程内容；2.布置课后任务1.思考教师总结，2.记录教师的任务要求并在课后完成。第五次课（2学时）教学内容5.4哈夫曼树哈夫曼树相关概念路径：若树中存在某个结点序列k1,k2,…,kj，满足Ki是ki+1的双亲，则该结点序列是树上的一条路径，路径自上而下地经过了树上的每一条边路径长度：路径经过的边数，称为路径长度树的路径长度：从树根到树中每一个结点的路径长度之和，完全二叉树的路径长度最短结点的权：给树的结点赋以一定意义的数值，称为结点的权结点的带权路径长度：从树根到某结点的路径长度与该结点的权的积树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和哈夫曼树：由n个带权叶子结点构成的二叉树具有不同形态，其中带权路径长度（WPL）最小的二叉树，又叫最优二叉树或最佳判定树构造哈夫曼树的方法，哈夫曼算法：根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令其权值为分别wj；在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树；置新二叉树根结点权值为其左右子树根结点权值之和；在森林中删除这两棵树，并将新得到的二叉树加入森林中；重复上述步骤，直到只含一棵树为止，这棵树即哈夫曼树。哈夫曼树的应用最佳判定树哈夫曼编码电报通讯中，电文以二进制的0,1序列传送，发送端将电文中的字符转换成0,1的二进制序列，接收端将收到的0,1序列转换成对应的字符序列(译码)假定电文是英文，电文字符串由26个英文字母组成，需要编码的字符集是{A,B,C,D,…,Z}方法一：等长的二进制编码方法二：不等长的二进制编码前缀码：任一字符的编码，不能是其他字符的前缀。假设字符集D={d1,d2,d3,…,dn}，每个字符di的编码长度为li，每个字符di在电文中出现的次数是ci，则电文的总长度为:∑ci*li。每个字符di在电文中出现频度的概率是wi，每个字符di的编码长度为li，则电文的平均总长度为:∑wi*li寻找最优前缀码的方法用d1,d2,d3,…,dn作为叶子结点，用w1,w2,w3,…,wn作为叶子结点的权，构造最优二叉树，将树中每个结点的左分支置为0，右分支置为1，从根到叶子结点的一个标号序列，就是该叶子结点的编码。例：设组成电文的字符集D及其概率分布如下：D={a,b,c,d,e}

W={0.12,0.40,0.15,0.08,0.25}教学重点哈夫曼算法教学难点哈夫曼树的应用教学流程教学环节教师活动学生活动考勤（5分钟）1.考勤1.考勤讲授（65分钟）1.哈夫曼树的概念（10分钟）2.哈夫曼算法（20分钟）3.哈夫曼树的应用（35分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动课堂练习（15分钟）1.哈夫曼树的构造与相关计算（15分钟）1.认真思考2.积极回答问题总结与发布课后任务（5分钟）1.总结本次课程内容；2.布置课后任务1.思考教师总结，2.记录教师的任务要求并在课后完成。教学效果与反思根