《数据结构[Python语言描述]》教案第11课树和二叉树（6.3）.docx

课题第11课树和二叉树(6.3)课时2课时(90min)教学目标知识目标：掌握二叉树的遍历方法，以及线索二叉树的线索化技能目标：能根据先序、中序和后序遍历方法快速得到二叉树的遍历序列素质目标：培养勇于探索、知难而进、追求卓越的创新精神教学重难点教学重点：二叉树的遍历方法、线索二叉树的线索化教学难点：二叉树的遍历方法、线索二叉树的线索化教学方法问答法、讨论法、i并授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：为什么要遍历二叉树？【学生】思考、举手回答传授新知【教师】通过学生的回答引入要讲的知识，介绍遍历二叉树、确定二叉树、线索二叉树6.3遍历二叉树和线索二叉树6.3.1 遍历二叉树遍历二叉树是指按照一定的次序访问二叉树中的所有结点，且每个结点仅被访问一次。由二叉树的定义可知，任意一棵非空二叉树均由根结点、左子树和右子树三部分组成，因此，只要遍历这三部分就能遍历整棵二叉树.二叉树的遍历方法有4种，分别为先序遍历、中序遍历、后序遍历和层次遍历。1.先序遍历对于非空二叉树，先序遍历的递归算法步骤如下.(1)访问根结点。(2)先序遍历根结点的左子树。(3)先序遍历根结点的右子树。【提示】遍历过程其实是一个递归过程,遍历任何一棵子树时仍然是先访问子树的根结点，然后遍历子树根结点的左子树，最后遍历子树根结点的右子树。【算法描述】defPreOrderTraverse(self,node):ifnodeisnotNone:#结点不为空print(node.data,end=,)#访问才艮结点self.preOrderTraverse(node.Ichild)#先序遍历根结点的左子树self.preOrderTraverse(node.rchild)#先序遍历才艮结点的右子树÷【教师】用多媒体展示“先序遍历二叉树”图(详见教材)，并介绍先序遍历二叉树的过程(1)先访问根结点A,再遍历其左子树和右子树。(2)遍历根结点A的左子树，也就是遍历以B为根结点的二叉树.因此，按照先序遍历步骤，先访问根结点B,再遍历其左子树和右子树。(3)遍历根结点B的左子树,也就是遍历以D为根结点的二叉树。因此，按照先序遍历步骤，先访问根结点D,再遍历其左子树和右子树.(4)-(18)洋见教材2.中序遍历对于非空二叉树，中序遍历的递归算法步骤如下。(1)中序遍历根结点的左子树。(2)访问根结点。(3)中序遍历根结点的右子树。【算法描述】defInOrderTraverse(self,node):if node is not None:#结点不为空#中序遍历根结点的左子树#访问根结点#中序遍历根结点的右子树self.InOrderTraverse(node.Ichild)print(node.data,end='')self.InOrderTraverse(node.rchild)÷【教师】用多媒体展示“中序遍历二叉树”图(详见教材)，并介绍中序遍历二叉树的过程3.后序对于非空二叉树，后序遍历的递归算法步骤如下。(1)后序遍历根结点的左子树。(2)后序遍历根结点的右子树。(3)访问根结点。【算法描述】defPostOrderTraverse(self,node):ifnodeisnotNone:#名吉点、不为空self.postOrderTraverse(node.!child)#后序才由吉点的左子才可self.postOrderTraverse(node.rchild)#后序iZ¾才影言点的右子才可#访问根结点print(node.data,end=*,)÷【教师】用多媒体展示“后序遍历二叉树”图(详见教材)，并介绍后序遍历二叉树的过程4.层次遍历对于非空二叉树，层次遍历的算法步骤如下。(1)访问根结点(第1层)。(2)从左到右依次访问第2层的所有结点。(3)从左到右依次访问第3层的所有结点第h层的所有结点。【算法描述】defIevelOrderTraverse(Self):#结点不为空#当前层结点 当前层存在结点时 处理每一层结点左孩子结点不为空#访问左孩子结点 右孩子结点不为空#访问右孩子结点ifself.rootisnotNone:queue=self.rootwhilequeue:cur_node=queue.pop(0)print(cur_node.elemzend=,1)ifcur_node.!childisnotNone:#queue.append(cur_node.Ichild)ifcur_node.rchildisnotNone:#queue.append(cur_node.rchild)*【教师】用多媒体展示“层次遍历二叉树”图（详见教材），并介绍层次遍历二叉树的过程6.3.2确定二叉树【教师】随机邀请学生回答以下问题如何确定二叉树？【学生】聆听、思考、回答1.由先序和中序遍历序列确定二叉树由先序和中序遍历序列确定二叉树的过程如下.（1）根据二叉树的先序遍历步骤可知，在先序遍历序列中，第一个结点一定是二叉树的根结点。（2）根据二叉树的中序遍历步骤可知，根结点（先序遍历序列的第一个结点）会将中序遍历序列分为两个子序列，第一个子序列（左中序）是根结点的左子树的中序遍历序列，第二个子序列（右中序）是根结点的右子树的中序遍历序根据这两个子序列，可以在先序遍历序列中找到对应的左子序列（左先序）和右子序列（右先序）.（3）在先序遍历序列中，左子序列（左先序）的第一个结点是左子树的根结点，右子筋（K右先序）的第一个结点是右子树的根结点。至此，就确定了根结点、左子树根结点和右子树根结点。（4）根据得到的左子树和右子树的根结点，重复上述步骤。按照这样的方式进行递归，当所有结点都取完时，即可确定二叉树。【教师】用多媒体展示“由先序和中序遍历序列确定二叉树”图（详见教材），并介绍由先序和中序遍历序列确定二叉树的过程2.由后序和中序遍历序列确定二叉树【教师】随机邀请学生回答以下问题结合由先序和中序遍历序列确定二叉树的过程,试着说一下如何由后序和中序遍历序列确定二叉树.*【学生】聆听、思考、回答由后序和中序遍历序列确定二叉树的过程如下。（1）根据二叉树的后序遍历步骤可知，在后序遍历序列中，最后一个结点一定是二叉树的根结点。（2）根据二叉树的中序遍历步骤可知，根结点（后序遍历序列的最后一个结点）会将中序遍历序列分为两个子序列，第一个子序列（左中序）是根结点的左子树的中序遍历序列，第二个子序列（右中序）是根结点的右子树的中序遍历序列。根据这两个子序列，可以在后序遍历序列中找到对应的左子序列（左后序）和右子序列（右后序）.（3）在后序遍历序列中，左子序列（左后序）的最后一个结点是左子树的根结点，右子序列（右后序）的最后一个结点是右子树的根结点。这样，就确定了根结点、左子树根结点和右子树根结点。(4)根据得到的左子树根结点和右子树根结点，重复上述步骤。按照这样的方式进行递归，当所有结点都取完时，即可确定二叉树。÷【教师】用多媒体展示“由后序和中序遍历序列确定二叉树”图(详见教材)，并介绍由后序和中序遍历序列确定二叉树的过程【提示】已知二叉树的先序遍历序列和后序遍历序列，是不能唯一确定一棵二叉树的，这是因为根据已知条件无法确定二叉树的左子树和右子树.÷【教师】讲解实例6-3(详见教材)6.3.3线索二叉树1.线索二叉树的定义对于具有n个结点的二叉树，其二叉链表中有2n个指针域，由于只有个结点被指针所指向(n个结点中只有根结点无指针指向)，则必有2-(-1尸+1个空指针域。因此，可利用这+1个空指针域存放该结点的前驱结点和后继结点信息，其余-1个指针域仍然存放该结点的左孩子结点和右孩子结点信息©÷【教师】随机邀请学生回答以下问题线索二叉树和二叉树的区别是什么7÷【学生】聆听、思考、回答在二叉树的二叉链表存储结构中，只存储了结点的数据信息和其左、右孩子结点信息，并不能直接从中得到结点在线性序列中的前驱结点和后继结点信息。为此，可采用的方法是利用二叉链表中的空指针域来存放遍历过程中结点的前驱结点和后继结点信息。为区分指针域中是孩子结点还是前驱结点或后继结点，须在每个结点中增加两个标志域(Itag和nag)÷【教师】用多媒体展示“增加标志域后的结点结构”图，并介绍其结构特点!childItagdatartagrchild其中，Itag和rtag的具体含义如下。(1)Itag为()时，表示Ichild域指向结点的左孩子结点；IIag为1时，表示Ichild域指向结点的前驱结点。(2)rtag为。时，表示rchild域指向结点的右孩子结点；rtag为1时，表示rchild域指向结点的后继结点。在这种存储结构中，指向前驱结点和后继结点的指针称为线索，加了线索的二叉树称为线索二叉树，对二叉树按照某种方法进行遍历并加上线索的过程称为线索化。线索二叉树的链式存储中结点的定义如下。classTHNode:definit_(self,data):#构造方法self.data=data#data域self.!child=None#IChild域self.rchild=None#rchildself.Itag=O#Itag域self.rtag=O#rtag域2 .二叉树的线索化二叉树的线索化实际上就是在进行某种遍历时，将二叉链表中的空指针域修改为指向相应结点的前驱结点或后继结点的过程。对二叉树按照不同的遍历方法进行线索化，可以得到不同的线索二叉树.*【教师】用多媒体展示“线索二叉树”图(详见教材)，并介绍二叉树线索化过程【提示】二叉树在进行线索化时，须注意3点：一是确定二叉树的遍历次序；二是确定需要前驱线索化、后继线索化还是两者皆有；三是只有空指针才能加线索.为方便操作，须在线索二叉树中增加一个头结点，头结点的data域为空，Ichild域指向二叉树的根结点Jtag为0Jrchild域指向遍历序列的尾结点frtag为1。同时,令二叉树遍历序列中第一个结点的Ichild域和最后一个结点的rchild域均指向头结点。3 .遍历线索二叉树在线索二叉树中，查找结点的前驱结点或后继结点非常简单。以中序线索二叉树为例，遍历线索二叉树的过程如下,(1)求中序遍历序列的开始结点，即根结点的最左下结点。(2)如果T结点p的rchild指针为线索，则rchild所指向的就是该结点的后继结点，否则该结点的后继结点就是其右子树的最左下结点。【算法描述】defin_OrderThread(self,node):#遍历中序线索二叉树ifnodeisnotNone:p=nodewhilep:whilep.Itag=0:#找中序遍历序列的开始结点p=p.Ichildprint(p.data,end=,)#访问结点whilep.rchildisnotself.rootandp.rtag=1:#如果是线索，则rchild所指向的就是其后继结点p=p.rchildprint(p.data,end=',)#访问结点P=p.rchild#如果不是线索，则查找其右子树最左下结点【学生】聆听、思考、理解、记录任务实施任务一利用二叉树求解表达式的值【教师】描述问翘，分析问题，安其浮生扫描微课二维码观看视频”利用二叉树求解表达式的值“(详见教材)，要求学生设计算法【问题描述】给定一个四则运算表达式，设计算法求解它的值.【问题分析】一般情况下，一个四则运算表达式由一个操作符和两个操作数构成，两个操作数之间有先后次序，并且操作数本身也可以是四则运算表达式。该结构与二叉树类似，因此可以利用二叉树表示四则运算表达式，即创建表达式解析树，然后再计算它的值。【学生】自行扫码观看配套微课，按照要求完成任务,如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点遍历二叉树：先序遍历、中序遍历、后序遍历、层次遍历确定二叉树：由先序和中序遍历序列确定二叉树、由后序和中序遍历序列确定二叉树线索二叉树的定义、二叉树的线索化、遍历线索二叉树【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的相关练习。【学生】完成课后任务教学反思