欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > DOCX文档下载  

    《数据结构[Python语言描述]》教案第10课树和二叉树(6.1-6.2).docx

    • 资源ID:7016907       资源大小:28.40KB        全文页数:6页
    • 资源格式: DOCX        下载积分:5金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要5金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    《数据结构[Python语言描述]》教案第10课树和二叉树(6.1-6.2).docx

    课题第10课树和二叉树(6.1-6.2)课时2课时(90min)教学目标知识目标:(1)理解树的定义、基本术语和基本操作(2)理解二叉树的定义、基本操作和性质(3)掌握二叉树的两种存储结构技能目标:能使用二叉树解决实际问题素质目标:增强自主学习、t办作学习、探究学习的意识教学重难点教学重点:树的基本操作、二叉树的基本操作和性质、二叉树的两种存储结构教学睚点:二叉树基本操归口两种存储结构教学方法问答法、讨论法、i并授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题:什么是树形结构?其多应用于哪些方面?【学生】思考、举手回答传授新知【教师】通过学生的回答引入要讲的知识,介绍树的定义、基本术语和基本操作,二叉树的定义、基本操作和性质,二叉树的两种存储结构6.1数概述树(Iree)是n(n>0)个结点的有限集合,当n=0时称为空树.任意一棵非空树T均满足如下条件。(1)有且只有一个称为根(root)的结点,它无前驱结点。(2)当n>1时,除根结点外的其余n-1个结点可以分为m(m>0)互不相交的有限集合TuT2、.T*其中每个集合Ti(I<i<m)本身又是一棵树,称为根结点的子树(subtree)*【教师】用多媒体展示“家庭成员关系的树形表示“图(详见教材),并介绍树的概念由图可以看出,这是一棵具有H个结点的树,即T=A,B,CJ.K其中,A是根结点,其余10个结点可以分为3个互不相交的集合,分别是Ti=B,E,FJ、T2=(C,GKT3=D,H,I,K).TuT2、T3本身也是一棵树,且都称为根结点A的子树。T1的根结点为B,其余3个结点可以分为两个互不相交的集合,分别是TU=(EJ、T2=F)Tu和2本身也是一棵树(T12只有根结点),且都称为根结点B的子树。T”的根结点为E,其余结点J本身是一棵只有根结点的树,称为根结点E的子树。【提示】T2和T3也是根结点A的子树,其分析方法与Tl相同,此处不再赘述.感兴趣的读者可自行分析子树T2和T3.由此可见,树的定义是递归的。号【教师】随机邀请学生回答以下问题树具有什么特点?*【学生】聆听、思考、回答树具有如下两个特点。(1)除根结点外,其余结点有且只有一个前驱结点。(2)每个结点都可以有若干后继结点.÷【教师】用多媒体展示“树的表示方法”图(详见教材),并介绍文氏图、凹入表示法、广义表表示法的概念(1)文氏图表示法是以嵌套集合的形式表示树。每棵树对应一个集合,集合内包含根结点和子树的集合,同一个根结点下的各子树对应的集合是不能相交的。(2)凹入表示法是以类似图书目录的形式表示树。每棵树的根结点对应一个条形,子树的根结点对应较短的条形,且树的根结点在上,子树的根结点在下。同一个根结点下的不同子树的根结点对应的条形长度相同。(3)广义表表示法是将根结点作为由所有子树组成的表的名字写在表的左边。6.1.2 树的基本术语)【教师】用多媒体展示“树的基本术语“表(详见教材),并介绍树的各种术语6.1.3 树的基本操作÷【教师】用多媒体展示“树的基本操作定义”表(详见教材),并介绍树的基本操作6.2二叉树概述÷【教师】随机邀请学生回答以下问题试概述二叉树的定义。÷【学生】聆听、思考、回答二叉树是一种特殊的树,它的每个结点最多有两棵子树,且子树有左右之分,其次序不能任意颠倒。6.2.1 二叉树的定义1 .二叉树二叉树是n(n>0)个结点的有限集合,当n=0时称为空二叉树。任意一棵非空二叉树T均满足如下条件。(1)有且只有一个称为根(root)的结点,它无前驱结点。(2)当n>I时,除根结点外的其余n-l个结点可以分为两个互不相交的子集和T2,分别称为T的左子树和右子树,其中T1和T2本身也是二叉树。二叉树的基本形态有5种。÷【教师】用多媒体展示“二叉树的基本形态”图片(详见教材),并介绍各种基本形态的特点(1)空二叉树,即二叉树有0个结点。(2)单结点二叉树,即二叉树只有一个根结点.(3)右子树为空的二叉树,即二叉树只有左子树。(4)左子树为空的二叉树,即二叉树艮有右子树。(5)左、右子树均不为空的二叉树,即二叉树既有左子树又有右子树。【提示】非空二叉树中的任意一个结点只可以有0、1或2个孩子结点,即二叉树中不存在度大于2的结点.2 .满二叉树在一棵二叉树中,如果所有非叶子结点都有左子树和右子树,并且所有叶子结点都在二叉树的最后一层,则称该二叉树为满二叉树。【教师】用多媒体展示“满二叉树”图片(详见教材),并介绍满二叉树的节点特点由图可以看出,深度为4的满二叉树共有24-l=15个结点。由此可知,满二叉树也可以这样定义,即一棵深度为h且有2a-1个结点的二叉树称为满二叉树。3,完全二叉树在一棵二叉树中,如果其所有结点所在位置的编号分别与同深度的满二叉树相应位置的结点编号一一对应,则称该二叉树为完全二叉树。÷【教师】用多媒体展示“完全二叉树”非完全二叉树”图片(详见教材),并介绍完全二叉树的节点特点完全二叉树也可以这样定义,即一棵深度为h的二叉树,除第h层外,其余各层(1rl)的结点数都达到最大值,且第人层的结点从左三右连续排列。6.2.2 二叉树的性质二叉树具有如下5个性质.(1胜质1:对于任何一棵非空二叉树T岩叶子结点数为,度为2的结点数为n2厕%=%+L(2)性质2:二叉树的第i(i>l)层最多有2-1个结点.(3)性质3:深度为h(h>l)的二叉树最多有2-1个结点。(4)性质4:具有n个结点的完全二叉树的深度为Lbg2+1。(LloSin表示小于等于,0g2n的最大整数)(5)性质5:对于具有n个结点的完全二叉树,按照从上到下、同一层从左到右的JI顺序对其所有结点进行连续编号,则结点i(l<in)具有如下特点。若上1,则该结点是根结点,无双亲结点;若/>1,则该结点的双亲结点为J/2。(/2J表示小于等于2的最大整数)若27>n,则该结点无左孩子结点;若2in,则该结点的左孩子结点为2/;若2/+1>n,则该结点无右孩子结点;若2+l<7,则该结点的右孩子结点为2/+Ie*【教师】讲解实例6-1、6-2(详见教材)6.2.3 二叉树的基本操作*【教师】用多媒体展示“二叉树的基本操作的定义”表(详见教材),并介绍二叉树的基本操作6.2.4 二叉树的存储结构二叉树是一种非线性结构,其存储结构有顺序存储和链式存储两种。1.二叉树的顺序存储二叉树的顺序存储是指用一组地址连续的存储单元存储二叉树中的结点,通常用一维数组来描述。为了在存储结构中反映出二叉树中各结点之间的逻辑关系,须将二叉树中的结点值按照一定的规律存储到一维数组中。*【教师】用多媒体展示“完全二叉树的顺序存储结构”“普通二叉树的顺序存储结构”图(详见教材),并介绍各自顺序存储特点可以按照层序编号将二叉树中的所有结点值顺序存储到一维数组中,即二叉树编号为/的结点值存储到一维数组中下标为M的单元中.对于普通二叉树,必须先将其补全为完全二叉树,然后再按照完全二叉树的形式进行存储。也就是说,将普通二叉树中的每个结点与完全二叉树中的结点相对应,同时将普通二叉树中不存在的结点位置用"0”填充.÷【教师】随机邀请学生回答以下问题满二叉树和完全二叉树为什么更适合采用顺序存储结构?÷【学生】聆听、思考、回答综上所述,满二叉树和完全二叉树更适合采用M页序存储结构,这样既能节省存储空间,又能利用数组下标确定结点在二叉树中的位置及结点之间的逻辑关系。2.二叉树的链式存储二叉树的链式存储是指用链表存储二叉树。在二叉树的链式存储结构中,每个结点由3个域组成。!childdatarchild其中,左子树域(Ichild)用于存储左孩子结点的地址;数据域(data)用于存储结点的数据信息;右子树域(rchild)用于存储右孩子结点的地址。二叉树的链式存储结构中结点的定义如下。classBTNode:#二叉树结点类definit_(self,data):#构造方法self.data=data#data域self.!child=None#IChiId域self.rchild=None#rchild域采用以上结点结构形成的二叉树的链式存储结构称为二叉链表,链表的头指针指向二叉树的根结点。÷【教师】用多媒体展示“二叉树对应的二叉链表”图(详见教材),并介绍二叉链表为了便于找到结点的双亲结点,可以在每个结点中增加一个指向其双亲结点的指针域parent,其结构如图所示。parent!childdatarchild采用这种结点结构形成的二叉树的链式存储结构称为三叉链表。÷【教师】用多媒体展示“三叉链表”图(详见教材),并介绍三叉链表【学生】聆听、思考、理解、记录任务一应用题(1)(2)【教师】描述问题,要求学生完成任务【问题描述】(1)已知二叉树的先序遍历序列为A、B、C、D、E、F,中序遍历序列为C、B、D、A、E、F,任务实施画出该二叉树。(2)已知二叉树的后序遍历序列为G、D、B、E、FxC.A,中序遍历序列为D、G、B、A、E、C、F,画出该二叉树。【学生】按照要求完成任务,如遇问题可询问老师【教师】巡堂辅导,及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点树的定义、基本术语和基本操作二叉树的定义:二叉树、满二叉树二叉树的性质和基本操作二叉树的存储结构:二叉树的顺序存储、二叉树的链式存储【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的相关练习.【学生】完成课后任务教学反思

    注意事项

    本文(《数据结构[Python语言描述]》教案第10课树和二叉树(6.1-6.2).docx)为本站会员(李司机)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开