数据结构-二叉树的遍历

运城职业技术大学教案(本科）20—20学年第学期课程名称数据结构课程性质学时授课班级授课教师教案首页教学单元名称第六章树和二叉树第三节遍历二叉树教学内容1.二叉树遍历的概念及方法2.二叉树的遍历算法课时2授课地点教室授课所需教具、工具、软件、耗材等多媒体、黑板、粉笔教学目标知识目标能力目标素质目标面对一些工程问题，能够联想到二叉树的方法，将二叉树的遍历思想融会贯通，开拓思维，注重创新教学重难点重点难点教学方法与手段讲授、演示、讨论、案例分析、实验课程资源备注教案一、导入新课（5分钟）作为有智慧的人类，我们学过“先乘除后加减，有括号先算括号”的算术顺口溜。但是计算机只会一条一条的执行预设的命令，并不会随机应变二、讲授新课（75分钟）授课环节1二叉树遍历的概念及方法（40分钟）1.遍历概念（5分钟）（1）遍历定义：是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。注意：不可有结点被重复访问，也不可有结点没有被访问。举反例讲解。（2）遍历用途：遍历是树结构插入、修改、删除、查找和排序计算的前提，是二叉树一切计算的基础和核心。访问结点所做的操作依赖于具体的应用问题。2.二叉树遍历规则（5分钟）二叉树由根结点、左子树、右子树构成，分别定义为：D、L、R。排列组合后可以有六种遍历方案：LDR、RDL、DRL、DLR、LRD、RLD。但根据“先左后右”的遍历原则，二叉树只有3种遍历方案：（1）DLR先序遍历，根结点最先被访问。（2）LDR中序遍历，根结点在左右子树中间被访问。（3）LRD后序遍历，根结点最后被访问。注意：“先、中、后”的含义是以根结点为参照物，标志着访问根结点的操作发生在访问子树之前还是之后。3.二叉树的遍历方法（30分钟）基于二叉树的递归定义．可得下述遍历二叉树的递归算法定义：先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。例题讲解：将先导问题中的算术表达式以二叉树的形式存储，使用二叉树的遍历方法解决计算问题。//-*6+3952根据上述二叉树的遍历操作定义，其先序序列为：/*3+25-96，中序序列为：3*2+5/9-6，后序序列为：325+*96-/。然后，计算机程序可以使用栈为工具计算后序序列。当访问到数字时，把数字压入栈中，而当访问到运算符时，从栈中取出两个元素进行运算，然后再压回栈中，直到访问完所有元素。最后在栈中的元素就是最终计算结果。授课环节2二叉树的遍历算法（35分钟）1.二叉树的递归算法（10分钟）根据上一环节的二叉树遍历递归操作定义，我们给出先序遍历的递归算法：voidDLR(BiTreeT){if(T!=NULL){visit(T);//访问根节点DLR(T->lchild);//递归遍历左子树DLR(T->rchild);//递归遍历右子树}}可以看到，在递归算法中，输入一棵树，首先判断是否非空，然后才开始遍历过程。根据先序遍历的规则，首先访问根结点，visit()操作根据具体的应用要求实现。然后遍历左子树，进入一个新的遍历二叉树的程序中，遍历完成后继续程序。最后遍历右子树。讨论：中序遍历和后序遍历的递归算法？（5分钟）2.二叉树的非递归算法（15分钟）可以借助栈S，将二叉树的递归遍历算法转换为非递归算法，以中序遍历为例给出中序遍历的非递归算法。先扫描(并非访问)根结点的所有左结点并将它们一一进栈。然后出栈一个结点P*(显然结点P*没有左孩子结点或者左孩子结点均已访问过)，则访问它。然后扫描该结点的右孩子结点，将其进栈，再扫描该右孩子结点的所有左结点并一一进栈，如此继续，直到栈空为止。中序遍历的非递归算法如下：voidInOrder2(BiTreeT){InitStack(S);BiTreep=T;//初始化栈；p是指针while(p||!empty(S)){//栈非空或p非空时循环if(p){push(S,p);//遇到非空树先向左走p=p->lchild;}else{pop(S,p);visit(p);//退栈；访问根结点p=p->rchild;//再向右走}}}讨论：先序遍历和后序遍历的非递归算法？（5分钟）三、课堂小结（5分钟）本次课我们了解了二叉树遍历的基本概念和方法，掌握了二叉树的三种遍历方法，并使用算法实现了遍历过程，包括递归算法和非递