填空法讲授二叉树遍历教学探讨
开篇：润墨网以专业的文秘视角，为您筛选了一篇填空法讲授二叉树遍历教学探讨范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
文章编号：1672-5913(2008)12-0075-02
摘要：本文从教学实践的角度出发，阐述了学生对“数据结构”课程教学中二叉树遍历这一知识点不易理解的问题，并提出一种新的方法――填空法解决这一问题。通过对填空法的基本原理和讲授方式的探讨，使学生产生兴趣从而提高该知识点的课堂教学效果。
中图分类号：G642
文献标识码：A
数据结构是计算机专业极其重要的专业基础课。所有数据结构中，树是非常重要的一种，尤其是二叉树，学习者是应该牢固掌握的。在学习了较为简单的线性表之后，学生开始接触了较为复杂的数据结构――树。概念树是容易接受的，可一旦讲到对树的建立和运算等问题时，很多学生或多或少地会感到一些困惑，尤其是二叉树的遍历，看似简单的递归算法，可要理解其遍历过程，未必能够一目了然。
1提出问题
对于二叉树遍历过程的讲解，传统的讲法以递归算法为蓝本，加上图示的辅助，帮助学生理解该算法怎样实现在树的遍历中如何调用对子树的遍历，如何输出结点以及如何返回，返回到哪一个结点。由于学生接触的递归算法不多(最多在C语言、数据结构的“栈”中有所学习，而且C语言大多在大一第一学期学习，关于算法和递归等知识的理解不够)，所以理解不是很好，教起来也不轻松。多次讲解此处知识后我们发现，如果以二叉树的图示为蓝本讲解，使学生反向理解二叉树的遍历算法效果要好很多。这样，不仅使学生容易理解二叉树的遍历过程，而且对递归这一常用的算法设计方法也有更深刻的理解，下面将总结后的经验与大家共勉。
2“填空法”遍历二叉树
对二叉树中的任何一个结点来说，它都有自己的左、右子树(当然有些可视为空)。那么，对于三种遍历方法：前序、中序、后序，我们无非是将该结点作为根，然后按照一定的顺序去遍历该结点及其左、右子树，同时还能确定的是：无论哪种遍历，左子树必定在右子树之前遍历。因此，我们可以将整个树的遍历过程看作根在A(左子树遍历序列)B(右子树遍历序列)C这一过程中可能出现的A、B、C三个位置之一，进而，可将二叉树中任何一个结点的遍历视作上述过程。由此我们可以发现，无论是前序、中序、后序哪种遍历方式，都可以将遍历过程中的任何一步作为当前结点与其左、右子树遍历顺序的填空过程，只要确定了或前、或中、或后的遍历顺序，即确定了二叉树中任一结点在上述过程中的A或B或C的位置，进而将遍历的结点依次填写在对整个二叉树遍历序列的相应位置上。此时我们发现，整个遍历过程的重点已经不在左子树、根、右子树的遍历顺序上了，因为对每个结点来说，一旦遍历顺序定则三者位置定，重点转移到遍历到任一结点时，该结点在整个遍历序列中的具置上了，所以，由于位置的确定，先遍历左子树或是右子树已经不重要了。下面以一个具体的实例来说明填空法的详细讲解过程。
例求下图所示二叉树的中序遍历序列首先，为数中的所有结点标号(可用学生最易接受的层次遍历顺序依次为每层结点标号)，接下来便开始遍历，按照中序遍历的顺序，任一结点在以其为根的子树中的位置是(左子树)该结点(右子树)，因此，对于结点A，我们可以用(1左)A(1右)这样的公式来表示，接下来，无论我们先遍历A的左子树或右子树，则A及其左子树在遍历的序列中的位置是不变的，A的左子树是以B为根结点的，因此该子树的遍历序列可用(2左)B(2右)来表示，由于B右为空，B左只有一个结点D，因此，(2左)B(2右)所表达的遍历序列即DB，也即在(1左)A(1右)中的(1左)；再看(1右)是以C为根结点的子树，我们同样可以用(3左)C(3右)来表示该子树的中序遍历，以后的遍历过程依次类推，那么在讲课过程中，我们实际上就可以按照以下的填空步骤来讲解该二叉树的遍历过程。
( 1左 )A( 1右 )
(2左 )B( 2右 )A( 3左 )C( 3右 )
DB A(5左)E(5右)C(6左)F(6右)
DB A E G C H F
由此可得该二叉树的中序遍历序列为DBAEGCHF，那么同时我们也可以看出为什么在填空法中要为树中结点标唯一的号，这是因为在二叉树中，结点的名字是很可能不唯一的，假如在填空的过程中用A左、A右来表示其左右子树的话很容易与其他重名结点的遍历混淆，在结点较多的情况下，发生混淆的可能性就更大。同样的道理，若是前序遍历二叉树，那么可以用类似A(1左)(1右)这样的公式表示，后序遍历则是(1左)(1右)A来表示，填空的方法基本相同。
3总结
使用“填空法”讲授二叉树遍历的优是显而易见的，直观的讲述和演示使学生能够很快掌握二叉树遍历的过程。此外，在遇到较为复杂的二叉树需要写出遍历序列时，填空法更显示出它的优点，比如对表达式的线性化要求写出表达式的波兰式，填空法的使用比直接用传统法遍历的出错率大大降低。当树中有多个重名结点时，填空法利用了结点标号的方法避免了遍历过程中结点混淆的问题，遍历迅速且不易出错。
但是，这种方法不适用于简单二叉树，二叉树结构简单时，对结点的标号和填空倒是显得有些笨拙了。
由于经验有限，此方法只是在作者讲授的计算机专业“数据结构”课程和自动化专业的“软件技术基础”课程中使用，课堂上学生对这种方法表达出的浓厚兴趣是显而易见的。更重要的是，通过这种填空法的遍历结果再去讲解遍历的递归算法使学生更容易理解算法中有关递归调用和返回的过程。考试结果显示，在这两门课程中该知识点的满分得分率达到90%以上，可以说这种填空法比较地成功的运用于教学中。
参考文献
[1] 严蔚敏,吴伟民. 数据结构(C语言版)［M］. 北京:清华大学出版社,2007.
[2] 徐士良. 计算机软件技术基础［M］. 北京:清华大学出版社,2002.
A Discussion on Fill in Blanks Method to Teach Binary Tree Traversal
Yang Chun-Lei, Wu Qing-Tao, Zhang Hong-Yi
(Electronic & Information Engineering College OF HAUST HeNan LuoYang 471003)
Abstract：From the angle of teaching practice, this article states a question that students can’t easily catch the binary tree traversal on Data Structure course, and brings forward a new method of filling in blanks to resolve it. The goal of discussion on the fundamental and teaching mode to it is giving birth to students’ interest and improving the teaching effect.
Keywods：Fill in blanks method, Binary tree, Traversal