高中信息技术浙教版：4-1 树与二叉树-教学设计

教学设计 课程基本信息 学科 信息技术 年级 高二 学期 春季 课题 树与二叉树 教学目标 1.了解树、子树、树的度、树的深度等概念。 2.了解二叉树、满二叉树、完全二叉树等概念。 教学内容 教学重点： 1.树、二叉树的概念。 2.树、二叉树的特点和性质。 教学难点： 1.树的特点。 2.二叉树的两种分类和三种性质。 教学过程 1、 问题导入：生活中的树可以抽象成逻辑上的树 在日常生活中，常见的树形结构有：1.公司组织架构 2.知识点汇总 3.动物分类等，这些树形结构的共同特征是：都呈现一对多的非线性关系 2、 树的概念与特点 1.树的定义：树是一种非线性数据结构，是有 n（n>=0）个节点的有限集合 2.空树：n=0 的树称为空树 3.当n>0时，n个节点的树有n-1条边 4.子树：树中某个节点下面的所有节点所构成的树 5.度：节点的度：节点所拥有的子树个数 树的度：最大的节点的度（树的宽度） 6.高度：（或深度）树中节点的最大层数 7.节点：根节点：（开始节点）没有前驱的节点 叶子节点：（终端节点）没有后继，度为0的节点 分支节点：度不为0的节点 内部节点：除根节点外的分支节点 父节点：两个以边直接连接的节点，上端节点是下端节点的父节点或双亲节点 孩子节点：下端节点是上端节点的孩子节点 兄弟节点: 拥有同一个父节点的同层节点 【学习任务一】 填一填： 1.该树有___个节点，____条边，该树的度是_____,高度是_____ 2.该树的叶子节点是___________________,内部节点是_____________________ 3.度为1的节点数有_____个，B的孩子节点是_______,Q的兄弟节点是_____ 答案：1. 12 11 3 6 2.E F Z P C H B G R Q D 3. 3 E F G P 3、 猜数游戏：小明写了一个100以内的正整数，让小红猜；小红每猜一次，小明会告诉她“猜大了”还是“猜小了”，直到猜出正确的结果。请问小红采用什么方法，能用最少的次数猜出正确结果？ 答：用折半猜数法，猜数过程如下，进一步引入二叉树 4、 二叉树的概念 二叉树是一个具有 n（n>=0）个节点的有限集合。当 n=0时，二叉树是一棵空树； 当 n>0时，则是由根节点、左子树和右子树组成；由于左、右子树也是二叉树，因此子树也可以是空树。二叉树的特征：所有节点的度都小于等于2。二叉树的5种不同形态如下图： 【学习任务二】 画一画：有3个节点的二叉树有几种不同的形态？（答：共5种，如下所示：） 5、 二叉树的分类 1.满二叉树 请学生观察以下3个二叉树的共同特点是？ 答:以上3个二叉树的所有的叶子节点都在最底层，除了叶子节点外，每个结点的度是2 这类二叉树称为：满二叉树 2.完全二叉树 请学生观察以下3个二叉树的共同特点是？ 答：以上3个二叉树至多只有最下两层中的节点的度数小于2，且最后一层的叶子结点都依次从左到右分布，这类二叉树称为：完全二叉树 【学习任务三】 判一判：下列4个图是否为完全二叉树？ （答案：D） 3.满二叉树 VS 完全二叉树 ①满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树 ②满二叉树在最后一层从最后一个节点开始，从右向左连续去掉几个节点，即为完全二叉树 【学习任务四】 选一选：下列哪些是满二叉树，哪些是完全二叉树？ （②是满二叉树 ⑤是完全二叉树） 6、 二叉树的性质 因为满二叉树在同层二叉树中，拥有的节点数最多，我们以满二叉树为例来探究下 性质1：二叉树的第k层上最多有2k-1个节点 性质2：深度为k的二叉树最多有2k-1个节点 性质3：在任意一颗二叉树中，度为2的节点数n2和度为0的节点数n0的关系是：n0=n2+1 【学习任务五】 请探究证明：在任意一颗二叉树中，都满足 n0=n2+1 推导过程如下： 节点数n满足等式： n=n0+n1+n2 ① 边数B满足等式： B=n-1 ② B=n0*0+n1*1+n2*2 ③ 由①②③可推导出 n0=n2+1 7、 课堂小结 8、 思考与探究 已知数组a=[7,9,12,23,34,40,66]，若要查找66，请参考“折半猜数法”，用二叉树画出查找的过程。（参考如下：） 教学反思 通过前三章的学习，学生已全面了解了线性数据结构中的数组、链表、字符串、队列和栈，对于蕴含线性结构的生活实例，可以用线性结构来存储数据、组织数据等。但对于非线性结构的生活实例，学生仅接触过，但并不能用树结构描述出数据的逻辑关系。本节课的重点是了解树、子树、树的度、树的深度、二叉树、满二叉树、完全二叉树等概