基于几何学的二叉树遍历教学设计研究

魏霞　郑胜

[摘 要]本研究通过把几何学的相关知识迁移到《数据结构》教学中，应用几何学的对称特性和等腰三角形巧解二叉树前序遍历、中序遍历和后序遍历。把文字描述变为图形表述，思路清晰明了，教学效果显著。

[关键词]数据结构；二叉树；遍历；几何学；教学设计

[中图分类号] O18 [文献标识码] A [文章编号] 2095-3437（2016）03-0155-03

《数据结构》是计算机专业一门重要的基础课，树形结构是《数据结构》课程中的一种非线形数据结构。二叉树是树形结构的重点，也是难点。遍历是二叉树中一个最重要的运算，是在二叉树上进行其他运算的基础。因此，掌握二叉树遍历相当重要。[1]然而，二叉树是一种非线性结构，其遍历不像线性链表那样容易，无法通过简单的循环实现。如何通过简便可行的、通俗易懂的方法，让学生理解和掌握二叉树遍历，值得广大教师探索、研究。

一、二叉树遍历算法

二叉树遍历就是指按照一定的规则和顺序，依次对树中的所有结点做一次且仅被访问一次，即按一定规律排列成一个线性队列。[2]二叉树是一种递归定义的结构，包含根结点（N）、左子树（L）、右子树（R）三个部分。根据访问根结点与左右子树先后进行命名，二叉树的遍历有三种方式：前序遍历（NLR）、中序遍历（LNR）、后序遍历（LRN）。对于这种传统的方法，教师讲解起来非常简单，但是学生比较难以掌握与应用。特别是在做一些遍历运算的题目时，虽然学生上课时听得明白，但是做起题目来却无从下手，思绪混乱。

二、几何学在二叉树遍历教学中的灵活应用

我们每个人都比较熟悉几何学，尤其是对称性和等腰三角形。如何将我们熟知的几何学应用于二叉树这一复杂的数据结构教学中，简化复杂的问题呢？本文将充分应用牵移法思想，基于几何学的浅显概念及属性，将几何学与二叉树遍历教学联系起来，让二叉树遍历教学由繁变简，让学生能够深刻掌握并灵活应用所学知识。

（一）应用对称对比，掌握二叉树遍历算法定义

从上述的前序遍历、中序遍历和后序遍历三种遍历的递归算法对比分析，可以以一个对称性图形对三类遍历类型进行教学。通过对比，可以让三类遍历类型简单明了、通俗易懂。图1是二叉树遍历类型图。

图1演示了二叉树三种遍历的过程。从整体来看，图1是一个对称的图形；从中序遍历本身来看，它也是一个单独的对称图形。图1演示图应用了软件工程UML图形设计元素、开始和结束的图形标记，可以让学生通过图形，了解二叉树的三种遍历的对比关系。

（1）开始：前序遍历开始在根结点，中序遍历开始在左子树，后序遍历开始也在左子树；

（2）结束：前序遍历结束在右子树，中序遍历结束也在右子树，后序遍历结束在根结点；

（3）根结点遍历情况：前序遍历的根结点最先遍历，中序遍历的根结点在中间遍历，后序遍历的根结点最后遍历。

（二）应用等腰三角形巧解二叉树遍历的运算

若要写出图2二叉树的三种遍历，很多学生无法理出一个清晰的思路。在此，本论文引入等腰三角形这个几何图形。

从图2可见，A、B、C三个结点就好比一个三角形的三个点，其中，B、C为底点，因而A、B、C三个结点可以组成一个等腰三角形；B、D、E三个结点也好比一个三角形的三个点，其中，D、E为底点，因而B、D、E三个结点可以组成一个等腰三角形；以此类推，可以把二叉对所有结点进行组合，看做多个三角形的组合体。而对于像CF、FH和DG这种只有两个结点的，我们可以假设其存在第三个点，比如，对于D、G两个结点，可以假设其还存在一个左子树结点，虚拟一个等腰三角形。在应用等腰三角形进行遍历书写时，我们将按照从上到下，一层一层地查找三角形。这种不会出现混淆情况。以下是图3所示的二叉树的三种遍历巧解过程。

1.前序遍历巧解过程

如图3所示，按照①②③④⑤五个等腰三角形的顺序，逐一按前序遍历的定义书写二叉树各结点，并结合图1所示二叉树遍历的规则，从上到下、从左向右，按顺序写出二叉树遍历。其步骤如下：

第一步，写第①个等腰三角形所在三个结点，这三个结点的前序遍历是ABC。

第二步，写第②个等腰三角形所在三个结点，这三个结点的前序遍历是BDE。此时，结合第一步所得，综合得到一个遍历顺序ABDEC。也可这么理解，即相当于用遍历BDE替换了遍历ABC中的B。

第三步，写第③个等腰三角形所在三个结点，这个三角形没有左底点，即以C为父结点的二叉树没有左子结点，即为空，在此，我们以“□”表示。同样，根据前序遍历规则，这三个结点的前序遍历是C□F，在第二步综合得到的遍历顺序ABDEC的基础上，通过替换，可以得到一个新的遍历ABDEC□F。道理与第二步相同，即相当于用遍历C□F替换了遍历ABDEC中的C。

第四步，写第④个等腰三角形所在三个结点，这个三角形也没有左底点，如第三步一样，我们以“□”表示。同样，根据前序遍历规则，这三个结点的前序遍历是D□G，在第三步综合得到的遍历顺序ABDEC□F的基础上，通过替换，可以得到一个新的遍历ABD□GEC□F。道理与第二步相同，即相当于用遍历D□G替换了遍历ABDEC□F中的D。

第五步，写第⑤个等腰三角形所在三个结点，这个三角形没有右底点，如第三步一样，我们以“□”表示。同样，根据前序遍历规则，这三个结点的前序遍历是FH□，在第四步综合得到的遍历顺序ABD□GEC□F的基础上，通过替换，可以得到一个新的遍历ABD□GEC□FH□。道理与第二步相同，即相当于用遍历FH□替换了遍历ABD□GEC□F中的F。

第六步，①②③④⑤五个等腰三角形都已按前序遍历规则逐一遍历到，最终得到了ABD□GEC□FH□遍历。此时，我们把“□”去掉，最终得到了遍历ABDGECFH，应用传统二叉树遍历解法进行检验，ABDGECFH就是图2所示的二叉树的前序遍历。

2.中序遍历巧解过程

如图3所示，按照①②③④⑤五个等腰三角形的顺序，逐一按中序遍历的定义书写二叉树各结点，并结合图1所示二叉树遍历的规则，从上到下、从左向右，按顺序写出二叉树遍历。其步骤如下：

第一步，写第①个等腰三角形所在三个结点，这三个结点的中序遍历是BAC。

第二步，写第②个等腰三角形所在三个结点，这三个结点的中序遍历是DBE。此时，结合第一步所得，综合得到一个遍历顺序DBEAC。也可这么理解，即相当于用遍历DBE替换了遍历BAC中的B。

第三步，写第③个等腰三角形所在三个结点，这个三角形没有左底点，即以C为父结点的二叉树没有左子结点，即为空，在此，我们以“□”表示。同样，根据中序遍历规则，这三个结点的中序遍历是□CF，在第二步综合得到的遍历顺序DBEAC的基础上，通过替换，可以得到一个新的遍历DBEA□CF。道理与第二步相同，即相当于用遍历□CF替换了遍历DBEAC中的C。

第四步，写第④个等腰三角形所在三个结点，这个三角形也没有左底点，如第三步一样，我们以“□”表示。同样，根据中序遍历规则，这三个结点的中序遍历是□DG，在第三步综合得到的遍历顺序DBEA□CF的基础上，通过替换，可以得到一个新的遍历□DGBEA□CF。道理与第二步相同，即相当于用遍历□DG替换了遍历DBEA□CF中的D。

第五步，写第⑤个等腰三角形所在三个结点，这个三角形没有右底点，如第三步一样，我们以“□”表示。同样，根据中序遍历规则，这三个结点的中序遍历是HF□，在第四步综合得到的遍历顺序□DGBEA□CF的基础上，通过替换，可以得到一个新的遍历□DGBEA□CHF□。道理与第二步相同，即相当于用遍历HF□替换了遍历□DGBEA□CF中的F。

第六步，①②③④⑤五个等腰三角形都已按中序遍历规则逐一遍历到，最终得到了□DGBEA□CHF□遍历。此时，我们把“□”去掉，最终得到了遍历DGBEACHF，应用传统二叉树遍历解法进行检验，DGBEACHF就是图2所示的二叉树的中序遍历。

3.后序遍历巧解过程

如图3所示，按照①②③④⑤五个等腰三角形的顺序，逐一按后序遍历的定义书写二叉树各结点，并结合图1所示二叉树遍历的规则，从上到下、从左向右，按顺序写出二叉树遍历。其步骤如下：

第一步，写第①个等腰三角形所在三个结点，这三个结点的后序遍历是BCA。

第二步，写第②个等腰三角形所在三个结点，这三个结点的后序遍历是DEB。此时，结合第一步所得，综合得到一个遍历顺序DEBCA。也可这么理解，即相当于用遍历DEB替换了遍历BCA中的B。

第三步，写第③个等腰三角形所在三个结点，这个三角形没有左底点，即以C为父结点的二叉树没有左子结点，即为空，在此，我们以“□”表示。同样，根据后序遍历规则，这三个结点的后序遍历是□FC，在第二步综合得到的遍历顺序DEBCA的基础上，通过替换，可以得到一个新的遍历DEB□FCA。道理与第二步相同，即相当于用遍历□FC替换了遍历DEBCA中的C。

第四步，写第④个等腰三角形所在三个结点，这个三角形也没有左底点，如第三步一样，我们以“□”表示。同样，根据后序遍历规则，这三个结点的后序遍历是□GD，在第三步综合得到的遍历顺序DEB□FCA的基础上，通过替换，可以得到一个新的遍历□GDEB□FCA。道理与第二步相同，即相当于用遍历□GD替换了遍历DEB□FCA中的D。

第五步，写第⑤个等腰三角形所在三个结点，这个三角形没有右底点，如第三步一样，我们以“□”表示。同样，根据后序遍历规则，这三个结点的后序遍历是H□F，在第四步综合得到的遍历顺序□GDEB□FCA的基础上，通过替换，可以得到一个新的遍历□GDEB□H□FCA。道理与第二步相同，即相当于用遍历H□F替换了遍历□GDEB□FCA中的F。

第六步，①②③④⑤五个等腰三角形都已按后序遍历规则逐一遍历到，最终得到了□GDEB□H□FCA遍历。此时，我们把“□”去掉，最终得到了遍历GDEBHFCA，应用传统二叉树遍历解法进行检验，GDEBHFCA就是图2所示的二叉树的后序遍历。

三、结语

在计算机专业里，数据结构是一门规律性很强的学科。我们可以通过建模，使数据结构可视化，反映出其中的规律。我们的日常生活也蕴藏着很多规律，我们可以通过联想迁移的方法，用生活中司空见惯的常识来解决复杂的问题。数据结构在计算机教学中，虽然看起来非常复杂，但通过数据挖掘、数学建模，数据结构能在很多日常的生活上得以反映，并能让数据结构教学化繁为简，提高教学效率。本文从几何学中最通俗的对称性和等腰三角形进行挖掘，查找出了它们与二叉树这一非线形数据结构的潜在联系，把复杂的问题简单化。这样在教学过程中，学生容易接受，教师讲授也显得轻松。

[ 参 考 文 献 ]

[1] 乔良才，赵奇.二叉树教学方法研究[J].攀枝花学院学报，2012（2）：124-126.

[2] 陈莉莉，刘琴琴.中序遍历二叉树的教学方法研究[J].电脑知识与技术，2011（9）：2100-2102.

[责任编辑：钟伟芳]