二叉树的遍历

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,二叉树的遍历,信息技术基础,要点回顾,满二叉树和完全二叉树,二叉树的存储结构,1,、请同学们仔细看下面三棵树，辨别出满二叉树和完全二叉树：,2,、二叉树通常采用,存储结构。,课前练习,满二叉树,完全二叉树,链式,满二叉树和完全二叉树,满二叉树：,每一层上的结点数都达到,最大值。,完全二叉树：,除最后一层外，每一层上的结点数均达到,最大值,；在最后一层上只,缺少右边,的若干结点。,要点回顾,二叉树的存储结构：采用,链式,存储结构。,存储结点由两部分组成：,数据域,与,指针域,。,存储结点的指针域有两个：,左指针,和,右指针,左指针,数据域,右指针,要点回顾,二叉树存储结点的结构,怎么访问数据呢？,存储,数据,教学内容,二叉树的遍历,重点难点：掌握和分清,二叉树遍历,的三种方法,二叉树的遍历：,是指,不重复,地访问二叉树中的,所有,结点。,前序遍历（,DLR,）,中序遍历,(LDR),后序遍历,(LRD),二叉树的遍历,三种遍历方法：,概念,前序遍历（,DLR,）,规则：,（,1,）,访问,根,结点；,（,2,）,前序遍历,左,子树；,（,3,）,前序遍历,右,子树；,遍历顺序,：,FCADBEGHP,二叉树的遍历,中序遍历（,LDR,）,规则：,（,1,）中序遍历,左,子树；,（,2,）访问,根,结点；,（,3,）中序遍历,右,子树。,遍历顺序,：,ACBDFEHGP,二叉树的遍历,后序遍历,(LRD),规则：,（,1,）后序遍历,左,子树；,（,2,）后序遍历,右,子树；,（,3,）访问,根,结点。,遍历顺序,：,ABDCHPGEF,二叉树的遍历,设有下列二叉树,求此二叉树的前序遍历、中序遍历和后序遍历的顺序分别是？,课堂练习,前序遍历：,ABDECF,中序遍历：,DBEAFC,后序遍历：,DEBFCA,答案解析,后序,遍历,中序遍历,前序遍历,ABDECF,DBEAFC,DEBFCA,内容小结,二叉树三种遍历记忆方法：,前,序遍历：,先找,根,，再,左右,中,序遍历：,先,左,边，,根,中间，,右,在后,后,序遍历：,先,左右,，再找,根,课后作业,1.,完成课后练习,1,、,2,、,3,题。,2.,复习下节课的内容。,谢谢！,