4.1 树与二叉树-教学设计（表格式）

教学设计 课程基本信息 课题 树与二叉树 教学目标 1.了解树、子树、树的度、树的深度等概念。 2.了解二叉树、满二叉树、完全二叉树等概念。 教学内容 教学重点： 1.树、二叉树的概念。 2.树、二叉树的特点和性质。 教学难点： 1.树的特点。 2.二叉树的两种分类和三种性质。 教学过程 问题导入：生活中的树可以抽象成逻辑上的树 在日常生活中，常见的树形结构有：1.公司组织架构 2.知识点汇总 3.动物分类等，这些树形结构的共同特征是：都呈现一对多的非线性关系 树的概念与特点 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 猜数游戏：小明写了一个100以内的正整数，让小红猜；小红每猜一次，小明会告诉她“猜大了”还是“猜小了”，直到猜出正确的结果。请问小红采用什么方法，能用最少的次数猜出正确结果？ 答：用折半猜数法，猜数过程如下，进一步引入二叉树 二叉树的概念 二叉树是一个具有 n（n>=0）个节点的有限集合。当 n=0时，二叉树是一棵空树； 当 n>0时，则是由根节点、左子树和右子树组成；由于左、右子树也是二叉树，因此子树也可以是空树。二叉树的特征：所有节点的度都小于等于2。二叉树的5种不同形态如下图： 【学习任务二】 画一画：有3个节点的二叉树有几种不同的形态？（答：共5种，如下所示：） 二叉树的分类 1.满二叉树 请学生观察以下3个二叉树的共同特点是？ 答:以上3个二叉树的所有的叶子节点都在最底层，除了叶子节点外，每个结点的度是2 这类二叉树称为：满二叉树 2.完全二叉树 请学生观察以下3个二叉树的共同特点是？ 答：以上3个二叉树至多只有最下两层中的节点的度数小于2，且最后一层的叶子结点都依次从左到右分布，这类二叉树称为：完全二叉树 【学习任务三】 判一判：下列4个图是否为完全二叉树？ （答案：D） 3.满二叉树 VS 完全二叉树 ①满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树 ②满二叉树在最后一层从最后一个节点开始，从右向左连续去掉几个节点，即为完全二叉树 【学习任务四】 选一选：下列哪些是满二叉树，哪些是完全二叉树？ （②是满二叉树 ⑤是完全二叉树） 二叉树的性质 因为满二叉树在同层二叉树中，拥有的节点数最多，我们以满二叉树为例来探究下 性质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 课堂小结 思考与探究 已知数组a=[7,9,12,23,34,40,66]，若要查找66，请参考“折半猜数法”，用二叉树画出查找的过程。（参考如下：） ... ...