浙教版信息技术高中选修1 数据与数据结构4.2 二叉树的基本操作-教学课件.pptxVIP

二叉树的基本操作浙教版信息科技

利用”贪吃蛇“游戏思想来解决本节难点部分”二叉树的遍历“

二叉树的遍历二叉树的建立二叉树的实践与体验

二叉树的遍历二叉树的建立实践与体验二叉树的遍历二叉树的建立二叉树的实践与体验

按照层的顺序进行，先由第1层开始，依次到下一层，在每一层中按照从左到右的顺序创建节点。建立方法数组链表数据结构类型二叉树的遍历二叉树的建立实践与体验方法与结构

二叉树的遍历二叉树的建立实践与体验数组实现-完全二叉树任务一：1.阅读课本第97页，用数组示意图方式完成右图（任务单图1.1）“完全二叉树”的表示。下标0123456789元素ABCDEFGHIJ

二叉树的遍历二叉树的建立实践与体验数组实现-非完全二叉树深度为K且只有k个节点需要2k-1个节点存储空间乙补全后的二叉树丙数组实现示意图甲原二叉树存储空间

二叉树的遍历二叉树的建立实践与体验数组实现-非完全二叉树任务一：2.用数组表示示意图方式完成右图（任务单图1.2）“非完全二叉树”的表示。下标0123456789元素ABCDG

二叉树的遍历二叉树的建立实践与体验链表实现二叉树的链表实现示意图两个指针域分别指向节点的左孩子和右孩子，这两个指针分别称为左指针和右指针。二叉树的节点至少需要3个域：一个数据域和两个指针域

二叉树的遍历二叉树的建立二叉树的实践与体验二叉树的遍历二叉树的建立实践与体验

二叉树的遍历实践与体验简要概述对二叉树的各个节点进行访问，即遍历二叉树遍历：是指按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。前序遍历中序遍历后序遍历二叉树的建立

二叉树的遍历二叉树的建立实践与体验前序遍历前序遍历的规则是：若二叉树为空，则空操作返回；否则，先访问根节点，再访问左子树，最后访问右子树总结：根-左-右如图所示，得到的前序遍历顺序为：A-B-D-H-E-C-F-I-G-J-K

二叉树的遍历二叉树的建立实践与体验前序遍历任务二：1.根据“贪吃蛇”游戏原理与前序遍历的规则，请同学们尝试画出二叉树的“贪吃蛇”的行进路线，并把路线中遇到的节点写下来。（完成任务单图2.1的二叉树前序遍历）

二叉树的遍历二叉树的建立实践与体验前序遍历任务二：1.根据“贪吃蛇”游戏原理与前序遍历的规则思考提示：1.根据游戏原理与前序规则，生成的点，是否可以随机生成？2.如果不是随机生成的点，那么生成的点的位置应该统一哪里？

二叉树的遍历二叉树的建立实践与体验前序遍历任务二：1.根据“贪吃蛇”游戏原理与前序遍历的规则思考提示：1.根据游戏原理与前序规则，生成的点，是否可以随机生成？2.如果不是随机生成的点，那么生成的点的位置应该统一哪里？规律：在所有节点的左侧画点，之后从根节点开始，依次沿着节点进行划线，并将遇到的点所对应的节点写下来，即为前序遍历结果。“贪吃蛇”遇到的节点顺序为：A-B-D-H-E-C-F-I-G-J-K

二叉树的遍历二叉树的建立实践与体验中，后序遍历中序遍历的规则是：若二叉树为空，则空操作返回；否则，先访问左子树，再访问根节点，最后访问右子树总结：左-根-右后序遍历的规则是：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树,最后访问根节点总结：左-右-根

二叉树的遍历二叉树的建立实践与体验中，后序遍历任务二：2.根据前序遍历的“贪吃蛇”画法与规律，尝试探究二叉树的中序和后序遍历画法。（完成任务单图2.2和2.3的二叉树中序和后序遍历）

二叉树的遍历二叉树的建立实践与体验中序遍历中序遍历的规则是：若二叉树为空，则空操作返回；否则，先访问左子树，再访问根节点，最后访问右子树总结：左-根-右“贪吃蛇”遇到的节点顺序为：D-H-B-E-A-I-F-C-J-G-K规律：在所有节点的下侧画点，之后从根节点开始，依次沿着节点进行划线，并将遇到的点所对应的节点写下来，即为中序遍历结果。

二叉树的遍历二叉树的建立实践与体验后序遍历后序遍历的规则是：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树,最后访问根节点总结：左-右-根“贪吃蛇”遇到的节点顺序为：H-D-E-B-I-F-J-K-G-C-A规律：在所有节点的右侧画点，之后从根节点开始，依次沿着节点进行划线，并将遇到的点所对应的节点写下来，即为后序遍历结果。

二叉树的遍历二叉树的建立实践与体验遍历总结前序遍历：在节点的左侧画点中序遍历：