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

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

1、课题第10课树和二叉树(6.1-6.2)课时2课时(90min)教学目标知识目标：(1)理解树的定义、基本术语和基本操作(2)理解二叉树的定义、基本操作和性质(3)掌握二叉树的两种存储结构技能目标：能使用二叉树解决实际问题素质目标：增强自主学习、t办作学习、探究学习的意识教学重难点教学重点：树的基本操作、二叉树的基本操作和性质、二叉树的两种存储结构教学睚点：二叉树基本操归口两种存储结构教学方法问答法、讨论法、i并授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：什么是树形结构？其

2、多应用于哪些方面？【学生】思考、举手回答传授新知【教师】通过学生的回答引入要讲的知识，介绍树的定义、基本术语和基本操作，二叉树的定义、基本操作和性质，二叉树的两种存储结构6.1数概述树(Iree)是n(n0)个结点的有限集合，当n=0时称为空树.任意一棵非空树T均满足如下条件。(1)有且只有一个称为根(root)的结点，它无前驱结点。(2)当n1时,除根结点外的其余n-1个结点可以分为m(m0)互不相交的有限集合TuT2、.T*其中每个集合Ti(Ii0)个结点的有限集合，当n=0时称为空二叉树。任意一棵非空二叉树T均满足如下条件。(1)有且只有一个称为根(root)的结点，它无前驱结点。(2)

3、当nI时，除根结点外的其余n-l个结点可以分为两个互不相交的子集和T2,分别称为T的左子树和右子树，其中T1和T2本身也是二叉树。二叉树的基本形态有5种。【教师】用多媒体展示“二叉树的基本形态”图片(详见教材)，并介绍各种基本形态的特点(1)空二叉树，即二叉树有0个结点。(2)单结点二叉树，即二叉树只有一个根结点.(3)右子树为空的二叉树，即二叉树只有左子树。(4)左子树为空的二叉树，即二叉树艮有右子树。(5)左、右子树均不为空的二叉树，即二叉树既有左子树又有右子树。【提示】非空二叉树中的任意一个结点只可以有0、1或2个孩子结点，即二叉树中不存在度大于2的结点.2 .满二叉树在一棵二叉树中，如

4、果所有非叶子结点都有左子树和右子树，并且所有叶子结点都在二叉树的最后一层，则称该二叉树为满二叉树。【教师】用多媒体展示“满二叉树”图片（详见教材），并介绍满二叉树的节点特点由图可以看出，深度为4的满二叉树共有24-l=15个结点。由此可知，满二叉树也可以这样定义，即一棵深度为h且有2a-1个结点的二叉树称为满二叉树。3,完全二叉树在一棵二叉树中，如果其所有结点所在位置的编号分别与同深度的满二叉树相应位置的结点编号一一对应，则称该二叉树为完全二叉树。【教师】用多媒体展示“完全二叉树”非完全二叉树”图片（详见教材），并介绍完全二叉树的节点特点完全二叉树也可以这样定义，即一棵深度为h的二叉树，除第h

5、层外，其余各层（1rl）的结点数都达到最大值，且第人层的结点从左三右连续排列。6.2.2 二叉树的性质二叉树具有如下5个性质.（1胜质1：对于任何一棵非空二叉树T岩叶子结点数为,度为2的结点数为n2厕%=%+L（2）性质2：二叉树的第i（il）层最多有2-1个结点.（3）性质3：深度为h（hl）的二叉树最多有2-1个结点。（4）性质4：具有n个结点的完全二叉树的深度为Lbg2+1。（LloSin表示小于等于,0g2n的最大整数）（5）性质5：对于具有n个结点的完全二叉树，按照从上到下、同一层从左到右的JI顺序对其所有结点进行连续编号，则结点i（l1,则该结点的双亲结点为J/2。（/2J表示小于

6、等于2的最大整数）若27n,则该结点无左孩子结点；若2in,则该结点的左孩子结点为2/；若2/+1n,则该结点无右孩子结点；若2+l7,则该结点的右孩子结点为2/+Ie*【教师】讲解实例6-1、6-2（详见教材）6.2.3 二叉树的基本操作*【教师】用多媒体展示“二叉树的基本操作的定义”表（详见教材），并介绍二叉树的基本操作6.2.4 二叉树的存储结构二叉树是一种非线性结构，其存储结构有顺序存储和链式存储两种。1.二叉树的顺序存储二叉树的顺序存储是指用一组地址连续的存储单元存储二叉树中的结点，通常用一维数组来描述。为了在存储结构中反映出二叉树中各结点之间的逻辑关系，须将二叉树中的结点值按照一定

7、的规律存储到一维数组中。*【教师】用多媒体展示“完全二叉树的顺序存储结构”“普通二叉树的顺序存储结构”图（详见教材），并介绍各自顺序存储特点可以按照层序编号将二叉树中的所有结点值顺序存储到一维数组中，即二叉树编号为/的结点值存储到一维数组中下标为M的单元中.对于普通二叉树，必须先将其补全为完全二叉树，然后再按照完全二叉树的形式进行存储。也就是说，将普通二叉树中的每个结点与完全二叉树中的结点相对应，同时将普通二叉树中不存在的结点位置用0”填充.【教师】随机邀请学生回答以下问题满二叉树和完全二叉树为什么更适合采用顺序存储结构？【学生】聆听、思考、回答综上所述,满二叉树和完全二叉树更适合采用M页序存

8、储结构，这样既能节省存储空间，又能利用数组下标确定结点在二叉树中的位置及结点之间的逻辑关系。2.二叉树的链式存储二叉树的链式存储是指用链表存储二叉树。在二叉树的链式存储结构中，每个结点由3个域组成。!childdatarchild其中,左子树域(Ichild)用于存储左孩子结点的地址；数据域(data)用于存储结点的数据信息；右子树域(rchild)用于存储右孩子结点的地址。二叉树的链式存储结构中结点的定义如下。classBTNode:#二叉树结点类definit_(self,data):#构造方法self.data=data#data域self.!child=None#IChiId域self

9、.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,画出该二叉树。【学生】按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点树的定义、基本术语和基本操作二叉树的定义：二叉树、满二叉树二叉树的性质和基本操作二叉树的存储结构：二叉树的顺序存储、二叉树的链式存储【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的相关练习.【学生】完成课后任务教学反思