第四章 树（复习课件）信息技术浙教版2019选择性必修1

复习课件 第4章 树 浙教版（2019） 选修一 树与二叉树 01 二叉树的基本操作 02 抽象数据类型 03 复习内容总览 树与二叉树 PART 01 第1节 树与二叉树 知识结构 第1节 树与二叉树 知识点一 树（Tree）可以描述为由n（n≥0）个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系。 树 节点:树的元素【n=0为空树] 子树:树中某个节点下面的所有节点所构成的树 两个节点之间存在一条边 节点的度：某节点拥有的子树个数 树的度：最大的节点的度 第1节 树与二叉树 知识点一 第1层 第3层 第4层 第2层 树的示例 根节点（开始节点）：没有前驱的节点 叶子节点（终端节点）：度为0 分支节点（非终端节点）：度不为0 内部节点：除根节点之外的分支节点 父节点（双亲节点）：以边相连的上端节点 孩子节点：以边相连的下端节点 兄弟节点：拥有同一父节点 父节点 根节点 叶子节点 第1节 树与二叉树 知识点一 1 线性结构： 必存在着唯一的一个“第一个元素”和唯一的一个“最后的元素”； 除第一个元素以外，其他数据元素均有唯一的“前驱”，除最后元素以外，其他数据元素均有唯一的“后继”。 2 树形结构（拥有多个节点）：非线性结构， 根节点（无前驱，有后继）， 叶子节点（存在多个，没有后继，只有前驱），其余的节点都只有一个直接前驱和多个直接后继。 第1节 树与二叉树 知识点二 二叉树的概念 二叉树（Binary Tree）是一个具有n（n≥0）个节点的有限集合。 二叉树的性质 01 02 二叉树的第k层上最多有2k–1（k≥1）个节点。 深度为k的二叉树最多有2k–1（k≥1）个节点。 03 在任意一棵二叉树中，若度为2的节点数量为，叶子节点（度为0的节点）数为，则。 第1节 字符串 提升练习 1.已知一棵完全二叉树共有200个节点，下列说法正确的是( ) A.该完全二叉树的高度为7 B.该完全二叉树有99个叶子节点 C.该完全二叉树有100个度为2的节点 D.该完全二叉树有1个度为1的节点 D 解析 完全二叉树的性质可以知道:叶子节点肯定在最后两层上，所以先计算出树的深度为8，前七层一共有127个节点，所以第8层有73个节点且都为叶节点，第七层有64个节点，第八层的13个节点的父节点在第七层，占据37个，所以总共叶节点为:73+(64-37)=100个;根据二叉树的性质:对于一棵非空的二叉树，如果叶子节点数为n0，度为2的结点数为n2，则no=n2+1，所以度为2的节点有100-1=99个;所以选项D符合意。 第1节 字符串 提升练习 2.某二叉树用一维数组存储结构如下表所示: 下列有关该二叉树的说法正确的是( ) A.该二叉树是完全二叉树 C.前序遍历为 A-B-D-F-G-C-H-E B.度为2的节点有3个 D.节点C是节点E 的父节点 D 解析 由数组可知二叉树如图: 该二叉树不是完全二叉树;度为2的节点有2个;前序遍历为:ABDFGCEH;节点C是节点E的父节点。故选:D。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D   E F G           H B A C D E H F G 第1节 字符串 提升练习 3.如图所示，一个数学表达式可以用一棵表达式树来表示。下列关于该表达式树的描述，不正确的是( ) A.该表达式树不是完全二叉树 B.若表达式树中只有四则运算,则对应的表达式树的每个节点都有两个子节点 C.表达式树的根节点左右子树深度差不会超过1 D.该表达式树对应的表达式为“(3+4)*6-8+4/(3*2)” C 解析 表达式树根节点左右子节点的深度差可以超过1，*节点的左右子树深度分别为3和1。 二叉树的基本操作 PART 02 第2节 二叉树的基本操作 知识结构 第2节 二叉树的基本操作 知识点一 1.数组实现 从二叉树的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为n–1。 然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。 完全二叉树 对于非完全二叉树，先将它补全为一棵完全二叉树，补上的节点及分支用虚线表示。 然后将补全后的完全二叉树，从它的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，第四章根节点的编号为0，最后一个节点的编号为n–1。 非完全二叉树 第2节 二叉树的基本操作 知识点一 2.链表实现 二叉树也可以采用链表来实现，用任意一组存储单元来存储二叉树的节点，用指向节点的指针来表示节点之间的关系。 二叉树的节点可能有两个孩子 右孩子 左孩子 此二叉树的节点至少需要3个域： 一个数据域和两个指针域。 第2节 二叉树的基本操作 知识点二 二叉树的遍历 概念 ①前序遍历（根-左-右） ②中序遍历（左-根-右） ③后序遍历（左-右-根） 按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。 遍历 方式 ④层序遍历 解题技巧 1.某二叉树的树形结构如下图所示，后序遍历结果为“WUSVTR”，则该二叉树的前序遍历结果为（    ） A．RSTUVW B．RTSVUW C．RTSUWV D．RSUWTV 解析 [解析]后序遍历就是左子树--->右子树>根结点， 根据这一规则，书写规则为故其前序遍历序列为: RSUWTV，故选D。 D 解题技巧 2.某二叉树的前序遍历为+*a-bc/df，中序遍历为a*b-c+d/f，下列说法正确的是（   ） A．该二叉树的叶子节点有2个 B．该二叉树为完全二叉树 C．该二叉树的后序遍历是abc-*df/+ D．若abcdf的值分别为3、2、5、6、3，则该表达式的运算结果为4 解析 [解析]本题主要考查二叉树的遍历。由前序遍历以及中序遍历，可画出该二叉树，由二叉树可知，该二叉树的叶子节点有5个;不是完全二叉树;该二叉树的后序遍历是abc-*df+;若abcdf的值分别为3、2、5、6、3，则该表达式的运算结果为3.0，故本题选C选项。 c 解题技巧 3.某二叉树如下图所示,请回答下列问题。 (1)该二叉树的深度为 。 (2)写出该二叉树的前序遍历、中序遍历和后序遍历。 前序遍历序列为: 。 中序遍历序列为: 。 后序遍历序列为: 。 解析 [解析]（1）本题主委考查的是二叉树的深度和遮历。(1)谊二叉树共有5层,根节点的深度为1,因此该二义树的深度为5。 (2)二叉树的前序遍历的規则是先访问穗节点,然后访问左子树,最后访问右子树,对左子树和右子树仍按上述规则访问,因此前序透历序列为“sbdhecfikg”；中序遍历的规则是先访问左子树,然后访问粮节点,最后访问右子树,因北中序遍历序列为“hdbcaifkcg”；后序遍历的规则是先访问左子树,然后访问右子树,最后访问根节点,因此后序遍历序列为"hdebikjfgca"。 5 abdhecfijkg hdbeaifkcg hdebikjfgca 抽象数据类型 PART 03 第3节 抽象数据类型 知识结构 第3节 抽象数据类型 知识点一 概念 抽象数据类型:(Abstract Data Type,简称ADT)是指一个数学模型及定义在该模型上的一组操作。 数据类型与抽象数据类型 字符串抽象数据类型的内部表现 第3节 抽象数据类型的描述 知识点二 描述 定义一个抽象数据类型，需要清晰地表述出各方面的形式要求（操作的名字、参数的个数和类型等）和功能要求（希望这个操作完成什么样的计算或产生什么效果等）。 当然，还需要为这一抽象数据类型确定一个类型名。 描述抽象数据类型的标准格式 第3节 抽象数据类型的作用 知识点三 2 4 5 3 1 程序结构清晰、层次分明，便于程序正确性的证明和复杂性的分析; 因为模块化的特点，便于改正错误的代码，利于维护系统; 抽象数据类型的表示和实现利于封装，便于代码的移植和重用； 使得算法设计和数据结构设计分开，降低了程序的复杂性，利于编写代码实现的可靠性； 使得数据结构可自由选择，给了算法的优化空间，提高了程序运行的效率。 抽象数据类型的作用 解题技巧 1.关于抽象数据类型的作用,下列描述不正确的是( ) A.抽象数据类型将生活中的一些细小规模的问题抽象成规模较大的问题 B.使用抽象数据类型编写出来的程序结构更加清晰,层次更加分明 使用抽象数据类型编写的程序具有模块化特点,具有更好的可维护性 D.抽象数据类型的表示和实现都可以封装起来,便于移植和重用 解析 [解析]抽象数据类型把生活中的实际问题分解成规模更小且容易处理的问题。 A 解题技巧 2.下列有关 Python 抽象数据类型(ADT)的说法中,错误的是（ ） A. ADT的基本思想是抽象,与在计算机内部如何表示和实现有关 B.Python 中的列表 list 就是一种抽象数据类型 C.Python 中通常使用类(class)来实现抽象数据类型 D, 定义一个抽象数据类型,目的是要定义一类计算对象,使它们具有某些特定的功能 解析 [解析]ADT的基本思想是抽象,它的定义仅取决于它的一组逻辑特性，把数据结构及其操作作为一个整体来研究，而与其在计算机内部如何表示和实现无关，因此 A选项错误。 A 解题技巧 3.有如下自定义函数: def fun(a): s=0 for i in a: s+=i return s 则 Python 内置函数中,与自定义函数fun(a)的功能相似的是（ ） A.len( ) C.max( ) B.sum( ) D.min( ) 解析 [解析]自定义函数fun(a)的功能是计算并返回列表a的元素之和,与之功能相似的是内置函数 sum()。 B 第4章 树 浙教版（2019） 选修一 谢谢观看 $$