数据结构中二叉树中序遍历的教学分析

数据结构中二叉树中序遍历的教学分析 玲 袁宇丽, 胡 Ξ )四川 内江 641112 (内江师范学院 计算机与信息科学系, 摘 要: 数据结构的教学应注重方法的应用, 在二叉树的中序遍历中使用投影法可以使遍历过程简单化, () ( ) 再由其中的一种遍历递归算法 先序推导得到另外两种 中序, 后序的遍历递归算法, 让学生加深对整个遍 历过程的了解与掌握。 关键词: 数据结构; 二叉树; 遍历; 算法 () 中图分类号: 642 文献标识码: 文章编号: 1671- 1785 200604- 0109- 03GA 1 引言 《数据结构》是计算机学科的一门专业技术基础课, 也是计算机程序设计的重要理论技术基础课。目的是在于让学生 学会分析研究计算机加工的数据结构的特性, 以便为应用涉及的数据结构选择适当的逻辑结构, 存储结构及其相应的算 法; 并初步掌握算法的时间分析和空间分析的技术; 培养学生进行复杂程序设计的能力和数据抽象的能力。 但从学生角 度而言, 在学习该门课程时普遍反映较难, 总觉得课程内容抽象, 不易理解, 好些具体算法不知从何下手。针对以上情况, 任课教师在讲授该门课程时更应注重方法的应用, 从多角度, 多侧面展现知识点, 化抽象为具体, 化特殊为一般, 不应只 局限于教材上的一种解题模式, 应结合自己的理解, 补充新方法, 这样才能更好的拓宽学生的思路, 达到化难为易, 举一 反三的效果。 下面以具体实例说明。 2 二叉树中序遍历的投影法 在二叉树的一些应用中, 常常要求在树中查找具有某种特征的结点, 或者对树中全部结点逐一进行某种处理。 这就 提出了一个遍历二叉树的问题, 即如何按某条搜索路径巡访树中每个结点, 使得每个结点均被访问一次, 而且仅被访问 一次。“访问”的含义很广, 可以是对结点作各种处理, 如输出结点的信息等。遍历对线性结构来说, 是一个容易解决的问 题。 而对二叉树则不然, 由于二叉树是一种非线性结构, 每个结点都可能有两棵子树, 因而需要寻找一种规律, 以便使二 叉树上的结点能排列在一个线性队列上, 从而便于访问。 回顾二叉树的定义可知, 二叉树是由三个基本单元组成: 根结点、左子树、右子树。 因此, 若能依次遍历这三部分, 便 () () () 是遍历了整个二叉树。若限定先左后右的顺序, 则分为三种情况: 先 根序遍历, 中 根序遍历, 后 根序遍历。二叉树的 ( 遍历及其应用是数据结构中一个很重要的知识点, 要求学生能根据所给二叉树得到相应的三种遍历序列 前序, 中序, 后 1 ) 序, 并能写出这三种遍历算法。 以中序遍历而言, 教材结合图给出了中序遍历过程示意图, 并具体分析了该遍历的递 归执行过程。 但递归调用及返回对学生来说本身就是一个较难掌握的知识, 往往出现进入递归后不知怎样层层返回, 所 以书上在说明二叉树的中序遍历时借用递归调用与返回的 方法向学生展示整个遍历过程对初学者总感觉有一定难度。 我们在这里补充一种教材上没有提到的二叉树中序遍历的 直观方法: 投影法。分析中序遍历的实质, 是按先中序访问左 子树, 再访问根结点, 最后中序访问右子树的顺序进行的。直 观上想, 处于二叉树最左下方的结点应该是第一个要访问的 结点, 再结合二叉树本身的构造特点, 是有严格的左右子树 之分的, 所以投影法就是根据二叉树的结构特征得来的。 对 于一棵二叉树, 从根结点所在的层开始, 将所有非空左子树 图 1 二叉树 完全位于当前根结点的左方, 将所有非空右子树完全位于当 收稿日期: 2005- 11- 11 () 作者简介: 袁字丽 1979- , 女, 四川自贡人, 内江师范学院助教, 硕士。 () : ; PRO C P reo rde r b tb it rep t r{先序遍历根结点指针为 的二叉树} b t ?IF b tN IL () [ ?. ; {访问根结点} T H EN v isit b tda ta () ?. ; P reo rde r b tlch ild () ?. ;P reo rde r b trch ild ] ; {}EN D PP reo rde r 那么二叉树中序遍历的递归算法又该怎样呢? 结合 果将上述算法中访问结点的语句放于不同的位置处, 便 () : ; PRO C Ino rde r b tb it rep t r{中序遍历根结点指针为 的二叉树} b t ?IF b tN IL () [ ?. ;T H EN Ino rde r b tlch ild () ?. ;v isit b tda ta () ?. ;Ino rde r b trch ild ] ; { }EN D PIno rde r () : ;PRO C Po sto rde r b tbo t rep t r {后序遍历根结点指针为 的二叉树}b t b t?N IL IF () [ ?. ; T H EN Po sto rde r b tlch ild () ?. ;Po sto rde r b trch ild () ?. ;v isit b tda ta ] ; {}EN D PPo sto rde r 所以, 只要弄清楚问题的本质, 算法设计也就容易解 的数据类型定义如下: T YP E = ?; N o dep t rno de typ e = N o dep t rreco rd : ; L ch ildno dep t r : ;D a tach a r : R ch ildno dep t r ;E nd () 该算法描述如下 类 语言: p a sca l : V a r roo tno dep t r () : {指向二叉树的根结P ro cedu re ino rde r p no dep t rp V a r p s : a r ray 1. . stack size ] o f no dep t r; : ; topin tege r B E G IN T op: = 0; {栈置空} R ep ea t < > W h ile p n il do B eg in : = + 1;T op top > {栈满的判断}; If top stack size th en stack fu l [ : = ; ? ?. ;: = P s top p pp lch ild ;E nd < > 0 If top th en B eg in : = [ ;Pp s top 1; T op: = top - () ??. ; W r ite p da ta : = ?. Pp rch ild ;E nd = 0U n t il top ;EN D 该算法借用堆栈实现二叉树的中序遍历, 没有涉及到递归的应用, 整个过程由循环语句控制, 结构清晰, 若是能再结 合具体图示给学生讲解, 理解与掌握该算法思想并不困难。 如果在刚才的中序遍历非递归算法中将?所在的语句放置 ?, 就得到了其先序遍历的非递归算法, 也就是说, 从二叉树的第一层开始, 在访问左右子树前, 先访问当前根结点, 其余 各层依次类推。 以上例子说明, 数据结构中的一些知识点之间彼此都有联系, 如果能发觉其间的规律, 着重分析相互之间的内在联 系, 并结合教材, 补充一些较易理解的解题算法, 这样由浅入深的进行介绍, 必会加深学生对这些知识的理解与掌握, 也 会加强对知识灵活应用的能力。 这也是我们开设这门课程的目的所在。 参考文献: () 1 严蔚敏, 吴伟民. 数据结构 第二版[. 北京: 清华大学出版社, 1992. 1252128.M () 2 严蔚敏, 吴伟民. 数据结构 语言版[. 北京: 清华大学出版社, 1998. C M The Teach in g Ana ly s is of In order Traver s in g B inary Tree in the D a ta Struc ture 2, YUAN YuliHU L ing (). , , , 641112, D ep to f Com p u te r & Info rm a t io n Sc ienceN e ijiang teach e r s co llegeN e ijiangS ich uan C h ina A bstra c t: T h e teach ing o f th e D a ta S t ruc tu re sho u ld m ak e a po in t o f th e app lica t io n o f th e m e tho d, u sing th e ca st . sh adow m e tho d can m ak e th e p ro ce ss o f t rave r se tu rned in b r ief a t ino rde r t rave r sing B ina ry t reeA ga in f rom am o ng ( ) , th em o f th e in side a t rave r se a lgo r ithm p reo rde rdeduce s a t r sve r se a lgo r ithm th a t ge t ano th e r tw o k ind s o fle t stu2 .den t deep en th e unde r stand ing o f w ho le th e p ro ce ss o f t rave r se : ; ; ; Key word sda ta st ruc tu reb ina ry t reet rave r sea lgo r ithm