4.2 二叉树的基本操作（教学设计）信息技术浙教版2019选择性必修1

4.2 二叉树的基本操作 1课时（教学设计） 年级 高二年级 授课时间 1课时 课题 4.2 二叉树的基本操作 教学 目标 1.了解树、子树、树的度、树的深度等概念。 2.了解二叉树、满二叉树、完全二叉树等概念。 3.通过具体任务的实践活动，体验用树型结构描述生活中蕴含树型结构的组织关系。 教学 重难点 重点： 二叉树的建立及遍历。 难点： 二叉树的前、中、后序三种遍历方式。 教学 准备 多媒体课件、多媒体教室 教学过程 教师活动 学生活动 新 课 导 入 一、课堂导入 1.通过两张图片(一张满二叉树，一张完全二叉树)展示进行问题导入:对于图中的两棵二叉树(一张满二叉树，一张完全二叉树)，如何组织、存储节点信息? 2.提示学生：可采用数组形式和链表形式存储节点信息。也可采用数组形式和链表形式，与学生一起模拟建树过程。 以图片方式，吸引学生参与课堂，让学生感知如何组织、存储节点信息。 设计意图:以图片对比导入形式引起学生兴趣，带着好奇心进入接下来的学习。 新 知 讲 授 二、二叉树的建立 1.数组实现 （1）完全二叉树： 从二叉树的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为n–1。 然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。 （2）非完全二叉树： 对于非完全二叉树，先将它补全为一棵完全二叉树，补上的节点及分支用虚线表示。 然后将补全后的完全二叉树，从它的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，第四章根节点的编号为0，最后一个节点的编号为n–1。 甲所示的一棵非完全二叉树补全为乙所示的完全二叉树 依次把完全二叉树中原二叉树的节点用一维数组的各个元素来表示，节点编号与数组的下标一一对应。 对于完全二叉树而言，一维数组的表示方式既简单又节省存储空间。但对于一般的二叉树来说，采用一维数组表示时，结构虽然简单，却容易造成存储空间的浪费。如上图甲所示，一个深度为k且只有k个节点的树需要如上图乙所示2k –1个节点的存储空间才能表示出来。 （3）探讨与讨论 2.链表实现 二叉树也可以采用链表来实现，用任意一组存储单元来存储二叉树的节点，用指向节点的指针来表示节点之间的关系。 由于二叉树的节点可能有两个孩子，即左孩子和右孩子，因此二叉树的节点至少需要3个域：一个数据域和两个指针域。两个指针域分别指向节点的左孩子和右孩子，这两个指针分别称为左指针和右指针，这样得到的链表也称为二叉链表。 3.拓展链接：二叉树的 list实现 二叉树节点可以看成一个三元组，元素是左、右子树和本节点数据。Python的list可以用于组合这样的三个元素。 下面介绍用list构造二叉树的方法。 （1）空树用None表示。 （2）非空二叉树用包含三个元素的列表[d,l,r]表示，其中：d表示根节点的元素，l和r是两棵子树，采用与整个二叉树同样结构的list表示。构更加复杂。 节点:树的二叉树 4.探讨与讨论 三、二叉树的遍历 概念：按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。 遍历方式： ①前序遍历（根-左-右） ②中序遍历（左-根-右） ③后序遍历（左-右-根 ④层序遍历 1.前序遍历（根左右） ※规则：若二叉树为空，则空操作返回；否则，先访问根节点，再访问左子树，最后访问右子树。 ※从右图中得到的前序遍历顺序为：A-B-D-H-E-C-F-I-G-J-K。 2.中序遍历（左根右） ※规则：若二叉树为空，则空操作返回；否则，先访问左子树，再访问根节点，最后访问右子树。 ※从右图中得到的中序遍历顺序为：D-H-B-E-A-I-F-C-J-G-K。 3.后序遍历（左右根） ※规则：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树，最后访问根节点。 ※从右图中得到的后序遍历顺序为：H-D-E-B-I-F-J-K-G-C-A。 4.层序遍历 ※规则：若二叉树为空，则空操作返回；否则，从根节点开始，自上而下，从左往右遍历。 如果选取其中一种遍历策略对二叉树进行遍历，对于二叉树的左右子树，也需遵守该遍历原则，即二叉树的任意一个局部都必须遵守该遍历原则。对一棵二叉树进行前序遍历时，根节点总是处于遍历序列之首；中序遍历时根节点位置居中，左子树的所有节点都在其左边，右子树所有节点都在其右边；后序遍历时根节点位置在最后，其所有节点都在其左边。 将右图中的二叉树实行中序遍历，将得到遍历序列：8–(3+2*6)/5+4，即人们平时习惯书写的数学表达式，也称为中缀表达式。 如果对图中二叉树实行后序遍历，那么得到遍历序列：8 3 2 6 *+ 5 / – 4 +，称为后缀表达式（也称逆波兰表达式）。 由于中缀表达式要将运算符放在两个操作数中间，并且在许多情况下为了确定运算顺序，括号是必不可少的。 而书写后缀表达式时，因为采用了运算符紧跟在两个操作数之后的方法，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右依序完成计算，并方便求得结果。 5.探讨与讨论 四、 二叉树遍历的Python程序实现 通过Python语言的程序实现来进一步体验二叉树的遍历机制 1.实践内容： 给出事先设计好的二叉树结构图，分别写出前序、中序和后序的遍历结果。通过输入Python程序分别建立、遍历二叉树，运行程序输出各种遍历结果，完成验证和体验。 2.实践步骤： ①给定右侧的二叉树 二叉树 ②写出该二叉树的前序、中序历的序列。 ③建立二叉树,代码如下： class Node: #建立二叉树 def __init__(self,value=None,left=None,right=None): self.value=value self.left=left #左子树 self.right=right #右子树 ④遍历二叉树，代码如下: def preTraverse(root): #前序遍历 if root==None: return print(root.value) preTraverse(root.left) preTraverse(root.right) def midTraverse(root): #中序遍历 if root==None: return midTraverse(root.left) print(root.value) midTraverse(root.right) def afterTraverse(root): #后序遍历 if root==None: return afterTraverse(root.left) afterTraverse(root.right) print(root.value) ⑤给定节点信息，输出遍历结果，代码如下: if __name__=='__main__': root=Node('A',Node('B',Node('D'),Node('E')), Node('C',right=Node('F',Node('G')))) print('前序遍历：') preTraverse(root) print('中序遍历：') midTraverse(root) print('后序遍历：') afterTraverse(root) 3.结果呈现: 基于上述实践任务，完成程序体验和结果验证。 ①运行程序，对比自己所写的遍历序列与程序输出的结果是否一致。 ②修改程序中的节点信息，输出表达式树的各种遍历序列，完成结果验证。 五、课堂练习 六、小 结 一、二叉树的建立 1.数组实现 （1）完全二叉树 （2）非完全二叉树 2.链表实现 3.拓展链接: 二叉树的list实现 二、二叉树的遍历 1.前序遍历 2.中序遍历 3.后序遍历 4.层序遍历 三、 二叉树遍历的Python程序实现 说明用数组法实现二叉树的方法，从两个方面：完全二叉树和非完全二叉树，图片对比结合讲解， 以知识条目的方式呈现完全二叉树和非完全二叉树的概念，并总结如何用数组实现。(意图:体现先学后教的理念。） 讲授基础理论，辅以图示，让学生对理论有更形象的了解，落实教学重点。 培养学生自主学习能力，并把学到的知识，并辅以实例，形式化的描述出来。 以讨论形式，现学现用，用树和数组结合解决生活中的问题。 学生回顾链表数据结构，模仿老师在学案上画出链表法建立二叉树。 设置难度适当的实践练习，加深学生对树如何用链表实现的理解，确定后续新知讲授的推进。 学生在老师的讲解下完成学案，实现四种二叉树遍历顺序 以图片对比的形式，从规则和图示结果来讲解四种二叉树的遍历。让学生循序渐进的理解。 知识点迁移。利用刚刚讲解的二叉树的四种遍历来解读数学表达式。 通过课堂练习，加深同学们对栈的理解。 通过主线总结，回顾本节课所说，并最后将整节课主线进行呈现，理解各环节间的关系。 课 堂 练 习 （有题有答案有解析） 1.二叉树也可以采用 来实现，用任意一组存储单元来存储二叉树的 ，用指向节点的指针来表示节点之间的关系。 2.二叉树的节点可能有两个孩子，即 和 ，因此二叉树的节点至少需要 个域： 和 。两个指针域分别指向节点的左孩子和右孩子，这两个指针分别称为 和 ，这样得到的链表也称为 。 3.二叉树节点可以看成一个 ，元素是 和 。 4.前序遍历的规则是：若二叉树为空，则空操作返回；否则，先访问根节点，再访问 ，最后访问 。 5.中序遍历的规则是：若二叉树为空，则空操作返回；否则，先访问 ，再访问根节点，最后访问 。 6.后序遍历的规则是：若二叉树为空，则空操作返回；否则，先访问 ，再访问 ，最后访问 。 7.层序遍历的规则：若二叉树为空，则空操作返回；否则，从 开始，自 而 ，从 往 遍历。 8.一棵二叉树的中序遍历序列为“dbgehafic"，后序遍历序列为“dghebifca"，则该二叉树的前序遍历序列是 。 9.一棵二叉树的前序遍历序列为“abdgecf'，中序遍历序列为“gdbeacf'，则该二叉树的后序遍历序列是 。 10.某二叉树如下图所示,请回答下列问题。 (1)该二叉树的深度为 。 (2)写出该二叉树的前序遍历、中序遍历和后序遍历。 前序遍历序列为: 。 中序遍历序列为: 。 后序遍历序列为: 。 答案： 1.链表、节点、 2.左孩子、右孩子、3、一个数据域、两个指针域、左指针、右指针、二叉链表 3.三元组、左.右子树、本节点数据 4.左子树右子树 5.左子树、右子树 6.左子树、右子树、根节点 7.根节点、上、下、左、右 8.【答案】abdeghcfi [解析]根据后序遍历序列为“dghebica”,中序遍历序列为“dbgehafe”可知,二叉树的根节点为a,在中序遍历序列中找到节点a,a节点前面部分为左子树的节点(dbgeh),a节点后面部分为右子树的节点(fe)。分析可得二叉树如下图所示: 根据前序遍历的规则容易得到该二叉树的前序遍历序列:abdeghcfi 。 9.【答案】gdebfca [解析]根据前序遍历序列abdgecf可知，该二叉树的根节点为a,然后在中序遍历序列中找到根节点a，根节点a前面部分为左子树的节点序列(gdbe)，后面部分为右子树的节点序列(cf)。然后对左子树进行处理，在前序遍历中找到左子树序列为bdge,可知左子树中的根节点为b,在中序遍历中找到b节点，可知gd为b节点的左子树，在前序遍历序列中d结点在g结点前面，因此b节点的左孩子节点为d,在中序遍历中的序列为gd,可知g为d节点的左孩子，用同样的方法再对右子树进行处理，这样就可以得到它的后序遍历的序列。 10.【答案】(1)5(2)abdhecfijkg、hdbeaifkcg、hdebikjfgca [解析]（1）本题主委考查的是二叉树的深度和遮历。(1)谊二叉树共有5层,根节点的深度为1,因此该二义树的深度为5。 (2)二叉树的前序遍历的規则是先访问穗节点,然后访问左子树,最后访问右子树,对左子树和右子树仍按上述规则访问,因此前序透历序列为“sbdhecfikg”；中序遍历的规则是先访问左子树,然后访问粮节点,最后访问右子树,因北中序遍历序列为“hdbcaifkcg”；后序遍历的规则是先访问左子树,然后访问右子树,最后访问根节点,因此后序遍历序列为"hdebikjfgca"。 课 堂 小 结 课堂小结 一、二叉树的建立 1. 数组实现 （1）完全二叉树 （2）非完全二叉树 2. 链表实现 3.拓展链接：二叉树的 list实现 二、二叉树的遍历 1. 前序遍历 2. 中序遍历 3. 后序遍历 作 业 设 计 1.某二叉树的树形结构如下图所示，后序遍历结果为“WUSVTR”，则该二叉树的前序遍历结果为（   ） A．RSTUVW B．RTSVUW C．RTSUWV D．RSUWTV 2.某二叉树的树形结构如第8题图所示，其后序遍历结果为“物技化数英语”，则中序遍历结果为() A.语数英物化技 B.物数技化语英 C.语数物化技英 D.化物技英数语 3.某二叉树的前序遍历为+*a-bc/df，中序遍历为a*b-c+d/f，下列说法正确的是（   ） A．该二叉树的叶子节点有2个 B．该二叉树为完全二叉树 C．该二叉树的后序遍历是abc-*df/+ D．若abcdf的值分别为3、2、5、6、3，则该表达式的运算结果为4 4.已知某二叉树的前序遍历结果为ABCDEF中序遍历结果为CBDAEF，则下列说法正确的是( ) A.其后序遍历结果为DCBFEA B.该二叉树为完全二叉树 C.该二叉树深度为3，叶子节点数为3 D.该二叉树用一维数组实现需要6个节点的存储空间才能表示 5.前序遍历与后序遍历得到的序列相同的二叉树为 A.只有左子树的二叉树 B.只有右子树的二叉树 C.满二叉树 D.只有根节点的二叉树 6.某二叉树对应的一维数组表示如图所示: 1 2 3 4 5 6 A B C D E 下列关于该二叉树的说法正确的是() A.该二叉树的度为3 B.该二叉树有2个叶子节点 C.该二叉树是一棵完全二叉树 D.该二叉树前序遍历结果为ABCDE 7.已知一棵完全二叉树共有5个节点，前序遍历为ABCDE，下列说法正确的是（   ） A.该二叉树的高度为3 B.该二叉树中只有1个度为2的节点 C.节点C的父节点是A D.该二叉树共有2个叶子节点 8.某二叉树从根节点开始，按从上到下、自左往右的顺序用A -G字母表示，若补全为完全二叉树后，用一维数组表示如图所示。 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G 下列关于该二叉树的说法，正确的是( ) A.该二叉树的深度为3 B.节点E的父节点是B C.该二叉树的中序遍历结果为BFDGACE D.该二叉树的叶子节点为D、E、F、G 9.已知一棵完全二叉树共有200个节点，下列说法正确的是() A.该完全二叉树的高度为7 B.该完全二叉树有99个叶子节点 C.该完全二叉树有100个度为2的节点 D.该完全二叉树有1个度为1的节点 10.已知某二叉树的后序遍历为GDBEHFCA，中序遍历为DGBAECHF，下列说法正确的是(） A.该二叉树中叶子节点有3个 B.该二叉树的前序遍历为ABDGCEHF C.该二叉树是一棵完全二叉树，树的高度为4 D.该二叉树中度为1的节点有2个 11.有一棵二叉树，如第下图所示，下列说法正确的是( ) A.此二叉树是完全二叉树 B.此二叉树的叶子节点有3个 C.此二叉树的后序遍历为F-D-B-E-C-A D.此二叉树用一维数组表示为['A’，’B，'E，'F’] 答案： 1.【答案】D [解析]后序遍历就是左子树--->右子树>根结点，根据这一规则，书写规则为 故其前序遍历序列为:RSUWTV，故选D。 2.【答案】B [解析]后续就是左子树--->右子树--->根结点，所以根节点为语，可排除选项AC，由于右子树只有一个节点，所以为英，可排除选项D。故选:B。 3.【答案】C [解析]本题主要考查二叉树的遍历。由前序遍历以及中序遍历，可画出该二叉树，由二叉树可知，该二叉树的叶子节点有5个;不是完全二叉树;该二叉树的后序遍历是abc-*df+;若abcdf的值分别为3、2、5、6、3，则该表达式的运算结果为3.0，故本题选C选项。 4.【答案】C [解析]某二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBDAEF，某其后序遍历结果为CBDFEA;该二叉树不是完全二叉树;该二叉树深度为3，叶子节点数为3，所以选项C符合题意。故选:C。 5.【答案】D [解析]根据前序遍历与后序遍历的规则可知,前序遍历与后序遍历得到的序列相同的二叉树,只有一种情况,就是只有根节点的二叉树。 6.【答案】B [解析]二叉树的度是指树中所有节点的度的最大值，此二叉树中节点的最大度为2，4错误;叶子节点是度为0的节点，这里只有节点D和B是叶子节点，有2个，B正确;完全二叉树是指除最后一层外，每一层上的节点数均达到最大值，且在最后一层上只缺少右边的若干节点，此二又树不符合完全二叉树定义，C错误;前序遍历应该是先访问根节点4，然后是左子树B，再是右子树C，D是B的子节点，E是D的子节点，所以前序遍历结果为ABDCE，D错误。故选:B。 7.【答案】A [解析]一棵完全二叉树共有5个节点，前序遍历为ABCDE，所以该二叉树的高度为3，该二叉树中只有2个度为2的节点;该二叉树共有3个叶子节点，所以选项A说法正确。故选:A。 8.【答案】C [解析]该二叉树如下，由图可知，该二又树的深度为4;节点卫的父节点是C;该二叉树的中序遍历结果为BFDGACE;该二叉树的叶子节点为E、F、G。 故选C。 9.【答案】D [解析]完全二叉树的性质可以知道:叶子节点肯定在最后两层上，所以先计算出树的深度为8，前七层一共有127个节点，所以第8层有73个节点且都为叶节点，第七层有64个节点，第八层的13个节点的父节点在第七层，占据37个，所以总共叶节点为:73+(64-37)=100个;根据二叉树的性质:对于一棵非空的二叉树，如果叶子节点数为n0，度为2的结点数为n2，则no=n2十1，所以度为2的节点有100-1=99个;所以选项D符合意。故选:D。 10.【答案】A [解析]根据题意，可以构建出二叉树。该二叉树的前序遍历为ABDGCEFH。不是完全二叉树，该二叉树中度为1的节点有3个，所以选项A说法正确。故选:A。 11.【答案】C [解析]4选项，观察此图，结合完全二叉树的定义发现该二叉树不是完全二叉树，A错误;该二又树的叶子节点有2个，不是3个，B错误;C选项，按照后序遍历(左右根)规则，该二叉树后序遍历序列为:FDBECA，正确。D选项，观察一维数组可以发现，B节点的孩子为D、E节点，这不符合二叉树图示，D错误。故选:C。 反 思 评 价 本章包含了树与二叉树、二叉树的基本操作、抽象数据类型等共3节，概念性的内容非常多。本节内容是中间一节的知识，了解树、子树、树的度、树的深度等概念。了解二叉树、满二叉树、完全二叉树等概念。通过具体任务的实践活动，体验用树型结构描述生活中蕴含树型结构的组织关系。 本节的重点是二叉树的建立及遍历。由于大部分内容是概念性的知识，可以结合生活实例，辅以图的形式，学习各种概念及性质。 对于差异化的教学，可以通过回顾复习、多画图展示，综合学生知识能力上的差异。任务差异化，目标一致化，对于学习能力强的同学，多布置课外思考题，能力一般的同学，以课堂目标为准，布置相应的任务。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$