二叉树遍历(稿)ppt课件.ppt

《二叉树遍历(稿)ppt课件.ppt》由会员分享，可在线阅读，更多相关《二叉树遍历(稿)ppt课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人数据结构数据结构 C C语言语言 AFEDCBG烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人 知识与技能知识与技能 理解遍历算理解遍历算理解遍历算理解遍历算法；掌握遍历法；掌握遍历法；掌握遍历法；掌握遍历规则；体会遍规则；体会遍规则；体会遍规则；体会遍历算法的应用。历算法的应用。历算法的应用。历算法的应用。过程与方法过程与方法 通过遍历规通过遍历规通过遍历规通过遍历规则讲解和自主则讲解和自

2、主则讲解和自主则讲解和自主总结遍历思想总结遍历思想总结遍历思想总结遍历思想及算法的教学及算法的教学及算法的教学及算法的教学过程过程过程过程，掌握学，掌握学，掌握学，掌握学习分析总结问习分析总结问习分析总结问习分析总结问题的题的题的题的方法方法方法方法。实现价值实现价值 体会复杂数据体会复杂数据体会复杂数据体会复杂数据结构在计算机中结构在计算机中结构在计算机中结构在计算机中的存储方式及组的存储方式及组的存储方式及组的存储方式及组织结构；学会织结构；学会织结构；学会织结构；学会解解解解决如何合理的用决如何合理的用决如何合理的用决如何合理的用计算机程序处理计算机程序处理计算机程序处理计算机程序处理复

3、杂数据复杂数据复杂数据复杂数据。烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人 教学重点教学重点掌握二叉树掌握二叉树的遍历方法。的遍历方法。理解二叉树理解二叉树的遍历算法的遍历算法 教学难点教学难点 二叉树遍历二叉树遍历的应用。的应用。重重点点难难点点烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人教教 学学 过过 程程引导引导引导引导讲授讲授讲授讲授分析分析分析分析总结总结总结总结 新课引入新课引入-遍历的应用遍历的应用1 课程讲解课程

4、讲解-基础知识基础知识2教学提升教学提升-课程总结课程总结4实践内容实践内容-练习讨论练习讨论3巩固巩固拓展拓展-课后作业课后作业5烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人问题问题问题问题引入引入引入引入 3(2+5)/(9-6)=7先算哪个呢？烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人借助二叉借助二叉借助二叉借助二叉树树树树将算术表达式画将算术表达式画成一棵二叉树成一棵二叉树/+36259它的中序遍历序列为：它的中序遍历序列

5、为：3 *2 +5 /9 6它的后序遍历序列为：它的后序遍历序列为：2 5 +3 *9 6 /中缀表达式（人的思维）后缀表达式（电脑的思维）()()烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人基基基基础础础础知知知知识识识识-概概概概念念念念遍历定义遍历定义遍历用途遍历用途遍历方法遍历方法指按某条搜索路线遍访每个结点且指按某条搜索路线遍访每个结点且不重复（又称周游）。不重复（又称周游）。它是树结构插入、删除、修改、查它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一找和排序运算的前提，是二叉树一切运算的

6、基础和核心。切运算的基础和核心。对每个结点的查看通常都是对每个结点的查看通常都是“先左后先左后右右”。烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人基基基基础础础础知知知知识识识识-遍遍遍遍历规则历规则历规则历规则二叉树由根、左子树、右子树构成，定义为二叉树由根、左子树、右子树构成，定义为D、L、R以根结点为参照系以根结点为参照系注：注：“先、中、后先、中、后”的意思是指访问的结点的意思是指访问的结点D D是先于子树出是先于子树出现还是后于子树出现。现还是后于子树出现。v D、L、R的组合定义了六种可能的遍历方案：

7、的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLDv 若限定若限定先左后右先左后右，则有三种实现方案：，则有三种实现方案：DLR LDR LRD先先序遍历序遍历 中中序遍历序遍历 后后序遍历序遍历 烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人基基基基础础础础知知知知识识识识-先序遍先序遍先序遍先序遍历历历历ADBCD L RAD L RD L RBDCD L R先序遍历序列：先序遍历序列：A B D C先序遍历先序遍历(DLR):特点：任意一个结点均处在其子女结点的前面(根结点在前)有

8、什么特点？烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人分析思想分析思想分析思想分析思想总结总结总结总结算法算法算法算法ADBCD L RAD L RD L RBDCD L RF访问根结点访问根结点F先序先序遍历根的左子树遍历根的左子树F先序先序遍历根的右子树遍历根的右子树递归过程先序遍历算法先序遍历算法先序遍历算法先序遍历算法DLR(node*root)if(root!=NULL)printf(“%d”,root-data);DLR(root-lchild);DLR(root-rchild);return(0);

9、烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人基基基基础础础础知知知知识识识识-中序遍中序遍中序遍中序遍历历历历ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A C特点：根结点左右分别为左右子树的所有结点.中序遍历中序遍历(LDR):讨论中序遍历思想及算法？烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人基基基基础础础础知知知知识识识识-后序遍后序遍后序遍后序遍历历历历ADBC后序遍历后序遍历

10、(LRD):讨论后序遍历思想及算法？L R DL R DL R DADCL R DB后序遍历序列：后序遍历序列：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)i

11、f(root!=NULL)LRD(root-lchild);LRD(root-rchild);printf(“%d”,root-data);return(0);结点数据类型自定义结点数据类型自定义结点数据类型自定义结点数据类型自定义typedef struct nodeint data;struct node*lchild,*rchild；node;node*root;先序遍历算法先序遍历算法先序遍历算法先序遍历算法DLR(node*root)if(root!=NULL)/非空二叉树非空二叉树 printf(“%d”,root-data);/访问访问D DDLR(root-lchild);/递

12、归遍历左子树递归遍历左子树DLR(root-rchild);/递归遍历右子树递归遍历右子树 return(0);烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人三种遍历算法分析三种遍历算法分析1.从前面的三种遍历算法可以知道：如果将从前面的三种遍历算法可以知道：如果将print语句抹去，语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的遍历算法的访问路径是相同的，只是访问结点的时机不同。访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到

13、终点的路径从虚线的出发点到终点的路径上，每个结点经过上，每个结点经过3次次。第第1次次经过时访问，是经过时访问，是先序先序遍历遍历第第2次次经过时访问，是经过时访问，是中序中序遍历遍历第第3次次经过时访问，是经过时访问，是后序后序遍历遍历2.2.二叉树遍历的时间效率和空间效率二叉树遍历的时间效率和空间效率时间效率时间效率:O(n)O(n)O(n)O(n)/每个结点只访问一次每个结点只访问一次空间效率空间效率:O(n)O(n)O(n)O(n)/栈占用的最大辅助空间栈占用的最大辅助空间精确值：树深为精确值：树深为k k的递归遍历需要的递归遍历需要k+1k+1个辅助单元个辅助单元AFEDCBG烧伤病

14、人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人实践内实践内实践内实践内容容容容-练习讨论练习讨论练习讨论练习讨论例例1：先序遍历的结果是：先序遍历的结果是：中序遍历的结果是：中序遍历的结果是：后序遍历的结果是：后序遍历的结果是：A B CD ED D B B E E A A C CD D E B CE B C A A口诀：口诀：D DLRLR先序遍历，即先序遍历，即先根再左再右先根再左再右A A B B D D E E C CL LD DRR中序遍历，即中序遍历，即先左再根再右先左再根再右LRLRD D后序遍历，即后序遍

15、历，即先左再右再根先左再右再根烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人实践内实践内实践内实践内容容容容-练习讨论练习讨论练习讨论练习讨论ABCDEFGHK例例2：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人知知知知识应识应识应识应用用用用-表表表表达达达达式式式式计计计

16、计算算算算+*A*/EDCB先序遍历结果先序遍历结果+*/A B C D E前缀表示法前缀表示法中序遍历结果中序遍历结果A/B*C*D+E中缀表示法中缀表示法后序遍历结果后序遍历结果A B/C*D*E+后缀表示法后缀表示法层次遍历结果层次遍历结果+*E*D/C A B例例3 3：用二叉树表示算术表达式用二叉树表示算术表达式烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人特别讨论特别讨论 若已知若已知若已知若已知先序先序先序先序（或（或（或（或后序后序后序后序）遍历结果和）遍历结果和）遍历结果和）遍历结果和中序中序中序

17、中序遍历结果遍历结果遍历结果遍历结果，能否，能否，能否，能否“恢复恢复恢复恢复”出二叉树？出二叉树？出二叉树？出二叉树？例：例：已知一棵二叉树的已知一棵二叉树的中序序列中序序列和和后序序列后序序列分别是分别是BDCEAFHGBDCEAFHG 和和 DECBHGFADECBHGFA，请画出这棵二叉树。，请画出这棵二叉树。分析：分析：由后序遍历特征，根结点必在后序序列尾部由后序遍历特征，根结点必在后序序列尾部（即（即A A）；由由中中序序遍遍历历特特征征，根根结结点点必必在在其其中中间间，而而且且其其左左部部必必全全部部是是左左子子树树的的子子孙孙（即即BDCEBDCE），其其右右部部必必全全部部

18、是是右右子子树树的的子孙子孙（即（即FHGFHG）；继继而而，根根据据后后序序中中的的DECBDECB子子树树可可确确定定B B为为A A的的左左孩孩子子，根根据据HGFHGF子串可确定子串可确定F F为为A A的右孩子；以此类推。的右孩子；以此类推。烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人特别讨论：特别讨论：利用后序和中序遍历序列构造一棵二叉树利用后序和中序遍历序列构造一棵二叉树利用后序和中序遍历序列构造一棵二叉树利用后序和中序遍历序列构造一棵二叉树已知中序遍历：已知中序遍历：B D C E A F H G

19、已知后序遍历：已知后序遍历：D E C B H G F A（B D C E）（F H G）A（D C E）BFGHCD EABBACCD C E如果是先序序列如果是先序序列和中序序列呢？和中序序列呢？烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人知识拓展知识拓展利用遍历建立二叉树利用遍历建立二叉树用空格字符表示用空格字符表示无孩子无孩子或指针或指针为空为空如何把二叉树存入电脑内？如何把二叉树存入电脑内？怎样利用遍历建立一棵二叉树？怎样利用遍历建立一棵二叉树？例：将下面的二叉树以二叉链表形式存入计算机内。例：将下面的

20、二叉树以二叉链表形式存入计算机内。A AB BGGD DF FC CE E考虑考虑1 1：输入结点时怎样表示：输入结点时怎样表示“无孩子无孩子”？考虑考虑2 2：以何种遍历方式来输入和建树？：以何种遍历方式来输入和建树？将二叉树按先序遍历次序输入：将二叉树按先序遍历次序输入：A B CA B C D ED E G G F F (/n)(/n)以先序遍历最为合适，以先序遍历最为合适，让每个结点都能及时让每个结点都能及时被连接到位。被连接到位。字符串输完后字符串输完后应当再应当再加一特殊的结束符号加一特殊的结束符号(如如$)，因为，因为 无无法惟一表示结束。法惟一表示结束。烧伤病人的治疗通常是取烧

21、伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人知识拓展知识拓展利用遍历建立二叉树利用遍历建立二叉树建树算法：建树算法：Status CreateBiTree(BiTree&T)/构造二叉树构造二叉树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);/

22、构造右子树构造右子树 return OK;/CreateBiTree/CreateBiTree输入序列：输入序列：A B C D E G F 烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人课课课课程程程程总结总结总结总结二叉树的遍历二叉树的遍历定义、用途、方法定义、用途、方法中序遍历：左、根、右中序遍历：左、根、右先序遍历：根、左、右先序遍历：根、左、右后序遍历：左、右、根后序遍历：左、右、根利用先序遍历建立二叉树利用先序遍历建立二叉树表达式的计算顺序表达式的计算顺序遍历算法：递归遍历算法：递归遍历规则遍历规则问题

23、引入问题引入遍历的概述遍历的概述遍历的应用遍历的应用特别讨论特别讨论如何利用遍历构造一棵二叉树？如何利用遍历构造一棵二叉树？遍历效率：遍历效率：O(n)烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人课课课课后拓展后拓展后拓展后拓展上机练习上机练习把二叉树的遍历算法改写成程序进行上机调试把二叉树的遍历算法改写成程序进行上机调试。小组讨论完成小组讨论完成小组讨论完成小组讨论完成小牛试刀小牛试刀写出利用先序遍历创建一棵二叉树的完整算法。写出利用先序遍历创建一棵二叉树的完整算法。个人独立完成个人独立完成个人独立完成个人独立

24、完成烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人1 1、如右图所示：写出该二、如右图所示：写出该二叉树的前序遍历、中序叉树的前序遍历、中序遍历和后序遍历的序列。遍历和后序遍历的序列。2 2、已知某二叉树的前序遍、已知某二叉树的前序遍历序列为历序列为ABDEFGCABDEFGC，中序，中序序列为序列为DEBGFACDEBGFAC，画出该，画出该二叉树。二叉树。3 3、已知某二叉树的后序遍、已知某二叉树的后序遍历序列为历序列为dabecdabec，中序序，中序序列为列为debacdebac，则它的前序，则它的前序遍历序列为：。遍历序列为：。ECAGFBD烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人商丘工学院商丘工学院 信息与电子工程学院信息与电子工程学院