高中信息技术学科二叉树遍历题型的教学思考

高中信息技术学科二叉树遍历题型的教学思考摘要《数据与数据结构》是浙江省高中信息技术课程的新教材，“数据结构”对于高中生来讲，属于较难的知识模块，其中“数据结构”中的二叉树的遍历（前序遍历、中序遍历、后序遍历）对于学生来讲较难理解掌握，而提供前序遍历和中序遍历或后序遍历与中序遍历，求另一种遍历这类题型对于二叉树的遍历学习有较大帮助关键词数据结构二叉树遍历数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合常见的数据结构有数组，链表，队列，栈，树，图等其中树，尤其是二叉树的遍历是高中信息技术教学中的一个重点和难点二叉树是一种特殊的树,是一个具有n个节点的有限集合，它的所有节点的度都小于或等于2当n等于0时，二叉树是一棵空树；当n不等于0时，它是一棵由根节点和两颗互不相交的，分别称作这个根节点的左子树和右子树的二叉树1遍历所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次树的遍历是树的一种重要的运算，从二叉树的根节点出发，节点的遍历分为三个主要步骤对当前节点进行访问操作、遍历左边子节点、遍历右边子节点根据对根节点、左子树、右子树访问的顺序可分为前序遍历、中序遍历和后序遍历前序遍历访问顺序为先访问根节点（N）,再访问左子树（L）,最后访问右子树（R）,顺序为NLR以一颗满二叉树层次遍历顺序为ABCDEFG为例，

1、先访问根节点A；

2、然后访问左子树BDE,左子树再遍历，先根节点B,然后访问左节点D,最后访问右节点E；

3、访问右子树CFG,先访问根节点C,再访问左节点F,最后访问右节点Go综上前序遍历结果为ABDECFGo中序遍历访问顺序为先访问左子树（L）,再访问根节点（N）,最后访问右子树（R）,顺序为LNR以一颗满二叉树层次遍历顺序为ABCDEFG为例，

1、先访问左子树BDE,左子树再遍历，先左节点D,再访问根节点B,最后访问右节点Eo左子树的访问顺序为DBE；

2、然后访问根节点A；3访问右子树CFG,先访问左节点F,然后访问根节点C,最后访问右节点G,右子树的访问顺序为FCG;综上中序遍历结果为DBEAFCGo后序遍历访问顺序为先访问左子树（L）,再访问右子树（R）,最后访问根节点（N）,顺序为LRN以一颗满二叉树层次遍历顺序为ABCDEFG为例，

1、先访问左子树BDE,左子树再遍历，先左节点D,再访问右节点E,最后访问根节点B,左子树的访问顺序为DEB；

2、访问右子树CFG,先访问左节点F,然后访问右节点G,最后访问根节点C访问顺序为FGC；

3、最后访问根节点A综上后序遍历结果为DEBFGCAo2遍历的结合前序遍历，中序遍历，后序遍历学生运用递归的思想能掌握，但前序遍历和中序遍历结合在一起，让推算后序遍历；或者中序遍历和后序遍历结合在一起，让推算前序遍历这类题型无疑将遍历的难点一下子提升，学生往往无从下手以下将采用分析法来破解此类题型举例某二叉树的中序遍历序列为cbdeagihjf,后序遍历结果为cedbijhgfa,问前序遍历结果对于此类题型，我们可以用分析法来处理1）结合中序遍历和后序遍历的原理，对中序遍历和后序遍历进行分析，中序遍历的顺序为左子树（L）—＞根（N）—＞右子树（R）,后序遍历顺序为左子树（L）—＞右子树（R）—〉根（N）,对于同样一棵树，尽管访问顺序不一样，但是树仍旧为那棵树，因此我们可以从后序遍历首先找到这棵树的根节点，本例根节点即a;2）找到此棵树的根节点a后，根据中序遍历的原理访问顺序为左子树（L）—＞根（N）—＞右子树（R）,即根将整个访问顺序分为左右两部分，左侧部分为左子树，即cbde；右侧部分为右子树，即gihjf3）根据中序遍历找到左子树cbde后，结合后序遍历左子树访问顺序为cedb,然后对这个子树重复上述1）2）两个步骤；根据后序遍历，子树根节点为b,然后根据中序遍历b左侧为左节点c,根节点b右侧子树为de,de作为一棵子树，结合后序遍历顺序ed,可知子树根节点为d,再结合中序遍历de,得到右孩子为e4）根据中序遍历找到右子树gihjf后，结合后序遍历子树的访问顺序为ijhgf,可知f为该右子树的根节点，然后对这个子树重复上述1）2）两个步骤;根据中序遍历gihjf,结合根节点f,可知该树只有左子树gihj,没有右子树再结合后序遍历对gihj的访问顺序ijhg来看，g为左子树的根节点，根据中序遍历gihj来看，只有右子树ihj,再结合后序遍历ijh可知h为子树根节点，根据中序ihj可知，i为左节点，j为右节点5）根据以上分析画出树的示意图，根据前序遍历的访问顺序为先访问根节点（N）,再访问左子树（L）,最后访问右子树（R）,得到前序遍历顺序为abcdefghijo3小结通过以上分析法我们可以将二叉树的遍历掌握，同时对二叉树遍历的理解进一步加深，对理解非线性的数据结构有较大帮助教师在讲授该类知识点的时候,可以采用该分析法，同时配合画结构示意图，更加形象生动的展示树的遍历过程,更易于学生的学习和理解。