维普资讯 http://www.cqvip.com ６ 宋玲吕强《数据结构》中－－ｙ．．树的教学方法探讨 《数据结构》中二叉树的教学方法探讨 Ｓｔｕｄｙ ｏｎ ｔｈｅ ｍｅｔｈｏｄ ｏｆ ｂｉｎｔｒｅｅ ｉｎ｛ｄａｔａ ｓｔｒｕｃｔｕｒｅ）） 宋玲 吕 强 ２５００１４ ２．山东电力研究院济南２５０００２ １．山东建工学院计算机系 济南【摘 要】本文概括、分析了《数据结构》课程的特点，针对二叉树，结合教学工作中存在的问 题。运用１美国学者Ｋｅｌｌｅｒ提出的ＡＲＣＳ动机模型和积累的实践经验提出相应的课改方案。最 后。给出了网上辅助学习的有关设想。 【关键词】数据结构 算法 教法 二叉树 在线学习 【中图分类号】ＴＰ３１１．１２ Ｇ４２７ １ 引言 【文献标识码】Ａ 方式及其相应的运算。数据之间的逻辑关系，大致 有四种：线性结构、树形结构、图状结构和集合。数 据的存储结构指数据在计算机中的存储形式—— 顺序方式和链式方式。数据的基本运算为：建立、查 找、插入、删除、更新等。数据结构课程的内容包括 五个要素．如下图所示．分别是数据的逻辑结构、存 储结构、基本运算、相应的算法以及算法复杂性分 析。 ＼层次数据结构是计算机存储、组织数据的方式。在 程序的设计中。数据结构的选择是一个最基本也是 最重要的考虑因素。许多大型软件系统的构造经验 表明。系统实现的困难程度和系统构造的质量都严 重依赖于是否选择了最优的数据结构。数据结构和 算法是密不可分的。但决定系统构造的关键因素是 数据结构而不是算法。 《数据结构》作为计算机科学与技术专业的专 业基础课程，是一门核心课程。通过本课程的学习， 方面 、＼ 抽象 实现 评价 数据表示 逻辑结构 存储结构 数据处理 基本运算 算 法 使学生能够从具体问题抽象出一个适当的数学模 型，也就是对应用所涉及的实际问题进行分析，从 中抽取操作对象，并根据数据对象之间的关系，选 择适合的数据结构组织数据，然后设计一个解决此 数学模型的算法，并初步掌握算法分析的能力，最 后应用一门高级程序设计语言来实现。所以这门课 程既可以锻炼学生的逻辑思维和抽象思维能力，又 培养学生综合运用离散数学、程序语言、程序设计 方法等相关知识来解决问题的能力。对这门课的理 解、掌握和拓展，将对学生编程能力有着深远的影 响．同时为后续课程的学习和从事软件开发奠定坚 实的基础。概括来说，数据结构指数据之间的关系， 不同结构的比较及算法分析 由于树型结构是一类重要的非线性数据结构， 本文将以二叉树为例来分析教学过程中存在的问 题以及相应的解决方法。 ２教学过程中存在的问题 在教学过程中．发现学生在学习这门课的过程 中存在一些障碍，究其原因，主要有以下几个方面： （１）前导课程学得不扎实。主要表现在数学知 识比较薄弱，在进行算法分析时，学生存在的问题 较多。另外一个比较突出的问题是有关的高级程序 设计语言不能熟练应用。在“数据结构”中的算法大 都由类ＰＡＳＣＡＬ或类Ｃ描述而成，ＰＡＳＣＡＬ或Ｃ语 言作为数据结构的前导课程已讲授过了。但学生对 包括数据之间的逻辑关系、数据在计算机中的存储 作者简介：宋玲，女，山东建工学院讲师，山东大学在读博士生， 主要从事计算机应用研究。 计算机语言的理解较为浅显。无法得心应手地应用 维普资讯 http://www.cqvip.com 山东电力高等专科学校学报 第９卷（２ｏｏ６） Ｊｏｕｒｎａｌ ｏｆ Ｓｈａｎｄｏｎｇ Ｃｏｌｌｅｇｅ ｏｆ Ｅｌｅｃｔｒｉｃ Ｐｏｗｅｒ §摹蘧墨＝≯器 ｑ ｔ丰 ｑ 脯●嘴矗翻 第２期 ｑ ■●抽硎●瞧 ■直ｔ量 ７ Ｃ、ＰＡＳＣＡＬ等高级程序设计语言来解决问题。学生 程序设计的方法和思想也不够成熟。 （２）上机课时不充足、学生的程序调试能力欠 缺。算法本身比较抽象。关于某种数据结构的基本 操作的算法描述也比较分散．学生不容易系统地理 解整个抽象数据类型。教材中用类ＰＡＳＣＡＬ或类Ｃ 语言的方法来描述算法。并且只描述出其主体部 分，其它部分如局部变量定义等经常被忽略掉，对 母 嚣 矗仔 ¨恚 ／ ＼ ／ ／ ＼ ＼ Ｕ ／ ／ ／ ／、 ／ 、 于学生来说，不容易系统学习和上机实现。 （３）学生缺乏完整体系思想。计算机科学本身 是一个完整、系统的专业，对学生而言，一门一门课 程去学，课程之间不能融会贯通，将所学课程孤立 起来。另外学时有限，对某些章节不可能讲深讲透， 造成学生前后知识点之间隔离．不能及时消化和融 会贯通。 （４）学生的重视程度不够。目前各种可视化化 程序设计方法很多。借助于集成开发环境可以很快 地生成程序。一些学生认为只要掌握几种开发工具 就可以成为编程高手。根本没有必要花大力气学习 专业课。另外学生低估了本课程学习的难度。遇到 困难时，自信心不足，当困难积累到一定程度，往往 知难而退。甚至放弃。 ３ 改进方法 本文运用美国学者Ｋｅｌｌｅｒ提出的ＡＲＣＳ动机模 型。针对这些存在的问题并结合教学过程中的经验 和教训，以二叉树为例提出相应的教学改进方法。 （１）注意力（ａｔｔｅｎｔｉｏｎ）：抓住学生的注意力激发 和维持学习动机。针对数据结构的五个要素，在二 叉树的讲解中贯穿一条主线。即逻辑结构、存储结 构、如何通过算法实现基本运算。二叉树的逻辑结 构是非线性的。它的定义、有关术语和性质比较抽 象，存储方式既可顺序存储又可链式存储。顺序存 储仅适用于完全二叉树，链式存储比较灵活。应用 较广。这些内容借助于多媒体教学。以生动、形象、 灵活的方式激发学生的学习兴趣。通过多个感官来 获取信息。二叉树基本运算为建树、前序、中序、后 自 序遍历。针对具体的算法，通过《数据结构算法演示 系统》教学，在算法演示中将函数调用、具体实例和 算法执行过程中变量当前值的变化显示给学生。直 观生动。下图为二叉树的中序遍历递归算法的演 示。沿着这条主线展开。始终紧紧地抓住学生的注 意力。见图ｌ ／ ／ Ｕ 结果：ＪＴ 图１ （２）相关性ｒｅｌｅｖａｎｃｅ）：强调知识前后的连续性 和相关性。比如以中序遍历为例，在讲解之前，应该 让学生清楚如何建立起一棵二叉树。然后再进行中 序递归遍历，通过算法演示和讲解让学生掌握递归 过程中系统设立的“递归工作栈”的使用。这样既复 习了前面栈的知识。又巩固了中序遍历递归算法的 理解，并通过这个递归算法分析推导出非递归中序 遍历算法；见算法１、算法２、算法３。 ｔｙｐｅｄｅｆ ｃｈａｒ ＳｅｌｅｍＴｙｐｅ； ｔｙｐｅｄｅｆ ｃｈａｒ ＴＥｌｅｍＴｙｐｅ； ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ＢｉＴＮｏｄｅ｛ 结点结构｝／ ＴＥｌｅｍＴｙｐｅ ｄａｔａ； ｓｔｒｕｃｔ Ｂｉ Ｉ’Ｎｏｄｅ ｌｃｈｉｌｄ． ｒｃｈｉｌｄ； 左右孩子指针 ／ ｝ＢｉＴＮｏｄｅ， ＢｉＴｒｅｅ； ｖｏｉｄ ＩｎＯｒｄｅｒＴｒａｖｅｒｓｅ（ＢｉＴｒｅｅ＆ １ｆ 中序递归遍历二叉树｝／ ２ ｉｆ（Ｔ） ３｛ ４ ＩｎＯｒｄｅｒＴｒａｖｅｒｓｅ（Ｔ—－＞ｌｃｈｉｌｄ）； 中序遍历左子树 ／ ５ ｐｒｉｎｆｆ（”％ｃ”，Ｔ一＞ｄａｔａ） 访问根节点｝／ ６ ＩｎＯｒｄｅｒＴｒａｖｅｒｓｅ（Ｔ—－＞ｒｃｈｉｌｄ）； 中序遍历右子树 ／ ７ ｝ ８｝ 算法１ 算法１中。通过图１中序遍历递归算法执行过 程中的递归工作栈的状态可见： （１）工作记录中包含每一层递归所需信息构成 一个“工作记录”。其中包括递归调用的语句编号 维普资讯 http://www.cqvip.com ８ 宋玲 吕 强《数据结构》中二叉树的教学方法探讨 （返回地址）和指向根结点的指针（实在参数），当栈 顶记录中的指针值为非空时，应遍历左子树，即指 向左子树根的指针进栈。 （２）若栈顶记录中的指针值为空，则退至上一 层，若是从左子树返回，则访问当前层的根结点。 （３）若从右子树返回，则表明当前层的遍历结 束，应继续退栈。 从以上分析可知，在找到最左下结点之前，一 直进栈。我们在非递归遍历中将用ＧｏＦａｒＬｅｆｌ（Ｂｉ． Ｔｒｅｅ Ｔ，ＳｑＳｔａｃｋ＆Ｓ）实现，见算法２。开始访问最左 下结点，然后根据它是否存在右子树分别处理。见 算法３ ＢｉＴＮｏｄｅ ＧｏＦａｒＬｅｆｌ（ＢｉＴｒｅｅ Ｔ，ＳｑＳｔａｃｋ＆Ｓ） 找 到最左下节点｝／ ｛ ｉｆ（！Ｔ）ｒｅｔｕｒｎ ＮＵＵＪ； ｗｈｉｌｅ（Ｔ－＞ｌｃｈｉｌｄ） ｛Ｐｕｓｈ（Ｓ， ； Ｔ＝Ｔ－＞ｌｃｈｉｌｄ； ｌ ｒｅｔｕｍ Ｔ： ｌ 算法２ ｖｏｉｄ Ｉｎｏｒｄｅｒ＿Ｉ（ＢｉＴｒｅｅ＆ ｛ 中序非递归遍历二 叉树 ／ ＳｑＳｔａｃｋ Ｓ；ＢｉＴｒｅｅ ｔ； ＳＥｌｅｍＴｙｐｅ ｅ： ＩｎｉｔＳｔａｃｋ（Ｓ）； ｔ＝ＧｏＦａｒＬｅｆｔ ｆｒ，Ｓ）∥找到最左下的结点 ｗｈｉｌｅ（０｛ ｐｒｉｎｆｆ（”％ｃ”．ｔ－＞ｄａｔａ）； ｉｆ（ｔ－＞ｒｃｈｉｌｄ） ｔ＝ＧｏＦａｒＬｅｆｌ（ｔ－＞ｒｃｈｉｌｄ，Ｓ）； ｅｌｓｅ ｉｆ（！ＳｔａｃｋＥｍｐｔｙ（Ｓ））／／栈不空时退栈 ｔ＝Ｐｏｐ（Ｓ，ｅ）； ｅｌｓｅ ｔ＝ＮＵＬＬ；／／栈空表明遍历结束 ｌ／／ｗｈｉｌｅ ｌ／／Ｉｎｏｒｄｅｒ＿Ｉ 算法３ 继续分析二叉树遍历的动态特性来导出线索 二叉树的建立，添加一头结点，为了记下遍历过程 中访问结点的先后关系，附设指针ｐｒｅ始终指向刚 刚访问过的结点。线索化的过程即为修改指针的过 程。见算法４、算法５。 ＢｉＴｈｒＮｏｄｅ ｐｒｅ； ｖｏｉｄ ＩｎＴｈｒｅａｄｉｎｇ（ＢｉＴｈｒＴｒｅｅ＆ ｛ ｉｆ （，，对以Ｐ为根的非空二叉树进行线索化 ＩｎＴｈｒｅａｄｉｎｇ ＞ｌｃｈｉｌｄ）；／／左子树线索化 ｉｆ（！Ｔ－＞ｌｃｈｉｌｄ１ ／／建前驱线索 ｛Ｔ－＞ＬＴａｇ＝Ｔｈｒｅａｄ； Ｔ－＞ｌｃｈｉｌｄ＝ｐｒｅ；｝ ｉｆ ｆ！ｐｒｅ一＞ｒｃｈｉｌｄ１／／建后继线索 ｛ｐｒｅ一＞ＲＴａｇ＝Ｔｈｒｅａｄ； ｐｒｅ－＞ｒｃｈｉｌｄ＝Ｔ；ｌ ｐｒｅ＝Ｔ．ｇ保持ｐｒｅ指向Ｔ的前驱 ＩｎＴｈｒｅａｄｉｎｇ ＞ｒｃｈｉｌｄ）；／／右子树线索化 、｜｜ ｌ／／ＩｎＴｈｒｅａｄｉｎｇ 算法４ ｖｏｉｄ ＩｎＯｒｄｅｒＴｈｒｅａｄｉｎｇ（ＢｉＴｈｒＴｒｅｅ＆Ｔｈｒｔ， ＢｉＴｈｒＴｒｅｅ＆ ｛，，构建中序线索链表 ！ ｒｔ＝（ＢｉＴｈｒＴｒｅｅ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（Ｂｉ删－ ｏｄｅ）））） ｐｒｉｎｆｆ（”ＯＶＥＲｎＪ０Ｗ”）； Ｔｈｒｔ－＞ＬＴａｇ＝Ｌｉｎｋ； Ｔｈｒｔ－＞ＲＴａｇ＝Ｔｈｒｅａｄ； Ｔｈｒｔ一＞ｒｃｈｉｌｄ＝Ｔｈｒｔ； ／／添加头结点 ｉｆ（１ １ｆ）Ｔｈｒｔ－＞ｌｅｈｉｌｄ＝Ｔｈｒｔ； ｅｌｓｅ｛ Ｔ｝ｌｎ一＞ｌｃｈｉｌｄ＝Ｔ：ｐｒｅ＝Ｔｈｒｔ； ＩｎＴｈｒｅａｄｉｎｇ（￣； ｐｒｅ一＞ｒｃｈｉｌｄ＝Ｔｈｒｔ；／／处理最后一个结点 ｐｒｅ－＞ＲＴａｇ＝Ｔｈｒｅａｄ； Ｔｈｒｔ－＞ｒｃｈｉｌｄ＝ｐｒｅ；｝ｌ／／ＩｎＯｒｄｅｒＴｈｒｅａｄｉｎｇ 算法５ （３）自信度（ｃｏｎｆｉｄｅｎｔ）：激发学生的学习兴趣， 增强学生的自信心，变被动学习为主动学习。有 些学生在初期学习时，没有入门，掌握不好，随 着内容的深入，增加了难度，久而久之，容易破 罐子破摔。对此，首先鼓励这部分学生克服困难， 迎头赶上。从讲课内容上在讲解新课的同时，不 断穿插已学章节的复习和总结。并尽量增加课堂 教学的生动性，通过提问、答疑、交流学习经验 等来带动大家，营造一个良好的学习氛围。以此 来培养学生自我挑战和战胜困难的能力。课堂教 维普资讯 http://www.cqvip.com 山东电力高等专科学校学报 第９卷（２ｏｏ６） Ｊｏｕｒｎａｌ ｏｆ Ｓｈａｎｄｏｎｇ Ｃｏｌｌｅｇｅ ｏｆ Ｅｌｅｃｔｒｉｃ Ｐｏｗｅｒ 第２期 ９ 学中对基本算法一定讲清讲透。在算法的讲解中， （３）答疑与讨论：解答学生的疑问，并鼓励学生 讨论和贴贴子，通过头脑风暴法来理解所学知识． 激发学生的创造力。 以中序线索化（算法５、算法４）为例，分三个层次进 行讲解，第一层针对一棵二叉树实例，和学生一块 分析完成线索化需要完成哪几方面的工作——建 头结点、如果树非空，头结点的左指针指向树，ｐｒｅ 指向头结点，开始中序遍历进行中序线索化．最后 一（４）在线作业：教师提供一批题目及相关答案． 便于学生自学和复习。 （５）在线考试：建立题库，自我测试和评判来了 解自己学习地掌握情况。 （６）相关学习资料和链接：充分利用网上资源． 个结点线索化，在这种启发性引导下理出大致思 路。第二层次将算法逐步细化，手工一步步分析算 法的执行过程。第三层次将算法改为完整的Ｔｕｒｂｏ Ｃ 程序或ｃ＋＋程序，从整体上让学生理解算法的意义 并通过运行程序，结果显示来加深学生对算法的理 解。通过这种层层讲解的方式逐步加深学生的理 解。提高学生学习的自信心。 （４）满意度（ｓａｔｉｓｆａｃｔｉｏｎ）：提供给学生真实的问题 解决情景，应用已学的知识解决问题．自信来源于 有意义的成功，成功来自于战胜困难的心理感受。 上机中根据学生的学习情况为不同的学生提供不 同难度的学习任务。对于水平较低的学生，教师具 体化的指导是很有必要的，提供部分Ｃ语言程序范 例，让这部分学生先模仿，再自己尝试去实现一些 算法。对水平较高的学生提出更高的要求，并试着 让他们去解决一些实际问题，比如约瑟夫环，电梯模 拟等。在解决过程中并不拘泥于书上的一些算法， 多鼓励学生自己去想办法．以锻炼学生的创新能 力。 总之，教和学都是一个循序渐进的过程，是个 动态交流的过程．在这个过程中师生之间相互配 合、相互学习。学生根据教师的讲解和要求去学习 和掌握学习内容．教师根据学生的反馈不断改进教 学方法和提高教学质量，只有这样，才能学好课程。 ４结束语 前面所探讨的传统意义上的课堂教学并不是 学习《数据结构》的唯一途径，随着网络的普及，可 以充分利用网络的优势．给学生提供网络学习的机 会。在工作中，我们基本实现以下功能： （１）在线学习，内容包括教学课件、算法和完整 的Ｃ语言程序，并且提供学习的导航图。 （２）知识查询：课程中所涵盖的有关知识点。 拓展学生的学习空间。 （７）留言箱：提供师生交流的渠道。 参考文献 【ｌ】严蔚敏，吴伟民．数据结构（Ｃ语言版）【Ｍ】． 北京：清华大学出版社，１９９７ 【２】殷人昆，陶永雷，谢若阳，盛绚华．数据结构 （用面向对象方法与Ｃ＋＋描述）【Ｍ】北京：清华大学 出版社．１９９９ 【３】杨开成，李秀兰，樊．基于ＡＲＣＳ模型构 建《数据结构》在线学习系统【Ｊ］．中国电化教育， ２００ｌ（１）：５１—５４． ［４】赵丽．“数据结构”教法浅析【Ｊ】．晋示范高等 专科学校校报，２００ｌ（３）：２７—２８． 【５】郭蔚．在“数据结构”教学中应用多媒体的 几点尝试【Ｊ］．河北工业大学成人教育学院学报，２００２ （１２） ［６】郭翠英．试论数据结构课程的教学方法【Ｊ］． 山西广播大学学报，２０００（９）：２４—２５ ［７］陈高云．《数据结构》多媒体课件的研究【Ｊ］． 安徽农业大学学报，２０００，２７（３）：３０５～３０８ Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐａｐｅｒ ｇｅｎｅｒａｌｉｚｅｓ ａｎｄ ａｎａｌｙｓｅｓ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｏｆ（ｄａｔａ ｓｔｒｕｃｔｕｒｅ）．Ｒｅｌｅｖａｎｔ ｉｍｐｒｏｖｉｎｇ ｍｅｔｈｏｄ ｉｓ ｖｅｎ ａｃｃｏｒｄｉｎｇ ｔｏ ｉｎｃｅｎｔｉｖｅ ｍｏｄｅｌ ｏｆ Ａｍｅｒｉｃａｎ ｓｃｈｏｌａｒ Ｋｅｌｌｅｒ ｎａｄ ｐｒａｃｔｉｃｉｎｇ ｅｘｐｅｒｉｅｎｃｅ．Ａｔ ｌａｓｔ， ｐｒｏｐｏｓｉｎｇ ａｎ ｉｄｅａ ｏｆ ａｓｓｉｓｔｎａｃｅ ｌｅａｒｎｉｎｇ ｔｈｒｏｕｇｈ Ｉｎｔｅｍｅｔ． Ｋｅｙ ｗｏｒｄｓ：ｄａｔａ ｓｔｒｕｃｔｕｒｅ ａｌｇｏｒｉｈｔｍｓ ｔｅａｃｈｉｎｇ ｍｅｔｈｏｄ ｂｉｎｔｒｅｅ ｌｅａｒｎｉｎｇ ｉｎ ｉｎｔｅｍｅｔ
