中小学教育资源及组卷应用平台
第四单元 二叉树
项目七 探究计算机中算术表达式的计算
——了解二叉树及其基本操作
第三课时 构建二叉树
教材分析
本节的主要内容是探究计算机中算术表达式的计算原理。以探究计算机中算术表达式的计算原理为主线，整个项目分为探究计算机中算术表达式的计算原理、探究为何二叉树能将算术表达式转换为后缀表达式、构建二叉树三部分。本节课时是通过问题“如何能得到上述二叉树呢”引出表达式二叉树的构建。通过这一项目的学习，结合实例分析，了解了二叉树的概念和基本操作，进一步培养学生的计算思维。
教学目标
1.了解构建二叉树的方法，学会构建表达式二叉树；
2.培养学生的信息意识和计算思维能力。
教学重点
1.了解构建二叉树的方法，学会构建表达式二叉树；
教学难点
1.了解构建二叉树的方法，学会构建表达式二叉树；
2.培养学生的信息意识和计算思维能力。
教学方法
体验法、讲授法、讨论法、示例法
教学准备
计算机教室、多媒体设备、多媒体广播软件、教学课件等。
教学过程
一、新课导入
回顾并提出问题：“我们已经了解了二叉树的基本操作，掌握了利用二叉树将算术表达式转换为方便计算机处理的后缀表达式的方法。那么二叉树又是如何构建的呢？"
二、构建叉树
如何能得到上述二叉树呢？算术表达式的运算符都是一元运算符，即每个运算符对应两个运算对象。先前说到按中序遍历得到的中缀表达式最贴近于算术表达式，因此，将运算符作为根结点，运算符前的运算对象作为左子树，运算符后的运算对象作为右子树(运算对象也可以是算术表达式来构建二叉树。按中序遍历的方式访问该二叉树，正好能得到中缀表达式，如图4-5所示
图4-5 a+b的表达式二叉树
按照此规则，对于算术表达式3*(4+5)-7,我们把优先级最低的运算符“_”作为根结点，两边的运算对象作为左子树和右子树。对于左边的运算对象即表达式3*(4+5)，可以按同样规则来构建左子树，以此类推，最终建立如图4-6所示的表达式一叉树。对于这一表达式二叉树进行后序遍历可以得到后缀表达式。
图4-6表达式二叉树
思考与讨论？
先序遍历得到的表达式称为前级表达式，前缀表达式是否和后缀表达式一样能用栈完成计算呢？
前缀表达式和后缀表达式一样能用栈完成计算。
与后缀表达式相反，前缀表达式的计算要从后往前遍历，其运算方式为：从右到左读取前缀表达式，如果当前字符为变量或者为数字，则进栈；如果是运算符，则将栈顶两个元素(运算对象)弹出作相应运算，结果再进栈，重复上述过程，直至表达式读取完，栈里就剩下最终结果。
三、课堂活动
对于算术表达式5*7+8*(4-2)，请为其构建表达式二叉树，并通过后序遍历的方式，将算术表达式转换成后缀表达式，然后用入栈和进栈操作来计算结果，画出表达式二叉树和栈操作示意图。
参考答案：
（1）表达式二叉树如图所示：
（2）后序遍历的过程如图所示：
得到的后缀表达式：57*842-*+
（3）栈操作示意图：
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
HYPERLINK "http://21世纪教育网(www.21cnjy.com)
" 21世纪教育网(www.21cnjy.com)(共23张PPT)
第三课时 构建二叉树
信息技术沪教版 选择性必修1
第四单元 二叉树
项目七 探究计算机中算术表达式的计算
——了解二叉树及其基本操作
一、新课导入
二、构建叉树
三、课堂活动
一、新课导入
二叉树的基本操作主要有二叉树的创建、二叉树的遍历、求二叉树的深度等。其中二叉树的遍历方法主要有以下几种。
①先序遍历：先访问二叉树根结点，然后先序遍历左子树，再先序遍历右子树。
②中序遍历：先中序遍历左子树，然后访问二叉树根结点，再中序遍历右子树。
③后序遍历：先后序遍历左子树，再后序遍历右子树，最后访问二叉树根结点。
④层次遍历：对二叉树从上到下，逐层从左到右访问每个结点。
前三种属于深度优先遍历，而层次遍历属于广度优先遍历，具体示例如图所示
先序遍历序列为：ABCDEGF
中序遍历序列为：CBECDFA
后序遍历序列为：CCEFDBA
层次遍历序列为：ABCDEFG
先访问根结点“－”的左子树，由于该左子树的根结点“*”也有自己的左子树即结点3，而结点3并无左子树，所以最先访问的是结点3，继而是“*”……最后访问的是根结点“－”的右子树，即结点7。
通过以上规则访问结点后，便可以得到3*4＋5－7的序列。这样的序列称为中缀表达式，中缀表达式的运算符都位于运算对象的中间。中缀表达式的顺序是和算术表达式一致的，只是缺了括号。
二、构建叉树
算术表达式的运算符都是一元运算符，即每个运算符对应两个运算对象。先前说到按中序遍历得到的中缀表达式最贴近于算术表达式，因此，将运算符作为根结点，运算符前的运算对象作为左子树，运算符后的运算对象作为右子树(运算对象也可以是算术表达式来构建二叉树。按中序遍历的方式访问该二叉树，正好能得到中缀表达式，如图所示。
a+b的表达式二叉树
按照此规则，对于算术表达式3*(4+5)-7,我们把优先级最低的运算符“-”作为根结点，两边的运算对象作为左子树和右子树。对于左边的运算对象即表达式3*(4+5)，可以按同样规则来构建左子树，以此类推，最终建立如图所示的表达式一叉树。对于这一表达式二叉树进行后序遍历可以得到后缀表达式。
表达式二叉树
思考与讨论？
先序遍历得到的表达式称为前级表达式，前缀表达式是否和后缀表达式一样能用栈完成计算呢？
思考与讨论？
前缀表达式和后缀表达式一样能用栈完成计算。
与后缀表达式相反，前缀表达式的计算要从后往前遍历，其运算方式为：从右到左读取前缀表达式，如果当前字符为变量或者为数字，则进栈；如果是运算符，则将栈顶两个元素(运算对象)弹出作相应运算，结果再进栈，重复上述过程，直至表达式读取完，栈里就剩下最终结果。
三、课堂活动
对于算术表达式5*7+8*(4-2)，请为其构建表达式二叉树，并通过后序遍历的方式，将算术表达式转换成后缀表达式，然后用入栈和进栈操作来计算结果，画出表达式二叉树和栈操作示意图。
（1）表达式二叉树如图所示：
（2）后序遍历的过程如图所示：
得到的后缀表达式：５７*８４２-*+
（3）栈操作示意图：
（3）栈操作示意图：
（3）栈操作示意图：
（3）栈操作示意图：
谢谢
21世纪教育网（www.21cnjy.com) 中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php
