高中信息技术浙教版（2019）选修1 第四章　课时1　树与二叉树（学案 课件，2份打包）

(课件网) 课时1　树与二叉树 第四章　树 1.了解二叉树的基本概念和特点，并能结合实例进行分析。2.了解满二叉树和完全二叉树的特点，并能正确区分满二叉树和完全二叉树。3.理解二叉树的性质，并能利用二叉树的性质解决实际问题。 目 录 CONTENTS 知识梳理 01 例题精析 02 随堂检测 03 巩固与提升 04 知识梳理 1 1.树(Tree)的几个基本概念 树是一种_____的数据结构，用它能很好地描述有分支和层次特性的数据集合。 (1)树可以描述为由n(n≥0)个节点构成的一个_____以及在该集合上定义的一种_____关系。 (2)节点(Node)：集合中的元素称为树的节点，_____的树称为空树。 根节点：在树形结构中，_____的节点称为根节点(Root)，又称为开始节点。 父节点、孩子节点：在树形结构中，对于两个以边直接连接的节点，上端节点称为下端节点的父节点(Parent)，下端节点为孩子节点(Child)，简称为子节点。 (3)子树：树中某个节点下面所有节点所构成的树称为该节点的子树。 非线性 有限集合 节点 n＝0 没有前驱 (4)边：树的两个节点之间如果有一条边连接，那么称为这两个节点之间存在一条边。 对于一棵有n个节点的树，它有_____条边。 (5)度(Degree) 节点的度：树的一个节点所拥有的_____称为该节点的度。 树的度：_____称为树的度。 节点的度和树的度是指宽度。 (6)叶子：度为___的节点称为叶子节点(Leaf)，又称为终端节点。 (7)树的深度(高度)：树中节点的层数(Level)从根开始计算，根的层数为___，其余节点的层数等于父节点的层数加1。树中节点的_____称为树的高度或深度(Depth)。 n－1 子树个数 节点的度的最大值 0 1 最大层数 2.二叉树 (1)二叉树的定义 二叉树是指除根节点外的所有节点可分为两个互不相交的有限集合，分别称为左子树和右子树，左子树和右子树也是二叉树。 二叉树的子树有左右之分，且左右子树的次序不能颠倒。 (2)二叉树的高度(深度) 二叉树中节点的_____称为二叉树的深度或高度。 最大层数 (3)二叉树的五种形态 单点树 只有根和右子树 左右子树均非空 3.特殊的二叉树 (1)满二叉树 符合满二叉树的两个条件为： ①每个节点的度数均_____； ②所有叶子节点都在_____。 (2)完全二叉树 符合完全二叉树的两个条件为： ①只有_____中的节点度数小于2； ②最下一层的叶子节点都依次排列在该层_____位置。 为2或为0 同一层 最下二层 最左边 正确区分满二叉树和完全二叉树的方法： (1)满二叉树的判断方法：指叶子节点都在最下面一层上，除叶节点外其他每个节点的度数为2。 (2)完全二叉树的判断方法：可将一棵二叉树先变为满二叉树，然后从上到下，同层从左到右的次序从1开始连续编号，如果能按从大到小的顺序连续删除该满二叉树的若干节点后得到该二叉树，则该二叉树为完全二叉树。 4.二叉树的性质 (1)二叉树的第k层上最多有_____ (k≥1)个节点。 (2)深度为k的二叉树最多有_____(k≥1)个节点。 (3)在任意一棵二叉树中，叶子节点数比度为2的节点数_____。 2k－1 2k－1 多1个 例题精析 2 例1 有一棵树，如图所示。 C 解析　本题主要考查的是节点的度和树的度。节点a有三个子节点b、c、d，因此节点a的度为3；树的度是指宽度，即树中节点的度的最大值，树中节点g的度最大，节点g的度为4，因此树的度为4，答案为C。 则该树中节点a的度和树的度分别为(　　) A.3，3 B.4，3 C.3，4 D.3，10 变式训练　有一棵树，如图所示。 解析　本题主要考查的是树的深度。树中节点的最大层数称为树的高度或深度，根的层数为1，因此树的深度为5，答案为C。 C 则该树深度为(　　) A.3 B.4 C.5 D.6 例2 若树的根的高度为1，则二叉树的第p层上的节点数最多为(　　) 解析　本题主要考查的是二叉树 ... ...