吐尔地·托合提

（新疆大学信息科学与工程学院，乌鲁木齐830046）

0 引言

查找和排序是日常生活及计算机软件设计中极为常用的，而且是最基本的两种运算。因此，查找和排序所使用存储结构及相应算法设计是数据结构与算法课程中重点讲解内容[1]。在数据结构中，查找表是一种逻辑结构，是由同一类型的数据元素构成的集合，其实现方法有顺序表和树表（二叉链表）两种存储表示。对于排序，也是在类似于查找表的集合中，按照关键码大小进行比较和移动，重新安排每一个数据元素（记录）在序列中的相应位置。

在教学中，我们系统讲解如何构造查找表，或如何在内存中存储待排序序列，不同存储表示（顺序的和链式的）相应的查找和排序算法思路，并分析各种算法的性能和优缺点，从而从知识层面上基本达到掌握各种查找与排序算法，对算法性能进行分析的基本能力的课程目标[2]。但是，在教学中发现，因为用有限的课时去讲授较多的排序和查找算法，出现“内容多，消化不良”现象[3]，从而从技能层面很难达到从知识中体会和掌握算法设计的思维方式及技巧，提高分析问题和解决问题能力的课程目标[4]。

本文以基于二叉树的查找和排序为例，形成课堂案例教学，通过讲解在二叉排序树的构造、查找和排序算法上的一些启发思路的知识点，一方面加深了学生对于二叉树的性质、存储结构、遍历，以及二叉树应用的理解和掌握，另一方面引导学生要认识到解决问题有多种方案可选，使分析问题和解决问题的能力得到了提升。……