中序遍历二叉树的教学方法研究
开篇：润墨网以专业的文秘视角，为您筛选了一篇中序遍历二叉树的教学方法研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要： 结合教学中学生难以理解与掌握中序遍历二叉树这一实际情况，本文提出利用下压法进行二叉树的中序遍历，同时，利用栈的思想推导中序遍历二叉树的递归算法和非递归算法，清晰直观，便于学生更好的学习与理解。
关键词：二叉树；中序遍历；教学方法
中图分类号：TP311.12文献标识码：A文章编号：1009-3044(2011)09-2100-03
The Teaching Method Research of Inorder Traversing Binary Tree
CHEN Li-li1, LIU Qin-qin
(Software Engineering Department of Zilang Vocational Technical College, Nantong 226002, China)
Abstract: A pressing based method of inorder traversing binary tree is presented in this paper to slove the problem that student is difficult to understand and grasp inorder traversing binary tree.Meanwhile, using stack to derive recursive algorithm and non-recursive algorithm of inorder traversing binary tree. The process is clear and intuitional, which is more better for students to learn and understand.
Key words: Binary tree; Inorder traversal; Teaching methods
数据结构[1]是计算机程序设计的重要理论基础，该课程是计算机及其应用专业的一门重要基础课程。它不仅是计算机软件专业课程的先导课程，而且也逐渐为其他工科类专业所重视。开设该课程的目的在于让学生学会分析数据的特性、数据间的相互关系及其存储结构，以便于设计出效率高、结构好的程序，培养学生数据抽象和复杂程序设计的能力。
由于任何树都可以转换为二叉树进行处理，而二叉树又有许多好的性质和规律，非常适合于计算机处理，因此二叉树也是数据结构研究的重点。但在教学过程中，学生普遍反映这类知识内容抽象、不容易理解，相应的算法难以实现。针对该门课程教学中所存在的这个现状，作为任课教师必然会利用实例图示跟踪、实例演示等教学方法与手段来让学生更好的理解相关知识点。
1 二叉树遍历
在二叉树的一些应用中[5]，常常要求在树中查找具有某种特征的节点以及对相应节点进行某种处理，因而便提出了二叉树遍历这一概念，即如何根据某一方法或路径去访问树中的每个节点，并且每个节点又且仅有一次被访问。众所周知，遍历线性结构是很容易的，但对于具有非线性结构特性的二叉树则不尽然，因此必须寻找一定方法或规律来进行二叉树的遍历，使树上的节点能排列在一个线性队列上，从而便于访问所有节点。
根据二叉树的定义可知[1]，一棵非空的二叉树由根节点、左子树和右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整棵二叉树。若以N、L、R分别表示访问根节点、遍历根节点的左子树和遍历根节点的右子树，则二叉树的遍历方式有如下6种：NLR、LNR、LRN、NRL、RNL和RLN。前三种和后三种是对称的，如果限定先左后右，则有NLR（先序遍历）、LNR（中序遍历）和LRN（后序遍历）三种遍历方式。
2 传统二叉树中序遍历方法
2.1 中序遍历定义
若二叉树非空，则先中序遍历左子树，再访问根节点，最后中序遍历右子树。二叉树的遍历是一个递归的过程，左右子树均为遍历，根节点为访问。
2.2 传统中序遍历方法
以图1所示的二叉树为例进行中序遍历，中序遍历的递归过程是：若二叉树为空，则遍历结束。否则：
1) 中序遍历根节点的左子树；
2) 访问根节点；
3) 中序遍历根节点的右子树。
详细的遍历流程如图2所示。
根据访问顺序可以得出该二叉树的中序遍历结果序列为：DBGEACHFI。二叉树作为一种重要的数据结构，诸多教材均对其进行了详细的讲解，但学生对于二叉树中序遍历的方法和算法实现的理解有难度。下面介绍一种简单的方法用于获取二叉树的中序遍历结果序列。
3 简易二叉树中序遍历方法――下压法
通过上述的传统的中序遍历的方法可以看出，过程繁琐，而且学生在学习过程中，该遍历的递归调用及返回对他们来说是较难掌握的知识，很多学生进入递归后就不知道该如何层层返回，最终难以得出正确的中序遍历结果。
结合以上情况，在此补述一种简单的二叉树中序遍历的直观方法：下压法。结合传统中序遍历的方法来分析中序遍历的实质，即若二叉树非空，则先中序遍历左子数，再访问根节点，最后中序遍历右子树。我们不难发现，从直观上可以看出处于二叉树最左下方的节点应该是第一个要访问的节点。同时，二叉树是有序的，即其具有严格的左右子树之分的。基于以上特性我们得出简易的二叉树遍历方法下压法。
首先如图3所示将所需遍历的二叉树构造为一棵符合要求的二叉树，即在每一层上，将所有非空左子树完全位于当前根节点的左方，将所有非空右子树完全位于当前根节点的右方，同时构造该二叉树时一定注意，若当前节点有左（右）子树，则在构造时，左（右）子树不能超过当前根节点的上一层根节点的左边界。例如图示中的节点E、G、H三个节点的位置的准确摆放。然后如图4所示在该二叉树下放画一条水平直线。最后将树中各节点一起下压到这条水平线上，此时该水平直线上得到的节点序列即为该二叉树的中序遍历序列。我们以上图1为例，利用下压法进行操作，如图4所示，从而得到该二叉树的中序遍历序列为DBGEACHFI，与传统方法遍历的结果一致。
通过采用下压法，学生对理解二叉树的中序遍历比较直观，避免了学生对遍历的递归调用和返回的理解所存在的困难，以利于学生进行更深入的学习。
4 中序遍历二叉树的算法实现
下面以二叉链表作为存储结构，分别讨论中序遍历二叉树的递归算法和非递归算法。
定义二叉树的链式存储结构：
typedef struct BiTreeNode
{ elemtype data;
struct BiTreeNode *lchild,*rchild;
} BiTreeNode,* BiTree;
定义一个空栈：
typedef struct{
elemtype data[100];
int top;
}Stack;
Stack S;
4.1 递归算法
根据二叉树的递归定义[1]，可得中序遍历二叉树的遍历过程是：若二叉树为空，则遍历结束。否则，
1) 中序遍历根节点的左子树；
2) 访问根节点；
3) 中序遍历根节点的右子树。
根据以上可得其递归算法如下：
void InOrder(BiTree bt)
{ if(bt==NULL) return;
InOrder(bt->lchild);
Visit(bt->data);
InOrder(bt->rchild);
}
编译程序对上述程序代码进行编译时[8]，将为递归调用建立一个递归工作栈，该栈的每一个元素包含两个域，分别为返回地址域和参数域。对图1中的二叉树进行递归遍历时的栈内变化如表1所示。
可以看出中序遍历该二叉树时，访问节点的顺序为DBGEACHFI，与前述结果一致。因此，在教学过程中结合栈的思想进行讲授能让学生更直观的理解中序遍历二叉树的递归算法。
5.2 非递归算法
在实际的应用中，考虑到递归算法的时间复杂度大，效率低，因此在必要时，可采用非递归算法去解决相应的问题，以节省计算机执行算法的时间和空间。同样可利用栈结构来实现，具体算法如下：
void InOrder(BiTree bt)
{
BiTreeNode *p;
p=bt;
InitStack(S);
while(p!=NULL||!Empty(S)) //结束条件：p为空且栈为空
{
if(p!=NULL) //寻找最左端的左子树
{
Push(S,p);//如果该节点有左子树，则入栈
p=p->lchild;//当前指针指向下一个左子树
}
else
{
p=Pop(S); //出栈，得到当前要访问的节点
visit(p->data); //访问节点
p=p->rchild;//遍历右子树
}}}
在上述算法中，整个遍历过程没有涉及到递归的应用，而是通过循环语句以及终止条件来进行控制。算法思路清晰，易于理解。在讲授过程中伴以演示图例等将更利于学生直观的理解与掌握。
6 小结
综上所述，在这类知识点的讲授中，不一定拘泥于教材，可根据实际内容和学生情况，有针对性的选择和补充一些更利于学生理解的方法与思路。在实际的教学过程中，教师通过下压法讲授二叉树的中序遍历，直观明了，同时，结合相关演示软件利用栈的思想去理解二叉树的中序遍历，演示过程形象易懂，逻辑清晰，便于学生的学习与理解。
参考文献：
[1] 邓文华.数据结构(第2版)[M].北京:清华大学出版社,2007:88-91.
[2] 王昆仑,李红.数据结构与算法[M].北京:中国铁道出版社,2007:208-213.
[3] 崔俊凯.计算机软件基础[M].北京:机械工业出版社,2007:164-165.
[4] 徐孝凯.数据结构实用教程[M].北京:清华大学出版社,1999:175-178.
[5] 袁宇丽,胡玲.数据结构中二叉树中序遍历的教学分析[J].内江师范学院学报,2005.21(4):109-111.
[6] 张亚萍,陈得宝,侯俊钦.二叉树遍历教学方法研究[J].牡丹江师范学院学报（自然科学版）,2010.73(4):69-70.
[7] 郭金华,占明.浅议二叉树的遍历[J].科技信息,2010(17):65.
[8] 马相芬.中序遍历二叉树的算法实现[J].科技信息,2008(12):227.