摘 要： “数据结构”是计算机科学与技术专业的一门核心课程，是一门理论与实践相结合的课程。学生对这门课程的学习往往不能将前后知识相关联并用于解决实际问题，对此提出在教学过程中从表达式求值及遍历二叉树出发，引导学生将该知识点与进化计算相关联。延伸出数学函数所对应的二叉树生成算法，二叉数求值算法，二叉树绘图算法，并将二叉树表达的树形结构编码用于进化计算，从而实现产品的外观造型设计。教学结果证明，该关联教学法可以很好地提高学生的自主创新能力。
关键词： 自主创新； 数据结构； 二叉树； 进化计算
中图分类号：G40 文献标志码：A 文章编号：1006-8228（2013）05-54-03
Exploration in the associated teaching methods during the data structure teaching process
Gao Liping， Deng Guiying， Cao Chunping， Hu Demin， Li Rui
（School of Optical-Electrical and Computer Engineering， University of Shanghai for Science and Technology， Shanghai 200093， China）
Abstract： Data Structure is one of the core courses of computer science specialty. It"s a course requiring the combination of the theory and practice. During the learning process of this course， students tend to pay more attention to the mastery of the teaching materials， while lacking the ability to combine the knowledge front and behind to solve the practical problems. A demand to guide the students to relate the knowledge of the expression evaluation and the binary tree traversing with the evolutionary computation is introduced. It extends the binary tree creation algorithm， binary tree evaluation algorithm and the binary tree drawing algorithm which mathematical functions are corresponded. The tree structure is used to enhance computation and to achieve the appearance design of products. The teaching results show that the associated teaching methods can improve the students" capacity for independent innovation to some extent.
Key words： independent innovation； data structure； binary tree； evolutionary computation
0 引言
数据结构[1]是计算机专业的专业基础课，属于主干和核心课程。数据结构的学习目的是让学生理解和掌握各种数据结构的定义及基本操作的实现，理解和掌握典型算法的基本思想、算法设计方法和计算算法的时间复杂度。使学生通过学习，掌握经典算法的编程方法和技巧，提高编程能力。这门课程的学习，不仅巩固了前导课程（如程序设计、离散数学等）知识，而且为后续课程（如算法设计与分析、人工智能、计算机图形学）的学习提供了基础[4]。
计算机专业的本科生在毕业之后往往选择从事IT领域的研发工作，而目前大型企业往往对应聘者的创新能力有较高的期望值。公司在决定是否接纳应聘者之前，通常需要对应聘者进行电话或者面试，而面试的主要内容则来源于实际问题中所抽象出来的分支问题。应聘者需要在给定时间内针对具体问题，进行相应的数据结构的设计，并基于所选择的数据结构，进行算法设计及效率分析。这就要求应聘者除了具有扎实的课本知识，还要能够灵活运用所学知识解决实际问题。因此，在授课过程中，教师除了讲解课本知识外，还应该对各种问题求解进行引申与延展，以促进学生创新思维能力的开发。
本文从“表达式求值”及“遍历二叉树”知识点出发，延伸出树形结构的进化计算技术，提出在二者之间通过二叉树生成、二叉树进化操作、二叉树求值、二叉树绘图、二叉树遍历等进行关联，从而在理论与实践之间构架一座桥梁。实验证明，该方法对于提高学生的自主创新能力具有十分重要的意义。
1 表达式求值
表达式求值是程序设计语言编译中的一个最基本的问题，它的实现往往采用“算符优先法”。例如4+2*3-10/5的计算顺序为：4+2*3-10/5=4+6-10/5=10-10/5=10-2=8。首先算法会比较+和*的优先级，发现*的优先级高于+，故首先执行2*3的运算，得到4+6-10/5这个表达式，之后再进行+和-的优先级比较，发现+的优先级高于-，故执行4+6的运算，得到10-10/5这个表达式，此后再进行-和/的优先级比较，发现-的优先级低于/的，故执行10/5的运算，得到10-2的表达式，最后算出最终结果为8。
从以上分析中可以看出，任何一个表达式都是由操作数和操作符组成，在表达式求值过程中通过不断地比较相邻两个运算符之间的优先级，来确定参加运算的运算数，并需要存储临时计算结果。这个过程可以通过定义操作符优先矩阵，并控制操作符及操作数栈的入栈和出栈顺序来实现。
在算符优先法中，主要通过堆栈这个数据结构完成对表达式的求值，且仅适用于双目运算符，无法提供对单目运算符（如sin，cos，exp等）的支持，并且也不能支持对表达式的自由变更。
2 遍历二叉树
二叉树的遍历分为前序、中序和后序遍历。前序遍历按照“根结点-左子树-右子树”的顺序完成对二叉树的访问；中序遍历按照“左子树-根结点-右子树”的顺序完成对二叉树的访问；后序遍历按照“左子树-右子树-根结点”的顺序完成对二叉树的访问。如图1所示的二叉树，经过中序遍历后，得到的中序序列为：a+b*c-d-e/f。
[a] [b][c] [d] [e] [f] [+] [-] [*] [/] [-]
图1 表达式a+b*（c-d）-e/f的二叉树
该二叉树结构能够支持表达式的自由变换，但当需要通过遍历生成所需要的表达式时，却没有根据运算符的优先级加括号，因此会产生与原表达式不一致的状态。例如图1所产生的表达式a+b*c-d-e/f与原表达式a+b*（c-d）-e/f含义不同。
3 基于树形结构的进化计算技术
进化计算[2]是模拟自然界生物进化过程的计算模型。它依据适者生存、优胜劣汰的进化规则对包含可能解的群体反复进行遗传操作（交叉、变异、选择），不断产生新的个体。
进化计算可以采用多种编码方式：二进制编码、实数编码及树形编码。一棵用数学表示的二叉树是一个数学操作数及数学操作符的有限节点集，该集或者是空集，或者是由根及两棵互不相交的，称为左、右子树的二叉树组成。二叉树的中序遍历序列是一个合法的数学表达式。树的节点可以是终端节点（操作数）或者是中间节点（操作符）。操作数可以是变量，也可以是常量，操作符包括基本运算符+，2，3，/，^，基本数学函数sqrt（），exp（），log（），三角函数sin（），cos（），tan（），asin（），acos（），atan（）以及双曲函数sinh（），cosh（），tanh（），asinh（），acosh（），atanh（）等。例如图1所示的二叉树就是个体a+b*（c-d）-e/f所对应的树形结构编码。基于树形编码的交叉和变异操作如图2和图3所示。
[A][B][A][B]
图2 树结构编码的进化计算的交叉操作
[A][移除的子树][用新子树替换
移除的子树][A]
图3 树结构编码的进化计算的变异操作
将基于树形结构编码的进化计算技术用于辅助设计领域，可以构造出奇异、梦幻、各种美轮美奂的图形和形状[5]，如图4所示。
图4 基于进化计算的辅助设计环境
在讲解完二叉树遍历这部分内容时，首先跟同学一起回顾二叉树求值的内容，之后，给出支持进化的辅助设计环境，以引发学生对这二者之间相互关联的探索兴趣。通过讨论得出如下结论：要能够支持树形结构编码的进化计算，首先我们需要设计相应的算法，将给定的表达式转化成二叉树表示，支持交叉和变异操作，之后能根据给定的变量值进行表达式求值，并根据求得的值进行图形显示，最后通过遍历得到字符串结构的表达式形式。
4 二叉树生成算法
算法1 生成数学函数的二叉树表示（CreateBiTree）
输入：S表示数学函数对应的字符串，low表示字符串的起点，high表示字符串的终点。
输出：tr表示数学函数对应的二叉树。
{ if （low和high位置上的左右括号配对出现）
脱括号（low++；high--）；
自左至右找出S串中low到high之间优先级最高的操作符，记为
Oper，Oper在S中的位置记为k。
if （Oper存在） {
tr->left=CreateBiTree（s，low，k-1）；//递归调用建立左子树
tr->right=CreateBiTree（s，k+Oper.Length（）+1，high）；
//递归调用建立右子树
}
tr=new CBiTree；
tr->data=Oper；
}
5 树形结构编码的交叉和变异算法
算法2 基于二叉树的交叉和变异算法（TreeCross）
输入：tr1，tr2分别代表两颗待执行交叉或变异操作的二叉树。
输出：tr1，tr2分别代表执行交叉或变异之后的二叉树。
{ if（tr1==NULL||tr2==NULL） return；
int len1=TraversTree（tr1）； //求出第一棵二叉树目前的节点个数
int len2=TraversTree（tr2）； //求出第二棵二叉树目前的节点个数
int sel1=rand（）%len1+1； //随机产生交叉点
int sel2=rand（）%len2+1； //随机产生交叉点
//以下进行交叉操作
TreeSelect（tr1，parent1，sel1，flag1）； //获取待交叉节点的父亲结点，存入parent1；flag1用来记录tree1是父亲结点的左/右孩子结点。
TreeSelect（tr2，parent2，sel2，flag2）；
//获取待交叉节点的父亲结点，存入parent2；
按照flag1和flag2的4种组合进行指针交换操作；
}
6 基于二叉树的求值算法
算法3 利用二叉树求解数学函数的值（CalByTree）
输入：tr表示数学函数对应的二叉树，x表示自变量的取值。
输出：f表示函数的值。
{ if （tr->data不是操作符） return x；
f1=CalByTree（tr->left，x）；
f2=CalByTree（tr->right，x）；
f=Cal（f1，tr->data，f2）；
}
7 二叉树所对应的三维图形的显示算法
算法4 二叉树所对应的三维图形显示（GraphicShow）[3]
输入：tr表示数学函数对应的二叉树，low和high表示自变量的取值范围，density表示曲线的平滑度。
输出：屏幕上图形显示结果。
{ 将low与high之间分成density份，对每一份求值置入数组
Point[density]中；
for （i=0； i api_solid_cylinder_cone（position（point[i].x，0，0）， position（point[i+1].x，0，0）， point[i].y，point[i].y， point[i+1].y， NULL，my_body ）； //构造圆柱体 Save（my_body）； //显示图形 } 8 改进的二叉树遍历算法 算法5 从二叉树结构出发构建字符串表示的表达式（ReConstruct） 输入：tr表示数学函数所对应的二叉树。 输出：字符串所表示的表达式。 { temp=tree->data； if （temp是操作数） return temp； if （temp是单目运算符） return temp+"（"+ReContruct（tree->right）+"）"； //如果temp是双目运算符 CString ltemp， rtemp； Int lflag， rflag； ltemp=tree->left->data； rtemp=tree->right->data； if （ltemp是操作符） if （level（ltemp，0） //比较ltemp与temp的优先级 if （rtemp是操作符） if （level（rtemp，0） //比较rtemp与temp的优先级 if （lflag） //子树的优先级低于根结点，需要加括号 temp="（"+ReContruct（tree->left）+"）"+temp； else //子树的优先级高于根结点 temp=ReContruct（tree->left）+temp； if （rflag） temp=temp+"（"+ReContruct（tree->right）+"）"； else temp=temp+ReContruct（tree->right）； return temp； } 9 结束语 数据结构课程是计算机科学与技术专业的一门非常重要的核心课程，担负着构架程序设计、算法设计与分析之间桥梁的重要任务，所学知识是学生走上社会岗位所必备的。传统的授课模式一般以课本知识为重点，鲜少进行基础知识与前沿科学之间的关联和讨论。本文从表达式求值及二叉树遍历两个知识点出发，延伸出数学函数所对应的二叉树生成算法，二叉树求值算法，二叉树绘图算法，并将二叉树表达的树形结构编码用于进化计算，从而实现产品的外观造型设计。课堂教学效果显示，该方法对于提高学生理论与实践的关联能力、提高学生独立思考和解决问题的能力具有十分重要的意义。 参考文献： [1] 严蔚敏，吴伟民.数据结构（C语言版）[M].清华大学出版社，2011. [2] 王正志，薄涛.进化计算[M].国防科技大学出版社，2000. [3] 杨晓波，陈邦泽.二叉树的可视化实现[J].国际IT传媒品牌，2011.32： 24-27 [4] 许自龙.关于《数据结构》的教学实践和体会[J].信息技术教学与研 究，2012.4：120-121 [5] 高丽萍，刘弘.支持创新设计的多Agent系统[J].计算机应用研究， 2003.10：18-21