树结构的教学策略初探

摘　要：

关键词：

中图分类号：G4    文献标识码：A     文章编号：
    数据结构是一门计算机领域中很重要的课程，是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构是介于数学、计算机硬件、计算机软件之间的一门交叉学科，它主要研究数据的逻辑结构、物理结构以及对数据的操作。它与算法有着很密切的关系，常用来实现和优化算法。树是数据结构中非常重要的一种结构，它的元素之间存在一对多的层次关系。由于数据结构本身的抽象和枯燥性，学生在学习相关知识时往往会比较被动和机械化，学习的效率和后期的应用能力也会受到很大影响。特别是树结构，若不采用适当的教学方式，则会导致教学过程过于缓慢且教学效果也不尽人意。
    若采用常规的教学方式，先介绍树和二叉树的基本概念和性质，再介绍二叉树的基本操作，最后举例讲解二叉树的应用。整个过程分块明显，使原本为一个整体的内容，由于讲解的过程分割开来，学生在学树的基本操作环节就显得疲乏，使教学过程很难进行到最后的应用环节。在反思和探究之后，我对课堂教学方式进行了研究和尝试，引入了一些有效的教学策略，使死板的课堂活跃起来，取得了很好的教学效果。
    1. 任务驱动 激发兴趣
    任务驱动教学法(TaskBasedLearning)是建立在建构主义教学理论基础上的一种教学方法，是建构主义理论在教育教学中的一种具体应用。这种教学方法主张教师将教学内容隐含在一个或几个有代表性的任务中，以完成任务作为教学活动的中心；学生在完成任务的动机驱动下，通过对任务进行分析、讨论，明确它大体涉及哪些知识，需要解决哪些问题，并找出哪些是旧知识，哪些是新知识，在老师的指导、帮助下，通过对学习资源的主动应用，在自主探索和互动协作的学习过程中，找出完成任务的方法，最后通过任务的完成实现意义的建构。我采用任务驱动方式，将树的基本知识和操作应用融入到学生熟悉有趣的实例中。
    引例：家谱
    传说有一天，LPZ小朋友遇见一个老爷爷LK，LK喊LPZ叔叔，并且他还拿出一张很大的纸，上面以奇怪的方式记录着一些人的姓名（没有重名），LPZ从中找到了自己的姓名，   
    任务1：他想知道为什么这个老爷爷要叫他叔叔。你能帮他吗？
    ……LH(LJ(LPZ,(I,J),LF),LB(LM(LK,LU))
    在上例中，可将输入的广义表形式转化为树状形式画出更明显的层次结构，介绍树的基本概念、表示方法、存储结构和建树，学生通过比较各种表示法得出更适合的表示方法。由于学生对家谱比较熟悉，很自然能接受相关知识。任务的直观性则充分调动了学生学习主动性，为进一步学习打下良好的基础。并且该例有很好的拓展性，自然提出以下的问题从而过度到下一环节的学习。
    任务2：他想知道他们的共同祖先的这个家族共有多少辈人？
    计算树的高度。
    任务3：最多的有几个孩子？
    计算树的宽度。
    任务4：一共有多少人？
    树结点计数。
    任务5：输出这个家族的家谱。
    树的遍历。
    任务6：他还想知道他跟他有多近？
    最近公共祖先。
    任务7：家族中距离最远的两人有多远？
    求树的直径。
    2. 一题多解 拓展思维
    数据结构基本操作是有限的，但将数据结构与算法相结合的应用是无限灵活的，在教学中通过一题多解的方法让学生在思维的广度和深度得到训练和拓展是教师面临的重要课题。“一题多解”是训练、培养学生思维灵活性的一种良好手段，通过“一题多解”的训练能勾通知识之间的内在联系，提高学生应用所学的基础知识与基本技能解决实际问题的能力，逐步学会举一反三的本领。引导学生一题多解，不仅能使学生掌握新知识，还能起到复习巩固旧知识的作用，使学生对相关知识和方法有更进一步的理解，同时能活跃课堂气氛，使学生对树的学习产生浓厚的兴趣，也培养了学生的一种钻研精神，使学生在思考问题上具有灵活性、多变性，避免了学生在解题中钻死胡同的现象。
    通过教学实践，我在任务7的环节中让学生充分思考，运用了4种方法解决该问题，使学生在算法和数据结构的联系和运用上加深了理解，拓展了思维。
    问题简述：求一棵树的直径。树的直径是指树中距离最大的两个结点的距离。
    方法一：图论算法
   采用邻接矩阵存储树中的结点。首先假定每一个点作为直径的一个端点，使用Floyd算法求出任意两点间的最长距离，但是这样的复杂度是O(N^3)。空间复杂度O(n^2)。树的结构对本题无影响。依旧要对每一个点找一遍，求最大值，边上带权也是同样的做法。
    缺点是这种办法效率很低，许多步骤都要做很多次。优点是编程复杂度较低。
    [代码略]
    方法二：
    随机一个点作为根节点，把它拉成一棵树。对于树中的一个元素，如果它是直径上的一个点，无非是下面3种情况：
    1）它是直径上的一个端点。
    2）它是直径上的一个转点。
    3）它是直径上的一个中间点。
    那么对于每一结点，记录3个值，分别是由此点出发的最长路径和次长路径（保证它们只在该结点处重合），以及最长路径上的第二个结点。这里面的次长路径和最长路径都可以向它的儿子和父亲方向延伸。
    然后进行第一遍DFS，统计出每一个结点他们向儿子方向延伸的3个信息。再进行第二遍DFS，统计出每一个结点向父亲方向延伸的长度，用来更新这3个信息。
    这里注意特殊情况的处理：对于每一个结点，用它父亲的最长路来更新，如果他父亲最长路的延伸方向是它本身，则用他父亲的次长路来更新。对于每一个结点，可以保证最长路径和次长路径延伸的方向不同，直接作代数加法就可以求出直径。
    时间复杂度O(N^2)，空间复杂度O（N^2），采用数组模拟链表，在数组中记录每一条边。用三个数组维护。第一个记录当前节点第一个边的位置，第二个记后面的边编号。第三个记录边。树的结构对时间、空间复杂度没有影响。
    方法三：
    第二种方法非常麻烦，需要用到两个DFS的树形动规，很容易出错。其实完全可以不用考虑通过父亲结点来查找直径。
   代码可以简化很多，直接用一遍DFS，对于每一个结点算出两个信息，分别是它们向儿子方向拓展的最长路径和次长路径（保证是向不同的儿子方向拓展）。
   这样答案就显而易见了，直接把每一个结点的最长路径和次长路径代数求和就可以了。
    缺点是系统栈承受不了100000层。我们用人工栈模拟，可以解决系统栈溢出的问题。可以处理边上带权的图，得到的值存最大值和次大值。边做边记录最大值，做完后就输出答案，树的形态可以忽略。
    时间复杂度O（ n^2）空间复杂度O(n)。
   [代码略]
   方法四：
   任意选取一个点做BFS，最远点一定是树的直径上的端点，找出一个最远点再做BFS，这样就可以得到树的直径。
   下面是对算法正确性的证明：
   原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点
    证明:
    1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是终点，则必定存在另一个点w使得u到w的距离更长，则与BFS找到了v矛盾)
    2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半部分，所以v一定是直径的一个端点，从v进行BFS得到的一定是直径长度。
    这种方法最简单但不易想到。
    树的结构对它完全没有影响。时间复杂度O(2n);空间复杂度O(n);
    缺点是带权边难以处理。
    数据结构的教学中，重视教学方法和策略的研究，特别在备课中要根据教学内容、学生情况适当地进行教材处理和钻研，要对知识进行横向和纵向联系，这堂课才能做到丰富多彩，也必定能使教学达到事半功倍的效果，从而对学生进行有效的思维训练和提高综合能力。

参考文献：
《信息技术教学方法：继承与创新》2003年9月第1版 李艺 李冬梅