二叉树遍历(稿).

数据结构C语言AFEDCBG知识与技能理解遍历算法；掌握遍历规则；体会遍历算法的应用。过程与方法通过遍历规则讲解和自主总结遍历思想及算法的教学过程，掌握学习分析总结问题的方法。实现价值体会复杂数据结构在计算机中的存储方式及组织结构；学会解决如何合理的用计算机程序处理复杂数据。教学重点掌握二叉树的遍历方法。理解二叉树的遍历算法教学难点二叉树遍历的应用。重点难点教学过程引导讲授分析总结新课引入-遍历的应用1课程讲解-基础知识2教学提升-课程总结4实践内容-练习讨论3巩固拓展-课后作业5问题引入3＊(2+5)/(9-6)=7先算哪个呢？借助二叉树将算术表达式画成一棵二叉树/＊+3－6259它的中序遍历序列为：3*2+5/9－6它的后序遍历序列为：25+3*96－/中缀表达式（人的思维）后缀表达式（电脑的思维）()()基础知识-概念遍历定义——遍历用途——遍历方法——指按某条搜索路线遍访每个结点且不重复（又称周游）。它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。对每个结点的查看通常都是“先左后右”。基础知识-遍历规则二叉树由根、左子树、右子树构成，定义为D、L、R以根结点为参照系注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。D、L、R的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右，则有三种实现方案：DLRLDRLRD先序遍历中序遍历后序遍历基础知识-先序遍历ADBCDLRADLRDLRBDCDLR先序遍历序列：ABDC先序遍历(DLR):特点：任意一个结点均处在其子女结点的前面(根结点在前)有什么特点？分析思想总结算法ADBCDLRADLRDLRBDCDLR访问根结点先序遍历根的左子树先序遍历根的右子树递归过程先序遍历算法DLR(node*root){if(root!=NULL){printf(“%d”,root-data);DLR(root-lchild);DLR(root-rchild);}return(0);}基础知识-中序遍历ADBCLDRBLDRLDRADCLDR中序遍历序列：BDAC特点：根结点左右分别为左右子树的所有结点.中序遍历(LDR):讨论中序遍历思想及算法？基础知识-后序遍历ADBC后序遍历(LRD):讨论后序遍历思想及算法？LRDLRDLRDADCLRDB后序遍历序列：DBCA三种遍历算法总结中序遍历算法LDR(node*root){if(root!=NULL){LDR(root-lchild);printf(“%d”,root-data);LDR(root-rchild);}return(0);}后序遍历算法LRD(node*root){if(root!=NULL){LRD(root-lchild);LRD(root-rchild);printf(“%d”,root-data);}return(0);}结点数据类型自定义typedefstructnode{intdata;structnode*lchild,*rchild；}node;node*root;先序遍历算法DLR(node*root){if(root!=NULL)//非空二叉树{printf(“%d”,root-data);//访问DDLR(root-lchild);//递归遍历左子树DLR(root-rchild);//递归遍历右子树}return(0);}三种遍历算法分析1.从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。第1次经过时访问，是先序遍历第2次经过时访问，是中序遍历第3次经过时访问，是后序遍历2.二叉树遍历的时间效率和空间效率时间效率:O(n)//每个结点只访问一次空间效率:O(n)//栈占用的最大辅助空间精确值：树深为k的递归遍历需要k+1个辅助单元AFEDCBG实践内容-练习讨论例1：先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABCDEDBEACDEBCA口诀：DLR—先序遍历，即先根再左再右ABDECLDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根实践内容-练习讨论ABCDEFGHK例2：先序序列：中序序列：后序序列：ABCDEFGHKBDCAEHGKFDCBHKGFEA知识应用-表达式计算+*A*/EDCB先序遍历结果+**/ABCDE—前缀表示法中序遍历结果A/B*C*D+E—中缀表示法后序遍历结果AB/C*D*E+—后缀表示法层次遍历结果+*E*D/CAB例3：用二叉树表示算术表达式特别讨论若已知先序（或后序）遍历结果和中序遍历结果，能否“恢复”出二叉树？例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请画出这棵二叉树。分析：①由后序遍历特征，根结点必在后序序列尾部（即A）；②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG）；③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。特别讨论：利用后序和中序遍历序列构造一棵二叉树已知中序遍历：BDCEAFHG已知后序遍历：DECBHGFA（BDCE）（FHG）A（DCE）BFGHCDEABBACCDCE如果是先序序列和中序序列呢？知识拓展—利用遍历建立二叉树用空格字符表示‘无孩子’或指针为空如何把二叉树存入电脑内？怎样利用遍历建立一棵二叉树？例：将下面的二叉树以二叉链表形式存入计算机内。ABGDFCE考虑1：输入结点时怎样表示“无孩子”？考虑2：以何种遍历方式来输入和建树？将二叉树按先序遍历次序输入：ABCDEGF(/n)以先序遍历最为合适，让每个结点都能及时被连接到位。字符串输完后应当再加一特殊的结束符号(如$)，因为无法惟一表示结束。知识拓展—利用遍历建立二叉树建树算法：StatusCreateBiTree(BiTree&T){//构造二叉树Tscanf(“%c”,&ch);If(ch==’’)T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(overflow);T-data=ch;//生成根结点CreateBiTree(T-lchild);//构造左子树CreateBiTree(T-rchild);//构造右子树}returnOK;}//CreateBiTree输入序列：ABCDEGF课程总结二叉树的遍历定义、用途、方法中序遍历：左、根、右先序遍历：根、左、右后序遍历：左、右、根利用先序遍历建立二叉树表达式的计算顺序遍历算法：递归遍历规则问题引入遍历的概述遍历的应用特别讨论如何利用遍历构造一棵二叉树？遍历效率：O(n)课后拓展上机练习◆把二叉树的遍历算法改写成程序进行上机调试。小组讨论完成小牛试刀◆写出利用先序遍历创建一棵二叉树的完整算法。个人独立完成1、如右图所示：写出该二叉树的前序遍历、中序遍历和后序遍历的序列。2、已知某二叉树的前序遍历序列为ABDEFGC，中序序列为DEBGFAC，画出该二叉树。3、已知某二叉树的后序遍历序列为dabec，中序序列为debac，则它的前序遍历序列为：。ECAGFBD商丘工学院信息与电子工程学院