4.2二叉树的基本操作课件-2025-2026学年浙教版高中信息技术选修一

该高中信息技术课件聚焦二叉树的建立与遍历，通过复习完全二叉树与非完全二叉树概念搭建学习支架，衔接数组、链表实现方法及前序、中序、后序遍历操作，构建完整知识脉络。 其亮点在于以问题驱动结合实例分析，通过评估数组与链表存储优劣培养信息意识，借助遍历规则简记法和表达式转换实例落实计算思维，课后Python实践任务促进数字化学习与创新。结构化小结与分层练习设计，助力学生提升问题解决能力，也为教师提供清晰教学路径。

4.2 二叉树的基本操作 年 级：高二年级 学 科：信息技术（浙教版） 主讲人：邓琳 学 校：湖南省隆回县第一中学 页面统一为16:9宽幅画面比例尺寸；PPT统一格式为PPT或PPTX。 中文： 1. 课名：微软雅黑48号字； 2.（第一课时）：微软雅黑32号字； 3.学校名称：请填写全称； 4.学科、年级、主讲人、学校：华文楷体28号字（具体根据文字量可适当调整）。 英文 1.课名：字体以Times New Roman为主，字号一般使用32—36号，特别强调可以用40号； 2.（Period 1）：字体使用Arial，字号为28； 3.正文一般用24—28号，特别强调可用32号。 注意标点的规范（例如：中文省略号为……，可用Shift+数字键6打出中文省略号，英文省略号为…） 1 4.2 二叉树的基本操作 年 级：高二年级 学 科：信息技术（浙教版） 主讲人：邓琳 学 校：湖南省隆回县第一中学 页面统一为16:9宽幅画面比例尺寸；PPT统一格式为PPT或PPTX。 中文： 1. 课名：微软雅黑48号字； 2.（第一课时）：微软雅黑32号字； 3.学校名称：请填写全称； 4.学科、年级、主讲人、学校：华文楷体28号字（具体根据文字量可适当调整）。 英文 1.课名：字体以Times New Roman为主，字号一般使用32—36号，特别强调可以用40号； 2.（Period 1）：字体使用Arial，字号为28； 3.正文一般用24—28号，特别强调可用32号。 注意标点的规范（例如：中文省略号为……，可用Shift+数字键6打出中文省略号，英文省略号为…） 2 A B C D E F (1)完全二叉树 A C F G (2)非完全二叉树 知识回顾 完全二叉树：按层从左到右排，不跳任何一个节点； 非完全二叉树：没按这个规矩，存在“跳节点”的情况。 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 3 无论是线性结构还是非线性结构数据，都需要对数据元素逐个进行组织存储和处理。 与之对应的二叉树的基本操作，主要包括二叉树的建立和遍历等。 课程目标 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 4 二叉树的建立--数组实现 A B C D E 0 1 2 3 4 5 6 7 (1)完全二叉树 从根节点开始，按从上而下，自左往右的顺序对n个节点进行编号，根节点编号为0，最后一个节点的编号为n-1。然后将节点用一组连续的数组元素来表示，节点编号与数组下标一一对应。 1 0 2 3 4 A B C D E 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 5 二叉树的建立--数组实现 (2)非完全二叉树 先将它补全为一棵完全二叉树，再按照完全二叉树的形式自上而下、自左向右的顺序对二叉树进行编号，然后依次把原二叉树节点用数组元素来表示，节点编号与数组下标一一对应。 A B 1 0 2 4 C 3 5 6 0 1 2 3 4 5 6 7 A B C 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 6 思考：用数组表示二叉树，在存储过程中是否可取？ 对于完全二叉树而言，一维数组的表示方式既简单又节省存储空间。 但对于一般的二叉树来说，采用一维数组表示时，结构虽然简单，却容易造成存储空间的浪费。 如图4.2.2甲所示，一个深度为k且只有k个节点的树需要如乙图所示2^k-1个节点的存储空间才能表示出来。 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 7 二叉树的建立--链表实现 二叉树也可以采用链表来实现，用任意一组存储单元来存储二叉树的节点，用指向节点的指针来表示节点之间的关系。 用链表表示二叉树，至少需要3个域：一个数据域和两个指针域，两个指针域分别指向节点的左子树和右子树。 左指针 数据 右指针 数据 指针 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 8 二叉树的建立--链表实现 左指针 数据 右指针 A B ^ C ^ ^ D ^ E ^ F ^ ^ G ^ 头指针 A B C D E F G 用链表表示二叉树，其两个指针域分别指向节点的左子树和右子树。 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 9 A B C D E F G 课堂小练 某棵二叉树用数组存储后如图所示： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G 则节点D的右孩子节点为： A.空 B.E C.F 0 1 2 4 3 6 5 8 7 10 9 D.G 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 10 二叉树的遍历 概念：按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。 根 左子树 右子树 前/中/后序遍历：基于树的递归特性确定的次序规则 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 11 规则：若二叉树为空，则空操作返回；否则， 先访问根节点，再访问左子树，最后访问右子树。 二叉树的遍历--前序遍历 A B C 前序遍历顺序为：根左右 ① ② ③ A B C 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 12 二叉树的遍历--前序遍历 A B C D E F G H ① ② ③ ⑤ ④ ⑥ ⑦ 前序遍历顺序为： A 规则简记：先根再左最后右 -B -D -E -H -C -F -G 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 13 规则：若二叉树为空，则空操作返回；否则， 先访问左子树，再访问根节点，最后访问右子树。 二叉树的遍历--中序遍历 A B C 中序遍历顺序为：左根右 ① ② ③ B A C 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 14 二叉树的遍历--中序遍历 A B C D E F G H ① 中序遍历顺序为： ② ③ ④ ⑤ ⑥ ⑦ D -B -H -E -A -F -C -G 规则简记：先左再根最后右 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 15 规则：若二叉树为空，则空操作返回；否则， 先访问左子树，再访问右子树，最后访问根节点。 二叉树的遍历--后序遍历 A B C 后序遍历顺序为：左右根 ① ② ③ B C A 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 16 二叉树的遍历--后序遍历 A B C D E F G H ① 后序遍历顺序为： ② ③ ④ ⑤ ⑥ ⑦ 规则简记：先左再右最后根 D -H -E -B -F -G -C -A 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 17 + * 4 2 - 3 8 课堂小练 中序遍历（左根右）得到： 8 * ( 3 - 2 ) + 4 后序遍历（左右根）得到： 8 3 2 - * 4 + 数学表达式，也称为中缀表达式 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 18 思考：已知前序和后序遍历序列，能否唯一确定一棵二叉树？ A B A B 不能，比如说前序遍历AB和后序遍历BA，我们就可以生成两棵树。如上图所示。 当二叉树中某个节点仅仅只有一个子树节点的时候，其前序和后序遍历序列不能具体确定是左右子树的那一个。 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 19 课堂小结 二叉树的建立 具体内容 数组实现 - 完全二叉树：从根节点开始，一层层从左至右依次编号 - 非完全二叉树：补全为完全二叉树后编号 链表实现 通过指针/引用连接节点，每个节点包含数据域和左右子树指针 二叉树的遍历 访问顺序 前序遍历 根节点 → 左子树 → 右子树（根左右） 中序遍历 左子树 → 根节点 → 右子树（左根右） 后序遍历 左子树 → 右子树 → 根节点（左右根） 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 20 思考如何利用Python实现二叉树的建立和遍历？下节实践课进行程序编写与调试运行。 课后作业 请注意： 1.正文标题为：黑体，30号字； 2.正文内容为：华文楷体，尽量不小于24号，特殊辅助性文字不低于18；根据文字量可适当调整。内容文字一行一般不能超过28个字，单页文字一般不能超过8行。 3.拍摄版本呈现内容务必与上传版本呈现的内容完全一致。 英文 1.正文标题为：以Times New Roman为主,可搭配使用Arial。字号为32—36号，特别强调可以用40号。 2.正文内容为：以Times New Roman为主,可搭配使用Arial。字号为24—28号，特别强调可用32号。 3.英文每行一般不能超过15个单词；单页文字一般不能超过8行。 21 $