4.2 二叉树的基本操作（教学课件）信息技术浙教版2019选择性必修1

第2节 二叉树的基本操作（1课时） 第4章 树 浙教版（2019） 选修一 二叉树的建立 01 二叉树的遍历 02 二叉树遍历的Python程序实现 03 学习目录 掌握二叉树的两种建立方式。 01 了解抽象数据类型的概念、抽象数据类型的描述、抽象数据类型的作用。 03 熟练掌握二叉树的三种遍历方式。 02 学习目标 PART 01 二叉树的建立 新课导入 树？ 完全二叉树 满二叉树 新课导入 想 想 一 对于图中的两棵二叉树(一张满二叉树，一张完全二叉树)，如何组织、存储节点信息? 问题 可采用数组形式和链表形式存储节点信息。也可采用数组形式和链表形式，与学生一起模拟建树过程。 办法 二叉树的建立 一 1 从二叉树的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为n–1。 然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。 完全二叉树 完全二叉树 数组表示示意图 完全二叉树的数组表示 数组实现 二叉树的建立 一 对于非完全二叉树，先将它补全为一棵完全二叉树，补上的节点及分支用虚线表示。 然后将补全后的完全二叉树，从它的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，第四章根节点的编号为0，最后一个节点的编号为n–1。 非完全二叉树 甲 原二叉树 非完全二叉树的数组表示 甲所示的一棵非完全二叉树补全为乙所示的完全二叉树 乙 补全后的二叉树 丙 数组实现示意图 依次把完全二叉树中原二叉树的节点用一维数组的各个元素来表示，节点编号与数组的下标一一对应。 二叉树的建立 一 甲 原二叉树 乙 补全后的二叉树 丙 数组实现示意图 对于完全二叉树而言，一维数组的表示方式既简单又节省存储空间。但对于一般的二叉树来说，采用一维数组表示时，结构虽然简单，却容易造成存储空间的浪费。如上图甲所示，一个深度为k且只有k个节点的树需要如上图乙所示2k –1个节点的存储空间才能表示出来。 非完全二叉树的数组表示 二叉树的建立 一 探讨与讨论 1.用数组表示的二叉树的方式更适合完全二叉树还是非完全二叉树?为什么? 对于完全二叉树而言，一维数组的表示方式既简单又节省存储空间。但对于一般的二又树来说，采用一维数组表示时，结构虽然简单，却容易造成存储空间的浪费。如图4.2.2甲所示，一个深度为k且只有k个节点的树需要如乙图所示2k1个节点的存储空间才能表示出来。 二叉树的建立 一 探讨与讨论 1.某二叉树如下图所示，用数组来表示为（ ） D 二叉树的建立 一 2 链表实现 二叉树也可以采用链表来实现，用任意一组存储单元来存储二叉树的节点，用指向节点的指针来表示节点之间的关系。 二叉树的节点可能有两个孩子 右孩子 左孩子 此二叉树的节点至少需要3个域： 一个数据域和两个指针域。 二叉树的建立 一 链表实现 两个指针域分别指向节点的左孩子和右孩子，这两个指针分别称为左指针和右指针，这样得到的 链表也称为二叉链表。 二叉树及其对应的二叉链表实现示意图 二叉树的建立 一 拓展链接 二叉树的 list实现 二叉树节点可以看成一个三元组，元素是左、右子树和本节点数据。Python的list可以用于组合这样的三个元素。 下面介绍用list构造二叉树的方法。 （1）空树用None表示。 （2）非空二叉树用包含三个元素的列表[d,l,r]表示，其中：d表示根节点的元素，l和r是两棵子树，采用与整个二叉树同样结构的list表示。构更加复杂。 二叉树 二叉树的建立 一 只需知道数据之间相互链接的顺序 探讨与讨论 1.某二叉树对应的一维数组表示如图所示: 下列关于该二叉树的说法正确的是( ) A.该二叉树的度为3 B.该二叉树有2个叶子节点 C.该二叉树是一棵完全二叉树 D.该二叉树前序遍历结果为ABCDE 1 2 3 4 5 6 A B C D   E B 二叉树的建立 一 只需知道数据之间相互链接的顺序 探讨与讨论 2.已知一棵完全二叉树共有200个节点，下列说法正确的是( ) A.该完全二叉树的高度为7 B.该完全二叉树有99个叶子节点 C.该完全二叉树有100个度为2的节点 D.该完全二叉树有1个度为1的节点 D 二叉树的遍历 二 概念 ①前序遍历（根-左-右） ②中序遍历（左-根-右） ③后序遍历（左-右-根） 按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。 遍历 方式 ④层序遍历 二叉树的遍历 二 前序遍历 根左右 ※规则：若二叉树为空，则空操作返回；否则，先访问根节点，再访问左子树，最后访问右子树。 ※从右图中得到的前序遍历顺序为：A-B-D-H-E-C-F-I-G-J-K。 前序遍历的过程 二叉树的遍历 二 中序遍历 左根右 ※规则：若二叉树为空，则空操作返回；否则，先访问左子树，再访问根节点，最后访问右子树。 ※从右图中得到的中序遍历顺序为：D-H-B-E-A-I-F-C-J-G-K。 中序遍历的过程 二叉树的遍历 二 后序遍历 左右根 ※规则：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树，最后访问根节点。 ※从右图中得到的后序遍历顺序为：H-D-E-B-I-F-J-K-G-C-A。 后序遍历的过程 二叉树的遍历 二 层序遍历 ※规则：若二叉树为空，则空操作返回；否则，从根节点开始，自上而下，从左往右遍历。 二叉树的遍历 二 如果选取其中一种遍历策略对二叉树进行遍历，对于二叉树的左右子树，也需遵守该遍历原则，即二叉树的任意一个局部都必须遵守该遍历原则。对一棵二叉树进行前序遍历时，根节点总是处于遍历序列之首；中序遍历时根节点位置居中，左子树的所有节点都在其左边，右子树所有节点都在其右边；后序遍历时根节点位置在最后，其所有节点都在其左边。 二叉树的遍历 二 表达式树 将右图中的二叉树实行中序遍历，将得到遍历序列：8–(3+2*6)/5+4，即人们平时习惯书写的数学表达式，也称为中缀表达式。 如果对图中二叉树实行后序遍历，那么得到遍历序列：8 3 2 6 *+ 5 / – 4 +，称为后缀表达式（也称逆波兰表达式）。 由于中缀表达式要将运算符放在两个操作数中间，并且在许多情况下为了确定运算顺序，括号是必不可少的。 而书写后缀表达式时，因为采用了运算符紧跟在两个操作数之后的方法，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右依序完成计算，并方便求得结果。 则该二叉树的前序遍历序列是(　 　) 则该二叉树的中序遍历序列是(　 　) 则该二叉树的后序遍历序列是(　 　) 则该二叉树的层序遍历序列是(　 　) 二叉树的遍历 二 探讨与讨论 1.某二叉树如图所示: a bdg cf dgb a cf gdb fc a a bc df g 二叉树的遍历 二 探讨与讨论 2.一棵二叉树的前序遍历序列为“abdgecf”，中序遍历序列为“gdbeacf”，则该二叉树的后序遍历序列是( ) A.gdebfca B.gdebcfa C.gdebafc D.gedbfca A 二叉树遍历的Python程序实现 三 通过Python语言的程序实现来进一步体验二叉树的遍历机制 实践内容 给出事先设计好的二叉树结构图，分别写出前序、中序和后序的遍历结果。通过输入Python程序分别建立、遍历二叉树，运行程序输出各种遍历结果，完成验证和体验。 二叉树遍历的Python程序实现 三 ①给定右侧的二叉树 ②写出该二叉树的前序、中序历的序列。 ③建立二叉树,代码如下： 实践 步骤 二叉树 class Node: #建立二叉树 def __init__(self,value=None,left=None,right=None): self.value=value self.left=left #左子树 self.right=right #右子树 二叉树遍历的Python程序实现 三 04 遍历二叉树，代码如下: def preTraverse(root): #前序遍历 if root==None: return print(root.value) preTraverse(root.left) preTraverse(root.right) def midTraverse(root): #中序遍历 if root==None: return midTraverse(root.left) print(root.value) midTraverse(root.right) def afterTraverse(root): #后序遍历 if root==None: return afterTraverse(root.left) afterTraverse(root.right) print(root.value) 二叉树遍历的Python程序实现 三 05 给定节点信息，输出遍历结果，代码如下: if __name__=='__main__': root=Node('A',Node('B',Node('D'),Node('E')), Node('C',right=Node('F',Node('G')))) print('前序遍历：') preTraverse(root) print('中序遍历：') midTraverse(root) print('后序遍历：') afterTraverse(root) 二叉树遍历的Python程序实现 三 结果呈现 基于上述实践任务，完成程序体验和结果验证。 1. 运行程序，对比自己所写的遍历序列与程序输出的结果是否一致。 2. 修改程序中的节点信息，输出表达式树的各种遍历序列，完成结果验证。 课堂练习 四 只需知道数据之间相互链接的顺序 探讨与讨论 1.某二叉树的前序遍历为+*a-bc/df，中序遍历为a*b-c+d/f，下列说法正确的是（    ） A．该二叉树的叶子节点有2个 B．该二叉树为完全二叉树 C．该二叉树的后序遍历是abc-*df/+ D．若abcdf的值分别为3、2、5、6、3，则该表达式的运算结果为4 C 课堂练习 四 只需知道数据之间相互链接的顺序 探讨与讨论 2.已知某二叉树的后序遍历为GDBEHFCA，中序遍历为DGBAECHF，下列说法正确的是( ） A.该二叉树中叶子节点有3个 B.该二叉树的前序遍历为ABDGCEHF C.该二叉树是一棵完全二叉树，树的高度为4 D.该二叉树中度为1的节点有2个 A 课堂练习 四 只需知道数据之间相互链接的顺序 探讨与讨论 2.已知某二叉树的后序遍历为GDBEHFCA，中序遍历为DGBAECHF，下列说法正确的是( ） A.该二叉树中叶子节点有3个 B.该二叉树的前序遍历为ABDGCEHF C.该二叉树是一棵完全二叉树，树的高度为4 D.该二叉树中度为1的节点有2个 A 课堂练习 四 只需知道数据之间相互链接的顺序 探讨与讨论 3.某二叉树用一维数组来表示如表所示。该二叉树从根节点开始，按照从上到下，从左到右的顺序依次用A-H字母表示，该二叉树的中序遍历为( ) A 下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 元素 A B C D E   F     G         H A.DBGEACFH B.DBGEACHF C.DBEGACHF D.ABCDEFGH 叉树的基本操作 五 小 结 一、二叉树的建立 1.数组实现 （1）完全二叉树 （2）非完全二叉树 2.链表实现 3.拓展链接: 二叉树的list实现 三、 二叉树遍历的Python程序实现 二、二叉树的遍历 1.前序遍历 2.中序遍历 3.后序遍历 4.层序遍历 谢谢观看 第2节 二叉树的基本操作 浙教版（2019） 选修一 $$