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

高中信息技术学科二叉树遍历题型的教学思考摘要：《数据与数据结构》是浙江省高中信息技术课程的新教材，“数据结构”对于高中生来讲，属于较难的知识模块，其中“数据结构”中的二叉树的遍历（前序遍历、中序遍历、后序遍历）对于学生来讲较难理解掌握，而提供前序遍历和中序遍历或后序遍历与中序遍历，求另一种遍历这类题型对于二叉树的遍历学习有较大帮助。关键词：数据结构二叉树遍历数据结构(DataStructure)是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构有数组，链表，队列，栈，树，图等。其中树，尤其是二叉树的遍历是高中信息技术教学中的一个重点和难点。二叉树是一种特殊的树，是一个具有n个节点的有限集合，它的所有节点的度都小于或等于2。当n等于0时，二叉树是一棵空树；当n不等于0时，它是一棵由根节点和两颗互不相交的，分别称作这个根节点的左子树和右子树的二叉树。1遍历所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次。树的遍历是树的一种重要的运算，从二叉树的根节点出发，节点的遍历分为三个主要步骤：对当前节点进行访问操作、遍历左边子节点、遍历右边子节点。根据对根节点、左子树、右子树访问的顺序可分为前序遍历、中序遍历和后序遍历。前序遍历：访问顺序为先访问根节点（N），再访问左子树（L），最后访问右子树(R),顺序为NLR。以一颗满二叉树层次遍历顺序为ABCDEFG为例，1、先访问根节点A；2、然后访问左子树BDE,左子树再遍历，先根节点B，然后访问左节点D，最后访问右节点E；3、访问右子树CFG，先访问根节点C，再访问左节点F，最后访问右节点G。综上前序遍历结果为ABDECFG。中序遍历：访问顺序为先访问左子树（L），再访问根节点（N），最后访问右子树(R),顺序为LNR。以一颗满二叉树层次遍历顺序为ABCDEFG为例，1、先访问左子树BDE，左子树再遍历，先左节点D，再访问根节点B，最后访问右节点E。左子树的访问顺序为DBE；2、然后访问根节点A；3访问右子树CFG，先访问左节点F，然后访问根节点C，最后访问右节点G，右子树的访问顺序为FCG;综上中序遍历结果为DBEAFCG。后序遍历：访问顺序为先访问左子树（L），再访问右子树(R)，最后访问根节点（N），顺序为LRN。以一颗满二叉树层次遍历顺序为ABCDEFG为例，1、先访问左子树BDE，左子树再遍历，先左节点D，再访问右节点E，最后访问根节点B，左子树的访问顺序为DEB；2、访问右子树CFG，先访问左节点F，然后访问右节点G，最后访问根节点C。访问顺序为FGC；3、最后访问根节点A。综上后序遍历结果为DEBFGCA。2遍历的结合前序遍历，中序遍历，后序遍历学生运用递归的思想能掌握，但前序遍历和中序遍历结合在一起，让推算后序遍历；或者中序遍历和后序遍历结合在一起，让推算前序遍历。这类题型无疑将遍历的难点一下子提升，学生往往无从下手。以下将采用分析法来破解此类题型。举例：某二叉树的中序遍历序列为cbdeagihjf，后序遍历结果为cedbijhgfa，问前序遍历结果。对于此类题型，我们可以用分析法来处理:1）结合中序遍历和后序遍历的原理，对中序遍历和后序遍历进行分析，中序遍历的顺序为左子树（L）—>根（N）—>右子树（R），后序遍历顺序为左子树（L）—>右子树（R）—>根（N），对于同样一棵树，尽管访问顺序不一样，但是树仍旧为那棵树，因此我们可以从后序遍历首先找到这棵树的根节点，本例根节点即a;2）找到此棵树的根节点a后，根据中序遍历的原理：访问顺序为左子树（L）—>根（N）—>右子树（R），即根将整个访问顺序分为左右两部分，左侧部分为左子树，即cbde；右侧部分为右子树，即gihjf。3）根据中序遍历找到左子树cbde后，结合后序遍历左子树访问顺序为cedb,然后对这个子树重复上述1）2）两个步骤；根据后序遍历，子树根节点为b，然后根据中序遍历b左侧为左节点c，根节点b右侧子树为de，de作为一棵子树，结合后序遍历顺序ed，可知子树根节点为d,再结合中序遍历de,得到右孩子为e。4）根据中序遍历找到右子树gihjf后，结合后序遍历子树的访问顺序为ijhgf，可知f为该右子树的根节点，然后对这个子树重复上述1）2）两个步骤；根据中序遍历gihjf，结合根节点f,可知该树只有左子树gihj，没有右子树。再结合后序遍历对gihj的访问顺序ijhg来看，g为左子树的根节点，根据中序遍历gihj来看，只有右子树ihj,再结合后序遍历ijh可知h为子树根节点，根据中序ihj可知，i为左节点，j为右节点。5）根据以上分析画出树的示意图，根据前序遍历的访问顺序为先访问根节点（N），再访问左子树（L），最后访问右子树(R)，得到前序遍历顺序为abcdefghij。3小结通过以上分析法我们可以