信息技术选修1 数据与数据结构3.构建二叉树获奖ppt课件

第四单元 二叉树

项目七 探究计算机中算术表达式的计算

——了解二叉树及其基本操作

第三课时 构建二叉树

❑教材分析

本节的主要内容是探究计算机中算术表达式的计算原理。以探究计算机中算术表达式的计算原理为主线，整个项目分为探究计算机中算术表达式的计算原理、探究为何二叉树能将算术表达式转换为后缀表达式、构建二叉树三部分。本节课时是通过问题“如何能得到上述二叉树呢”引出表达式二叉树的构建。通过这一项目的学习，结合实例分析，了解了二叉树的概念和基本操作，进一步培养学生的计算思维。

❑教学目标

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）栈操作示意图：