4.1 树与二叉树（教学设计）信息技术浙教版2019选择性必修1

4.1 树与二叉树 1课时（教学设计） 年级 高二年级 授课时间 1课时 课题 4.1 树与二叉树 教学 目标 1.了解树、子树、树的度、树的深度等概念。 2.了解二叉树、满二叉树、完全二叉树等概念。 3.通过具体任务的实践活动，体验用树型结构描述生活中蕴含树型结构的组织关系。 教学 重难点 重点： 1.树、二叉树的概念。 2.树、二叉树的特点和性质。 难点： 1.树的特点。 2.二叉树的两种分类和三种性质。 教学 准备 多媒体课件、多媒体教室 教学过程 教师活动 学生活动 新 课 导 入 一、课堂导入 1.通过两张图片展示进行问题导入:生活中的树可以抽象成逻辑上的树。 2.展示现实生活中组织关系图为树型结构的实例，引出树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。 让学生思考，列举组织关系图为树型结构的生活实例。 以图片方式，吸引学生参与课堂，感知生活中蕴含树型结构的实例。 结合树型结构，发挥想象，列举生活中的实例。 新 知 讲 授 二、树 通过展示公司内部管理的组织关系图、赋值语句的语法树、数据库层次结构图，让同学们知道树形结构在现实世界中广泛存在。 概念：树（Tree）可以描述为由n（n≥0）个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系。 节点:树的元素【n=0为空树] 子树:树中某个节点下面的所有节点所构成的树 两个节点之间存在一条边 一棵具有n个节点的树，它有n-1条边。 ※树中共有13个节点、12条边。 ※节点B、G、H构成了节点A的一棵子树。 节点的度：某节点拥有的子树个数 树的度：最大的节点的度 ※节点A的度为5， ※节点B的度为2， ※节点I的度为3， 因此树的度为5。 线性表( 特殊的树)——度为1 节点的度和树的度共同体现了树的宽度(节点的分支数和树的发散程度)。 根节点（开始节点）：没有前驱的节点 叶子节点（终端节点）：度为0 分支节点（非终端节点）：度不为0 内部节点：除根节点之外的分支节点 父节点（双亲节点）：以边相连的上端节点 孩子节点：以边相连的下端节点 兄弟节点：拥有同一父节点 树的高度/深度=4 树中节点层数：根节点层数为1，其余节点层数等于其父节点的层数加1 树的高度/深度=最大层数 （1）线性结构： ①必存在着唯一的一个“第一个元素”和唯一的一个“最后的元素”； ②除第一个元素以外，其他数据元素均有唯一的“前驱”，除最后元素以外，其他数据元素均有唯一的“后继”。 （2）树形结构（拥有多个节点）：非线性结构， ①根节点（无前驱，有后继）， ②叶子节点（存在多个，没有后继，只有前驱），其余的节点都只有一个直接前驱和多个直接后继。 拓展链接：图（Graph） 图状结构是一种比线性结构和树形结构更为复杂的非线性结构，广泛应用于计算机网络、通信工程等诸多领域。在线性表中，一个数据元素只和它的前驱和后继元素有关系。在树中，一个节点只和它的父节点和孩子节点有关系。而在图中，每个顶点都有可能和其他任意顶点有关系，这就使得图的存储和运算比前两种数据结构更加复杂。 探讨与讨论 1.诸葛亮家族的部分家谱如图所示。和家谱图结构相似的数据结构是( ) A.树 B.栈 C.队列 D.链表 三、二叉树 树的形态有很多，在实际的使用过程中，需要对树的形态进一步地进行约束和简化， 以便于设计和操作。二叉树是树形结构的一个重要类型，在实际应用中，许多问题抽象出 来的数据结构往往就是二叉树的形式。 猜数字游戏：甲方事先在纸上写出一个100以内的正整数，让乙方猜，乙方每猜一次，甲方都会告诉乙方“猜大了”或是“猜小了”，直至猜出正确结果。乙方如果采取“折半”的策略进行猜数字，就一定能够在7次以内猜对结果。 猜数字过程的抽象形态 每个节点为乙方所猜的数字，每条边为实际数字与所猜数字 之间的大小关系，图中仅呈现前4次的猜数字情况。 1. 二叉树的概念 二叉树（Binary Tree）是一个具有n（n≥0）个节点的有限集合。 （1）当n=0时，二叉树是一棵空树; （2）当n≠0时，则是一棵由根节点和两棵互不相交的、分别称作这个根节点的左子树和右子树组成的二叉树，由于左、右子树也是二叉树，因此子树也可以是空树。 二叉树的重要特征：它的所有节点的度都小于或者等于2。 二叉树的示例 五种不同形态的二叉树 从左到右分别是： ①空二叉树； ②只有根节点的单点树； ③只有根节点和左子树； ④只有根节点和右子树； ⑤左右子树均非空。 满二叉树 ①每个节点的度数为2(具有两个非空子树)，或者度数为0(叶子节点)。 ②所有叶子节点都在同一层 完全二叉树 ①至多只有最下两层中的节点度数小于2。 ②最下一层的叶子节点都依次排列在该层最左边位置。 （3）探讨与讨论 满二叉树和完全二叉树有什么区别？ ①满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。 ②空二叉树和只有根节点的二叉树既是满二叉树，也是完全二叉树。 ③完全二叉树可看作是在满二叉树最下一层，从右向左去掉若干个节点后得到。 ④完全二叉树中一个节点如果没有左子节点，就一定没有右子节点。 2.二叉树的性质 （1）二叉树的第k层上最多有2k–1（k≥1）个节点。 ※当k=1时，只有1（20=1）个根节点； ※当k=2时，由于节点的度最大为2，因此，第2层的节点数最多有2（21=2）个节点。依次推出，第k层上最多有2k–1个节点。 （2）深度为k的二叉树最多有2k–1（k≥1）个节点。 ※第1层至第k层上的最大节点数相加的结果是：20+21+…+2k–1=2k–1。 ※因此2k–1是深度为k的二叉树的最多节点总数。 （3）在任意一棵二叉树中，若度为2的节点数量为n_2，叶子节点（度为0的节点）数为n_0，则n_0=n_2+1。 ※度为0，1和2的节点数分别是nn_0、n_1和n_2 ，总的节点数n=n_0+n_1+n_2 ① ※n个节点的二叉树的总边数为n-1条。 ※二叉树的总边数与度之间的关系: n-1= n_0×0+n_1×1+n_2×2 ② 联立等式① ②，可得n_0=n_2+1 甲、乙两棵二叉树 ※在甲树上，度为2的节点数是1，度为1的节点数是1，叶子节点数为2； ※在乙树上，度为2的节点数是2，度为1的节点数是1，叶子节点数为3。 3.拓展链接：哈夫曼树 哈夫曼树又称最优二叉树，它的相关概念如下。 路径:树中两个节点之间所经过的分支,称为它们之间的路径。 路径长度:一条路径上的分支数,称为该路径的长度。 节点的权:给二叉树中的节点赋一个数,该数称为该节点的权。 节点带权路径长度:从根节点到一个节点的路径长度与该节点的权值的乘积，称为该节点的带权路径长度。 4.探讨与讨论 （1）已知一棵完全二叉树共有200个节点，下列说法正确的 是( ) A.该完全二叉树的高度为7 B.该完全二叉树有99个叶子节点 C.该完全二叉树有100个度为2的节点 D.该完全二叉树有1个度为1的节点 四、课堂练习D E A B C F 1.某二叉树如图所示，下列说法正确的是( ) A.该二叉树是完全二叉树 B.该二叉树共有4个叶子节点 C.节点D、F都是节点B的孩子节点 D.该二叉树后序遍历的结果为DEBFCA 2.某二叉树的前序遍历结果为ABC,若该二叉树不是满二叉树，则其后序遍历结果为( ) A.ABC B.BCA C.CBA D.CAB 3.已知某二叉树的前序遍历为“ABCDEF"中序遍历为“BCAEFD”，则该二叉树的后序遍历为( ) A.CBFEDA B.BCFEDA C.CBEFDA D.BCEFD 五、小结 通过实际问题，恰当地选择树结构，以知识条目的方式呈现树结构相的概念，并总结树的概念。(意图:体现先学后教的理念。） 讲授基础理论，辅以图示，让学生对理论有更形象的了解，落实教学重点。 培养学生自主学习能力，并把学到的知识，与前几章节中的线性结进行对比，并辅以实例，形式化的描述出来。 以讨论形式，现学现用，用树结构解决生活中的问题。 设置难度适当的实践练习，加深学生对树概念和特性的理解，确定后续新知讲授的推进。 以一个游戏为例，吸引学生参与课堂，抛出问题，让学生思考并观看教师的PPT课件上的图片提示，从而引出二叉树的概念。 知识点迁移。利用刚刚讲解的二叉树的所有形态，模拟出4个节点的所有二叉树的形态。 帮助学生通过小组合作的方式，从“满二叉树”“完全二叉树”两种形态，归纳出它们的不同点与相同点。 以多种树的形式，直观的展现第k层的情况，验证性质1的正确性。 通过课堂练习，加深同学们对栈的理解。 讲解二叉树的性质，让学生理解二叉树的节点的算法，如何解决实际中的二叉树节点算法的问题，逐步形成运用二叉树结构解决问题的思维方式和学科方法。 梳理本次课内容，形成知识体系；分析树与二叉树的重要性，并对今后学习进行展望。 课 堂 练 习 （有题有答案有解析） 1.树是一种 的数据结构，用它能很好地描述有 和 特性的数据集合。 2.树（Tree）可以描述为由 个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系。 3.一棵具有n个节点的树，它有 条边。 4.树的一个节点所拥有的子树个数称为该节点的度（Degree），最大的节点的度称为 。 5.二叉树（Binary Tree）是一个具有 个节点的有限集合。当n=0时，二叉树是一棵 。 6.二叉树的重要特征：它的所有节点的度都 。 7.二叉树的第k层上最多有 个节点。 8.深度为k的二叉树最多有 个节点。 9.一棵度为3，深度为4的树，最多有（）个节点。 A.31 B.32 C.40 D.42 10.一棵高度为6的满二叉树中的节点数为（） A.31个 B.32个 C.63个 D.64个 11.某二叉树如下图所示,用数组来表示为（） D E A B C F G A. 0 1 2 3 4 5 6 7 8 A B C D E F G B. 0 1 2 3 4 5 6 7 8 A B C D E F G C. 0 1 2 3 4 5 6 7 8 A B C D E F G D. 1 2 3 4 5 6 7 8 9 A B C D E F G 12.已知一棵完全二叉树有8个叶子节点，下列说法正确的是（） A.该完全二叉树的高度可能为3 B.该完全二叉树的形态只有一种 C.该完全二叉树可能有1个度为1的节点 D.该完全二叉树有9个度为2的节点 13.某二叉树如下图所示： 用list表示该二叉树为（） A.['1,2,3',4,5'↓6',7'] B.[1,[2,4',5],['3',6','7']] C.[1,[2,[4],['5]],[3 ,[6’],['7']]] D.[1,[2,[4',None,None],[5',None,None]],[3',[6,None,None],[7,None,None]]] 答案： 1.非线性、分支、层次。 2.n（n≥0）。 3.n-1。 4.树的度。 5.n（n≥0）、空树。 6.小于或者等于2。 7.2k–1（k≥1）。 8.2k–1（k≥1）。 9.【答案】C [解析]第一层为1个节点，第二层为3个节点，第三次为9个节点，第四层为27个节点。共计1+3+9+27=40故选:C。 10.【答案】C [解析]本题主要考查的是满二叉树的特点。一棵高度为6的满二叉树中的节点数为26-1个,即63个,因此,答案为C。 11.【答案】C [解析]本题主要考查的是二叉树的数组表示，图中的二叉树为非完全二叉树,先将它补全为一棵完全二叉树,即补全C节点的右孩子节点,然后按照完全二叉树的方法来表示，因此,答案为C。 12.【答案】C [解析]已知一棵完全二叉树有8个叶子节点，可能是高度为4的满二叉树，也可能第五层还有一个叶子节点的完全二叉树，因此该完全二叉树的形态有两种;该完全二叉树可能有1个度为1的节点;该完全二叉树有7个度为2的节点。故选:C。 13.【答案】D [解析]本题主要考查的是二叉树的list 实现。空树用None表示,非空二叉树用三个元素的列表[根节点,左子树节点,右子树节点],左右子树也采用相同的方式处理。因此该二叉树用list表示为[1',[['2',[['4',None,None]，[['5',None,None]]，[['3',[['6',None,None]，[['7',None,None]]]，答案为D。 课 堂 小 结 课堂小结 一、树 1. 树的概念 2. 树的示例 二、二叉树 1.二叉树的概念 2. 二叉树的性质 3.拓展链接：哈夫曼树 作 业 设 计 1.某完全二叉树共有 300个节点，该二叉树的高度是（） A.8 B.9 C.10 D.11 2.已知一棵完全二叉树共有200个节点，下列说法正确的是（） A.该完全二叉树的高度为7 B.该完全二叉树有99个叶子节点 C.该完全二叉树有100个度为2的节点 D.该完全二叉树有1个度为1的节点 3.某二叉树如图所示，下列说法正确的是（） D E A B C F A.该二叉树是完全二叉树 B.该二叉树共有4个叶子节点 C.节点D、F都是节点B的孩子节点 D.该二叉树后序遍历的结果为DEBFCA 4.某二叉树的前序遍历结果为 ABC,若该二叉树不是满二叉树，则其后序遍历结果为（） A.ABC B.BCA C.CBA D.CAB 5.已知某二叉树的前序遍历为“ABCDEF"中序遍历为“BCAEFD”，则该二叉树的后序遍历为（） A.CBFEDA B.BCFEDA C.CBEFDA D.BCEFD 6.某二叉树用一维数组存储结构如下表所示: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H 下列有关该二叉树的说法正确的是（） A.该二叉树是完全二叉树 C.前序遍历为 A-B-D-F-G-C-H-E B.度为2的节点有3个 D.节点C是节点E 的父节点 7.用一维数组表示二叉树，如表所示: 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G 下列有关该二又树的说法正确的是（） A.该树中共有4个叶子节点 B.该树是完全二叉树，其深度为4 C.该树的中序遍历为B-F-D-G-A-C-E D.该二叉树的结构图为(如图所示) 8.诸葛亮家族的部分家谱如图所示。和家谱图结构相似的数据结构是（） A.树 B.栈 C.队列 D.链表 9.已知一棵完全二叉树共有200个节点，下列说法正确的是( ) A.该完全二叉树的高度为7 B.该完全二叉树有99个叶子节点 C.该完全二叉树有100个度为2的节点 D.该完全二叉树有1个度为1的节点 答案： 1.【答案】B [解析]本题考查的是二叉树的遍历。前序的规则就是根结点--->左子树--->右子树;中序遍历的规则是:左子树--->根结点--->右子树;后续就是左子树--右子树--->根结点。根节点:没有父节点的节点。度:节点下孩子节点的个数，树的度为节点度的最大值。分支节点:度不为0的节点。叶子结点:没有子节点的节点，树的终端。完全二叉树，高度是[log2N]+1，以2为底的对数取整后+1。故该完全二叉树的高度为h=log2300+1=9。故选:B。 2.【答案】D [解析]完全二叉树的性质可以知道:叶子节点肯定在最后两层上，所以先计算出树的深度为8，前七层一共有127个节点，所以第8层有73个节点且都为叶节点，第七层有64个节点，第八层的13个节点的父节点在第七层，占据37个，所以总共叶节点为:73+(64-37)=100个;根据二叉树的性质:对于一棵非空的二叉树，如果叶子节点数为n0，度为2的结点数为n2，则no=n2+1，所以度为2的节点有100-1=99个;所以选项D符合意。故选:D。 3.【答案】D [解析]选项A，该二叉树不是完全二叉树，如果是完全二叉树，则叶子节点尸的位置应该是C节点的左孩子节点。选项B，该二又树共有4个叶子节点，说法错误。共有3个叶子节点，分别是D、E、F。选项C，说法错误，F节点是节点C的孩子节点。故选:D。 4.【答案】C [解析]前序遍历结果为ABC，不是满二叉树，故其树可能为: B A C B A C B A C C B A 其后序遍历结果都为:CBA。故选:C。 5.【答案】A [解析]阅读题干根据前序遍历可知根节点为4，所以左子树为BC，右子树为EFD，最终推得后序遍历为CBFEDA。故选:A。 6.【答案】D [解析]由数组可知二叉树如图:B A C D E H F G 该二叉树不是完全二叉树;度为2的节点有2个;前序遍历为:ABDFGCEH;节点C是节点E的父节点。故选:D。 7.【答案】C [解析]观察图形可知，中序遍历的规则是:左子树--->根结点--->右子树所以该树的中序遍历为B-F-D-G-A-C-E选项C说法正确。故选:C。 8.【答案】A [解析]树状图是一种数据结构，它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。选项A符合题意。故选:A。 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。 反 思 评 价 本章包含了树与二叉树、二叉树的基本操作、抽象数据类型等共3节，概念性的内容非常多。本节内容是后两节的先行知识，了解了树、二叉树等相关的概念及性质后，可以深度学习二叉树等基本操作。 本节的重点是了解树、子树、树的度、树的深度、二叉树、满二叉树、完全二叉树等概念，以及它们的性质。由于大部分内容是概念性的知识，可以结合生活实例，辅以图的形式，学习各种概念及性质。 对于差异化的教学，可以通过回顾复习，综合学生知识能力上的差异。任务差异化，目标一致化，对于学习能力强的同学，多布置课外思考题，能力一般的同学，以课堂目标为准，布置相应的任务。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$