《数据结构[Python语言描述]》教案第12课树和二叉树（6.4-6.5）.docx

《《数据结构[Python语言描述]》教案第12课树和二叉树（6.4-6.5）.docx》由会员分享，可在线阅读，更多相关《《数据结构[Python语言描述]》教案第12课树和二叉树（6.4-6.5）.docx（7页珍藏版）》请在优知文库上搜索。

1、课题第12课树和二叉树(6.4-6.5)课时2课时(90min)教学目标知识目标：(1)掌握哈夫曼树的构造方法及哈夫曼编码(2)掌握树的存储结构,以及树、森林和二叉树的转换方法(3)掌握树和森林的遍历方法技能目标：能利用哈夫曼树解决编码问题素质目标：培养勇于探索、知难而进、追求卓越的创新精神教学重难点教学重点：哈夫曼树的构造方法及哈夫曼编码，树、森林和二叉树的转换方法，树和森林的遍历方法教学睚点：树、森林和二叉树的转换方法，树和森林的遍历方法教学方法问答法、讨论法、i并授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假

2、人员及原因问题导入【教师】提出以下问题：什么是哈夫曼树？【学生】思考、举手回答传授新知【教师】通过学生的回答引入要讲的知识，介绍哈夫曼树的构造方法及哈夫曼编码，树、森林和二叉树的转换方法，树和森林的遍历方法6.4哈夫曼树6.4.1 哈夫曼树的定义哈夫曼树是一种特殊的二叉树.在介绍它的定义之前，首先了解如下基本术语.(】)路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。(2)路径长度：从树中一个结点到另一个结点所经过的分支数目。(3)树的路径长度：从树的根结点到树中所有结点的路径长度之和。(4)结点的权：在实际应用中，人们为树的每个结点赋予的一个具有某种实际意义的数值称为该结

3、点的权。(5)结点的带权路径长度：从树的根结点到该结点之间的路径长度与该结点的权的乘积。(6)树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作WPL=1以北=I其中，为叶子结点个数，Wk为第个叶子结点的权值，/%为根到第Z个叶子结点的路径长度.哈夫曼树又称为最优二叉树，是n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树。6.4.2哈夫曼树的构造哈夫曼树的构造方法如下.(1)用给定的。个权值以物,陶对应/7个结点，构成具有棵二叉树的森林F=T1,T2Tn,其中每棵二叉树T”只有一个权为W的根结点，其左、右子树均为空.(2)从森林中选取两棵根结点权值最小的二叉树，分别作为左

4、、右子树构造一棵新的二叉树，且新的二叉树的根结点的权值为其左、右子树根结点的权值之和。(3)从森林中删除(2)中选取的两棵二叉树，并把新构成的二叉树加入森林中.(4)重复(2)和(3)的操作，直到森林中只含有一棵二叉树，这棵二叉树即为哈夫曼树。【教师】用多媒体展示“哈夫曼树的构造过程”图(详见教材)，并介绍哈夫曼树的构造过程【提示】在构造哈夫曼树的过程中，两棵二叉树作为根结点的左、右子树是任意的，因此构造出来的哈夫曼树可能不是唯一的，但是其带权路径长度一定是相同的。6.4.3哈夫曼编码为防止编码有二义性，要求每一个字符的编码都不能是另一个字符编码的前缀，这种编码称为前缀编码。利用哈夫曼树可以设

5、计出最优的前缀编码，具体方法如下。(1)以每个字符的出现频率为权值构造一棵哈夫曼树。(2)将哈夫曼树中的每一条左分支标记为O,每一条右分支标记为I0(3双根结点到每个叶子结点所经过的路径分支组成的。和】的序列构成了该结点对应字符的编码，这个编码称为哈夫曼编码。【教师】用多媒体展示“哈夫曼编码”图(详见教材)，并介绍哈夫曼编码过程【教师】讲解实例6-4(详见教材)6.5树和森林【教师】随机邀请学生回答以下问题树和森林的区别是什么？【学生】聆听、思考、回答森林是若干棵互不相交的树的集合，而树去掉根结点就变成了森林，森林加上根结点就变成了树。6.5.1 树的存储结构1 双亲表示法双亲表示法是用一组连

6、续的存储空间来存储树中的结点，结点的存储顺序为从上到下、同一层从左到右。在每个结点中设置一个指针Parent,用于指示其双亲结点的位置。【教师】用多媒体展示“树及其双亲表示的存储结构”图，并介绍该存储结构dataparent其中，dala域用于存储结点的数据信息；Parent域用于存储其双亲结点的地址。由于根结点没有双亲结点，故将其Parent域设置为-1。双亲表示法结点的定义如下。classNode:definit(self,data,parent):self.data=data#data域self.parent=parent#parent【高手点拨】双亲表示法利用了树的每个结点（根结点除外

7、）只有唯一双亲结点的性质，在这种存储结构中，求某个结点的双亲结点非常容易，但是求某个结点的孩子结点则需要遍历整棵树。2 .孩子表示法孩子表示法是将树中每个结点的孩子结点排列起来，构成一个线性表。由于每个结点的孩子结点个数不确定，所以通常采用单链表作为存储结构，称为孩子链表。n个结点即有n个孩子链表（叶子结点的孩子链表为空表）。孩子表示法中包含两种结点，一种是表头数组的表头结点，也就是双亲结点（见图6-35）,另一种是孩子链表的孩子结点（见图6-36）.datafirstchildchildnext图635表头结点结构图6-36孩子结点结构其中，表头结点的data域用于存储结点的数据信息；fir

8、stchild域用于存储该结点的孩子链表的头指针。孩子结点的Child域用于存储结点在表头数组中的位置；next域用于存储指向表头结点的下一个孩子结点的地址。孩子表示法表头结点的定义如下。classPNode:def_init_(self,data):self.data=dataself.firstchild=None#data域#firstchild域孩子表示法孩子结点的定义如下。classCNode:def_init_(self,child):self.child=childself.next=None#child域#next域【教师】用多媒体展示“树及其孩子表示的存储结构”图（详见教材）

9、，并介绍该存储结构【提示】孩子表示法便于杳找树中结点的孩子结点.若将双亲表示法和孩子表示法结合起来，那么实现树的各种操作都将变得非常容易。3 .孩子兄弟表示法孩子兄弟表示法又称二叉链表表示法，即以二叉链表作为树的存储结构。二叉链表中的每个结点由3个域组成。firstchilddatarightsib其中，firstchild域用于存储结点的第一个孩子结点的地址；data域用于存储结点的数据信息Jrightsib域用于存储结点的右兄弟结点。孩子兄弟表示法结点的定义如下。classNode:def_init_（self,data）:self.data=data#data域self.firstchi

10、ld=None#firstchild.# rightsib 域self.rightsib=None【教师】用多媒体展示“树及其孩子兄弟表示的存储结构”图(详见教材)，并介绍该存储结构6.5.2树、森林和二叉树的转换1 .礴专换为二叉树将一棵树转换为二叉树的步骤如下。(1)加线：在树中的兄弟结点之间加一条连线.(2)抹线：对树中的每个结点，除了其最左孩子结点外，抹掉其与其他孩子结点之间的“双亲T子”关系的连线。(3)旋转：以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。【教师】用多媒体展示“树转换为二叉树”图(详见教材)，并介绍树转换为二叉树的过程【知识库】从物理结构上看，树

11、的孩子兄弟存储结构与二叉树的二叉链表存储结构是相同的，只是它们的含义不同。通过树的孩子兄弟表示法，可以将树转换为二叉树。(详见教材)【高手点拨】将一棵树转换为二叉树的加线过程，就是将树中的兄弟关系转换为二叉树中的双亲一右孩子”关系。通过以上转换可以看出，树中任意一个结点都对应于二叉树中的一个结点。(详见教材)2 .森林转换为二叉树【教师】随机邀请学生回答以下问题结合树转换为二叉树的步骤，思考森林如何转换为二叉树？【学生】聆听、思考、回答森林转换为二叉树，实际上就是将森林中的若干棵树转换为相应的二叉树，然后再将这若干棵二叉树转换为一棵二叉树。将森林转换为二叉树的步骤如下。3)转换：将森林中的每一

12、棵树转换为相应的二叉树。(2)调整：第一棵树不动，从第二棵树开始，依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子结点，直到所有的二叉树连在一起成为一棵二叉树。【教师】用多媒体展示“森林转换为二叉树”图(详见教材)，并介绍森林转换为二叉树的过程【提示】通过以上转换可以看出，当有m(ml)棵树的森林转换为二叉树时，除第一棵树外，其余各树均变为二叉树中根结点的右子树。3 .二叉树转换为树或森林将一棵二叉树转换为树或森林的步骤如下。(1)加线：若某个结点是其双亲结点的左孩子结点，则把该结点的右孩子结点、右孩子的右孩子结点都与该结点的双亲结点用线连接起来。(2)抹线：抹掉原二叉树中所有双亲结点

13、与右孩子结点的连线。(3)整理：整理得到的树或森林，使之结构层次分明。*【教师】用多媒体展示“二叉树转换为树”图(详见教材)，并介绍二叉树转换为树的过程6.5.3树和森林的遍历1 .树的遍历树的遍历方法有两种，一种是先根遍历；另一种是后根遍历。对于非空树，先根遍历的步骤如下.(1)访问根结点。(2)依次先根遍历根结点的每一棵子树。对于非空树，后根遍历的步骤如下。(1)依次后根遍历根结点的每一棵子树。(2)访问根结点。2.森林的遍历森林的遍历方法有两种，一种是先序遍历；另一种是中序遍历。对于非空森林，先序遍历的步骤如下。(1)访问森林中第一棵树的根结点。(2)先根遍历第一棵树的根结点的子树森林。

14、(3)先根遍历除第一棵树之外的其余树构成的森林。对于非空森林，中序遍历的步骤如下。(1)后根遍历森林中第一棵树的根结点的子树森林。(2)访问第一棵树的根结点。(3)后根遍历除第一棵树之外的其余树构成的森林。【提示】森林的先序遍历和中序遍历分别与其对应二叉树的先序遍历和中序遍历相同，因此可以用相应二叉树的遍历序列来验证森林的遍历序列。另外，树可以看作只有一棵树的森林，所以树的先根遍历和后根遍历与森林的先序遍历和中序遍历相同。【学生】聆听、思考、理解、记录任务实施任务一利用树解决8枚硬币的真假判定问题【教师】描述问题，分析问题，要求学生完成任务【问题描述】有8枚硬币，其中有I枚是假币，假币的外观与

15、真币完全相同，但重量不同，可能轻，也可能重。若以天平为称量工具，如何用最少的称量次数挑选出假币，并确定假币的重量比真币轻还是重.【问题分析】解决这个问题需要经过一系列的判断，这些判断构成了树结构，这样的树称为判定树。将8枚硬币分别用4、氏c、4、e、工g、表示。从8枚硬币中任取6枚(假设是a、b、c、d、。和/),在天平两端各放3枚进行膜。假设&b、C这3枚硬币放在天平的一端，久&/这3枚硬币放在天平的另一端，可能出现如下3种阴结果。(详见教材)【学生】按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点哈夫曼树的定义、构造和编码树的存储结构树、森林和二叉树的转换树和森林的遍历【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的剩余练习。【学生】完成课后任务教学反思