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

(课件网) 课时2　二叉树的基本操作 第四章　树 1.掌握使用数组和链表等数据结构建立二叉树的方法。2.掌握二叉树遍历的基本操作方法。 目 录 CONTENTS 知识梳理 01 例题精析 02 随堂检测 03 巩固与提升 04 知识梳理 1 1.建立二叉树的方法 建立二叉树的操作方法为：按照二叉树层的顺序进行，先由第___层开始，依次到下一层，在每一层中按照从_____的顺序创建节点。 1 左到右 2.用数组实现二叉树的创建 (1)完全二叉树 ①从二叉树的_____开始，按_____、自左向右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为_____。 ②然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与_____一一对应。 (2)非完全二叉树 ①对于非完全二叉树，先将它补全为一棵_____二叉树，补上的节点及分支用虚线表示。 ②然后按照完全二叉树的方法，将节点存储在数组中。 根节点 从上到下 n－1　 数组的下标 完全 (3)使用数组(列表)建立二叉树 空树用None表示，非空二叉树用包含三个元素的列表[d，l，r]表示，分别存储着根节点的元素和左右子树，因此二叉树的list实现采用嵌套括号([])的形式。 用数组(列表)构建二叉树的代码如下： def create_tree(tree，data)： for i in range(len(data))： depth＝0 #程序的第0层相当于树的第1层 if i＝＝0: #根节点 　　　　 tree[depth]＝data[i] else： 　　　　 #while循环结束表示找到存放数据的节点(索引)位置 　　　while tree[depth] ！＝0： 　　　 　　　if data[i]>tree[depth]：　#往右寻找 　　　　　　　　depth＝depth*2＋2　#父节点的右孩子位置 　　　　　　else：　　　　#往左寻找 　　　　　　　　depth＝depth*2＋1　#父节点的左孩子位置 tree[depth]＝data[i]　#找到数据应存放的节点位置，并存储该节点 3.用链表实现二叉树的创建 二叉树用链表实现时，二叉树的节点至少需要三个域：一个_____和两个_____。如下图所示： lchild data rchild 其中lchild和rchild是指针域，存放指向节点的左孩子节点和右孩子节点的指针，data是数据域。 使用链表建立搜索二叉树如下： def insert(self，data)： if self.data：　　　#如果根节点不存在 if data