高中信息技术沪教版（2019）选修1 数据与数据结构2.探究为何二叉树能将算术表达式转换为后缀表达式一等奖课件ppt

这是一份高中信息技术沪教版（2019）选修1 数据与数据结构2.探究为何二叉树能将算术表达式转换为后缀表达式一等奖课件ppt，文件包含项目七第二课时pptx、项目七第二课时doc等2份课件配套教学资源，其中PPT共41页， 欢迎下载使用。
第四单元 二叉树项目七 探究计算机中算术表达式的计算——了解二叉树及其基本操作第二课时 探究为何二叉树能将算术表达式转换为后缀表达式 ❑教材分析本节的主要内容是探究计算机中算术表达式的计算原理。以探究计算机中算术表达式的计算原理为主线，整个项目分为探究计算机中算术表达式的计算原理、探究为何二叉树能将算术表达式转换为后缀表达式、构建二叉树三部分。本节课时是让学生探究为何二叉树能将算术表达式转换为后缀表达式，并适时引出二叉树的概念及相关操作（遍历），学生最终得出通过后序编历表达式二叉树，就能得到后缀表达式的结论。通过这一项目的学习，进一步培养学生的计算思维。❑教学目标1.了解二叉树的概念；2.了解二叉树的先序遍历、中序遍历、后序遍历等基本操作；3.了解从二叉树得到后缀表达式的方法；4.了解计算机完成后缀表达式的运算的过程；5.培养学生的信息意识和计算思维能力。❑教学重点1.了解二叉树的概念；2.了解二叉树的先序遍历、中序遍历、后序遍历等基本操作；3.了解从二叉树得到后缀表达式的方法；❑教学难点1.二叉树的先序遍历、中序遍历、后序遍历等基本操作；2.二叉树得到后缀表达式的方法3.培养学生的信息意识和计算思维能力。❑教学方法体验法、讲授法、讨论法、示例法❑教学准备　　计算机教室、多媒体设备、多媒体广播软件、教学课件等。❑教学过程一、新课导入讲解树、二叉树的概念及相关术语。1.树树是一种重要的非线性数据结构，直观地看，它是数据元素(在树中称为结点)按分支关系组织起来的结构，与自然界中的树很像。日常生活中很多事物可以用树形图来表示，如家族图谱、行政管理架构等，如图所示。    在数据结构中，树(tree)是n(n>=0)个结点的有限集合T,T为空时称为空树，否则它满足如下两个条件：(1)有且仅有一个特定的称为根的结点，如右图中的结点A;(2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3,…T,其中每个子集又是一棵树，并称其为子树( subtree),如图4-9中的子树T1,T2,T3。2.二叉树二叉树是由n个结点的有限集合构成，n=0称为空二叉树，n>0时由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树是由n(n>=0)个结点的有限集合构成，n=0称为空二叉树，n>0时由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树，如图4-10所示。(1)树根(或称根结点)：没有前驱的结点称为树根，一棵非空二叉树有且仅有一个树根，如图中的结点A。(2)结点的度：结点的后继数。如图中结点A的度为2,结点C的度为1,结点F的度为0。(3)分支点：有后继的结点，也称内结点，即结点的度不为零，如结点B和结点C。(4)树叶(或称叶结点)：无后继的结点，也称终端结点，即结点的度为零，如结点D、E、F。(5)树的深度：树的层次数。上图中二叉树为三层根结点为第一层，结点B、C为第二层，结点D、E、F为第三层。(6)左孩子：直接左后继结点，如结点D是结点B左孩子；右孩子：直接右后继结点，如结点E是结点B的右孩子。(7)双亲结点：直接前驱结点，如结点C是结点F的父结点。二叉树的抽象数据类型表示如下：ADT Binary Tree:数据对象：具有相同特性的数据元素集合。数据关系：数据元素集合中仅有一个结点无前驱元素(根)；其余结点有且仅有一个前驱结点，每个结点最多有两个后继结点且有左右之分；每个结点到根都存在一个线性序列。基本操作：def_init_(self)  #初始化一棵空二叉树def BTEmpty(self)  #若二叉树为空，则返回True,否则返回Falsedef Root(self)  #返回树根def Value(self,e)   #返回e结点的值def Depth(self) #返回树的深度def Parent(self,e) #返回e的双亲def Leftechild(self,e)  #返回e的左孩子def Rightchild(self,e) #返回e的右孩子def PreOrderTraverse(self,e) #先序遍历二叉树def inOrderTraverse(self)  #中序遍历二叉树def PostOrderTraverse(self) #后序遍历二叉树 二、探究为何二叉树能将算术表达式转换为后级表达式如何能将算术表达式转换为后缀表达式呢？有一种方法是使用二叉树(binary tree)来转换。二叉树是有一个根结点(无前驱)，每个树权都最多只有两个分支的树(可以是0个、1个或2个)，根结点左边的分支称为左子树、右边的分支称为右子树。结点的后继结点为左孩子和右孩子，没有分支的结点称为叶结点。树枝的方向都是往下的，箭头省略，如图4-2所示。图4-2 二叉树示例图中所示的左子树和右子树是根结点A的左子树和右子树，在左子树中，结点B可以看成是该子树的根结点。而叶结点D和可以看成是结点B的左子树和右子树(只有个结点的子树)，也是左孩子和右孩子。 思考与讨论？结点C有左子树和右子树吗？只有右子树。左子树和右子树是有顺序的，节点C右边的分支称为右子树。 了解了二叉树后，依据某一规则对二叉树的结点依次进行访问，就可以得到一个序列。假设有图4-3所示二叉树我们采用先访问其左子树，然后访问根结点，再访问右子树的规则(所有子树也按此规则进行访问)。图4-3按序访问二叉树结点具体就是先访问根结点“－”的左子树，由于该左子树的根结点“*”也有自己的左子树即结点3，而结点3并无左子树，所以最先访问的是结点3，继而是“*”……最后访问的是根结点“－”的右子树，即结点7。通过以上规则访问结点后，便可以得到3*4＋5－7的序列。这样的序列称为中缀表达式，中缀表达式的运算符都位于运算对象的中间。中缀表达式的顺序是和算术表达式一致的，只是缺了括号。上述访问规则称为二叉树的中序遍历，可以看出，中序遍历的序列对应了中缀表达式。思考与讨论？1.如果没有结点3,最先访问的是哪个结点？节点*。2.如果结点7有左孩子，最后访问的是哪个结点？节点7。3.如何可以在中序遍历后得到带括号的算术表达式？二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于缺少了括号。要将二叉树表示的表达式还原成原表达式，只需当根节点运算符优先级高于左子树(或右子树)根节点运算符时，给左子树(或右子树)的中序序列加上括号即可。与中序遍历相应的还有先序遍历和后序遍历。先序遍历是先访问根结点，再访问左子树，最后访间右子树(对于所有子树也采用此规则遍历)，如图4-4所示图4-4先序遍历可以看出，先序遍历第一个访问的一定是根结点。后序遍历是先访问左子树，再访问右子树，最后访问根结点(对于子树也采用此规则遍历)。而上图所示二叉树的后序遍历得到的序列恰好对应了后缀表达式345+*7-。 三、叉树的常用基本操作二叉树的基本操作主要有二叉树的创建、二叉树的遍历、求二叉树的深度等。其中二叉树的遍历方法主要有以下几种。①先序遍历：先访问二叉树根结点，然后先序遍历左子树，再先序遍历右子树。②中序遍历：先中序遍历左子树，然后访问二叉树根结点，再中序遍历右子树。③后序遍历：先后序遍历左子树，再后序遍历右子树，最后访问二叉树根结点。④层次遍历：对二叉树从上到下，逐层从左到右访问每个结点。前三种属于深度优先遍历，而层次遍历属于广度优先遍历，具体示例如图4-11所示先序遍历序列为：ABCDEGF中序遍历序列为：CBECDFA后序遍历序列为：CCEFDBA层次遍历序列为：ABCDEFG图4-11遍历示例  四、课堂活动参照先序遍历和中序遍历的方式，画出上述表达式二叉树的后序遍历得出后缀表达式的过程。参考答案：后序遍历的过程如图所示：得到的后缀表达式：345+*7-