二叉树遍历(稿)教学内容.ppt

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