数据结构-树与森林课件

数据结构——树与森林..幽默来自智慧，恶语来自无能数据结构——树与森林..数据结构——树与森林..幽默来自智慧，恶语来自无能第六章树与森林学习要点树的递归定义和森林的基本概念。树与森林的存储结构树与森林的遍历算法树、森林与二叉树的相互转换信息化教学是当前教学改革的一个重要方向，在军校教学中已经得到了广泛应用。信息化教学不仅是在教学手段上大量运用信息技术，更是在教学思想、教学模式上有别于传统教学的一种教学方式，其本质是在信息技术的支持下对教学内容、教学方法、教学过程和教学评价等进行设计，从而创设信息化的教学过程，促进学习者的学习。信息化教学强调在充分利用信息技术的基础上，促进学习者积极主动地进行独立学习、终身学习和具有个性化的学习，应真正做到“因材施教、因人而异”，体现出以学生为中心、尊重学生个体差异的特点，力图使学生在创新、问题求解和决策、批判性思维、信息素养、获取隐性知识、自我管理和可持续发展等方面的能力获得有效的发展。[1]目前，多媒体教学已经在包括军校在内的各高等院校普及，但如何进一步将信息技术融入教学、如何认识和开展信息化教学对于大多数院校仍然处于实验和探索阶段。本文结合军校教学实际，针对当前信息化教学中取得的经验和发现的问题，探讨了如何寻找信息化教学改革的创新点和突破口，使信息化教学成为创新思维和探索精神培养的有力手段。一、军校信息化教学的优势及存在的问题军校教学有着鲜明的军事特色，例如紧密结合装备进行教学、师生之间存在着明显的等级差别、学员各项行动需要整齐划一等，这就造成了军校信息化教学与地方院校信息化教学既有共同性又有特殊性的特点。1.军校信息化教学的优势将信息技术贯穿整个教学过程、融入各个教学环节，能够大大提高教学效果。目前，军校信息化教学的优势可以概括为以下几个方面：（1）有利于复杂装备信息的表达。课堂上的信息来源丰富多彩，信息源不再局限于教员和课本。多种媒体的应用不仅能够扩大信息的容量，而且还可以充分调动学员的感官，有利于信息的接受。特别是对于复杂装备的教学，无论是结构、原理和信号流程等，不借助于图像、视频等很难完整展现出来。（2）有利于提高学员的主动性、积极性。先进信息手段的加入，尤其是多媒体和网络的加入，使教员的作用不再仅仅是灌输和讲授，而是更多地指导学员的学习探索活动，让学员能够更好地自主学习。现代武器装备大量应用了高新技术，特别是计算机和信息技术，如何理解装备设计思想、理解各种技术的应用等都需要学员在教员指导下进行反复地探索和思考，离开了学员的自主学习势必大大影响教学效果。（3）有利于因材施教，进行个性化教学。计算机的交互性，使学员能够实现个性化学习，自主选择学习的难易程度，自己调整学习进度，并且随时可以同教员进行互动，及时解决学习中遇到的问题。例如基于网络的虚拟操作训练系统的使用，能够让学员充分根据自己的实际情况把握学习的节奏，避免了实际装备少、操作时间短、学员掌握程度参差不齐等问题。（4）有利于学员互动。学员之间也可以通过互动、相互竞争或者分角色扮演等形式共同学习，能够培养他们的合作意识、竞争意识，深化对所学知识的认识和理解。例如，在编程教学中，通过分组学习，互相交流和探讨，实现了充分的互动，能够快速达成教学目标。（5）有利于培养学员信息处理能力。通过多媒体超文本特性与网络特性的结合，可以培养学员对信息的获取、处理、和表达等能力，有利于学员主动发现、主动探索，培养他们的创新精神。通过设定主题，使学员通过校园网等检索相关文献，进而加深自己的理解，甚至提出自己的观点，实现了教学的拓展。2.军校信息化教学存在的问题近年来，军械工程学院进行了两次信息化教学研讨，倡导全院教员积极开展信息化教学活动。通过专家听查课、教学研讨等活动，发现在信息化教学方面主要存在以下问题：（1）对信息化教学本身的认识不足。多媒体教学是信息化教学的初级阶段，也是课堂教学的典型形式。在多媒体教学中，需要将文字、声音、图像、视频等多种资源进行整合，需要根据实际情况进行精心设计。[2]而有些教员对此认识不足，认为多媒体教学就是把板书转化为课件，用投影仪作为黑板。结果，教学课件只是对知识的简单罗列和组合，缺乏启发性和发散性，往往不能够引起学员的深入思考和理解。更有甚者，将抽象的原理和复杂的公式等简单通过PPT讲解，人为加快了教学节奏，缩短了学员理解的时间，反而降低了教学效果。另一方面，有的教员过分强调课件的炫目效果，将信息化教学作为信息技术水平的表现手段，华而不实，很难收到良好的教学效果。（2）过度依赖信息化教学设备。信息化教学具有集成性、交互性、多样性、非线性、实时性和动态性等突出优势，但恰恰是这些优势造成了部分教员对信息化教学设备的过度依赖，摒弃了一些传统的较好的教学模式。传统的教学模式，比如板书，不论在教学的哪一个阶段，都具有不可替代的作用。例如在定理推导教学中，板书往往比课件更能抓住学员的思维，引导学员紧跟教员的思路。因而，要重视信息化教学手段与传统教学手段的有机融合，要发挥教学在教学过程中的创新作用，而不能变成课件的播放员、机械的演员。（3）教员与学员之间的角色还需要正确认识。传统式教学中，一切以既定知识为中心进行讲授，学员按照教员的安排进行学习活动，教员和学生分别处于主导和被动的地位。[3]军校学员因其服从意识与等级观念，在课堂上往往习惯于教员占据权威地位和主导地位，这样容易使信息化教学缺乏互动，信息化教学模式陷入僵化。因此，必须正确认识教员与学员之间的角色，课上与课下要分开，在不同教学内容中的角色也要及时调整，由角色转变带动信息化教学的改革，使信息化教学充满生机和活力。（4）信息化基础建设需要继续加强。由于军校学员自主时间很少且网络使用受限，使得学员自己进行信息搜集和相关工作的限制较大，因而实施信息化教学的重心转移到了教员身上。要想使学员实现与教员的良好互动，还需要拓宽有监督的信息获取途径，使学员能够掌控更多的学习资源。为此，加快图书馆资源的更新和校园网的完善是提高信息化教学水平的重要物质基础。（5）信息化教学的教学方法和评估方法比较单一。任何教学的改革归根结底都是教学方法和评估方法的改革。目前军校教学评估方法的改革要远远滞后于教学方法的改革，尤其是在本科生教学中，一些类似计算机软件之类的编程课程还是采用笔试的方式考核，信号分析类的课程缺乏实验环节，这些导致了很多学员高分低能，不能“学以致用”。因此，教学评估方法的改革同样需要重视，要与逐渐改进的教学方法改革相适应。二、军校信息化教学的改革的几点建议1.夯实基础，为军校信息化教学创造条件随着信息技术的快速发展与应用，装备仿真模型、虚拟训练系统、虚拟维修教学、课程试题库、网络教学系统等各种教学软件陆续投入使用，给学员的学习提供了有利的条件，也给教员的能力和素质提出了更高的要求。因此对于每一个教员，熟练使用计算机及其网络系统技术，掌握基本知识、基本操作程序和技能，及时进行信息更新，能够搜集、设计、利用广泛的信息资源等等，都是信息化教学对教员的要求。[4]此外，对于信息化教学的硬件设施和各种资源，都应该进行实时监测，及时进行维护，为教学提供有力保障。2.彻底转变课堂上教员与学员之间的角色长期以来所形成的灌输式的教学模式已不再适应形势的需要。[5，6]教员要转变自己的角色，要从知识为主体转变到学员为主体，要从单纯的“教”转变到“教与学”的互动，把自己变成学员的伙伴，充分调动学员自主学习的能动性。要当好学员的领路者，不仅指明他们应该学什么，还要教会他们如何去学，正如古人说的“授人以鱼不如授人以渔”，要争取做到“鱼”与“渔”兼得。要做好学员的解答者，要求教员在掌握每个人基本情况的基础上对学员的各种问题做好解答，帮助他们尽快进入这个领域。要做好学员的倾听者，教员要鼓励学员发表自己对于某个问题的观点，倡导展开讨论交流，给学员一个展现自己的舞台。3.拓宽信息化教学的渠道多媒体教学作为信息化教学的基本形式，已经取得了良好的效果。但是应该注意到，仅仅有多媒体教学还不够，应积极探索各种信息技术在教学中的应用。对军校教育来说，多媒体教学大多用在课堂上，脱离了课堂就难以实施。随着校园网的不断完善，目前已经覆盖了大多数教学区和宿舍区。因此，教员可以通过网络平台建立教员与学员的互动机制，大大提高学习的灵活性和时效性；依托校园网还可以实现教学评价机制的改革。另外，目前正在开发的网上装备操作训练系统等，也将给学员提供随时随地学习的条件。此外，利用校园网和军网上的数字图书馆等，可以获取大量新课程标准指出，倡导自主、合作、探究的学习方式，也就是倡导“发现性学习”，转变学生的学习方式就是改变原有的过分强调单一的“接受性学习方式”，按照新课程标准，将课程内容、教材知识以问题的形式呈现出来，把发现、探讨、研究等认识过程突显出来，让学生在自主发现问题、探究问题、获得结论的过程中形成独特的学习方式。一、从观念上正确引导学生对待问题意识，让学生成为问问题的主体美国教育家布鲁巴克曾说过：“最精湛的教学艺术，遵循的最高原则就是让学生自己提问题。”传统课程的“满堂灌”与新课程标准提倡的“自主、合作、探究”的学习方式严重背离，由于参与性不够，学生常常充当听者的角色，在课堂上自主发言的机会不多。加上学生自身年龄因素的影响，知识水平有限，在课堂上，学生是配角，课堂提出的问题多数是教师精心设计的，学生的思维基本是围绕着教师提出的问题一步步展开。这样的课堂组织性较强，容易展开教学活动，但往往也容易限制学生的思维，影响学生积极性、主动性的发挥，长久下去，学生的依赖性会加强，易造成“等”和“靠”的局面，从而扼杀他们爱问的天性，故很难做到培养学生的问题意识。教学过程体现为孩子们不断提出问题和解决问题的过程。在教学中，为增强学生的问题意识，要引导学生提问，要特意为学生们的“疑”创设空间。课堂不再是教师一味地设问，牵着学生走，而是学生饶有兴趣地提出问题，并在一个个问题的生成和解决过程中实现教学目标，学生也不再表现为没有问题或不敢提出问题。让学生学会主动地提出问题，这是他们学会学习的第一步。惟其如此，才能充分挖掘孩子们的潜力，使他们积极主动地学习。心理学研究表明，学生提问是学生个体获取知识的心理能力的外部体现。学习是从发问开始的，没有自己的问题，就永远没有创造，敢于提问、善于提问是积极思维、富有创造性的表现。由此可见，课堂上教师再精妙的提问也无法替代学生独立思考，只有真正把提问的主动权还给学生，才能在学生的学习过程中，促使其勇于探索、追求创新，所以唯有更新教育观念、重视学生的问题，才能维护学生提问的尊严，不让他产生挫折感、畏惧感，从而让他们敢问、乐问。二、从方法上进行及时的点拨和指点由于长期形成的教师主导理念，仍然是以教师提问为主、学生提问为辅，因而阻碍了学生生成问题的可能性。头脑风暴法应遵守如下原则：延迟判断原则，对各种意见、方案的评判必须放到最后阶段，此前不能对别人的意见提出批评和评价。认真对待任何一种设想，而不管其是否适当和可行；欢迎各抒己见、自由鸣放，创造一种自由的气氛，激发参加者提出各种荒诞的想法；追求数量，意见越多，产生好意见的可能性越大；探索取长补短和改进办法，除提出自己的意见外，鼓励参加者对他人已经提出的设想进行补充、改进和综合。除了在程序上的要求之外，更为关键的是探讨方式、心态上的转变，概言之，即充分、非评价性的、无偏见的自由畅谈、延迟评判、禁止批评、追求数量；从内容上可以是预习中遇到的语言文字上的困难、题目与内容的扣题方面、主题思想及作者的观点立场、作者的创新之处和值得学习的地方、写作方法上的选择出于哪些考虑等等，不一而足。三、从数量过渡到质量新课程呼唤教师教学观念和学生学习方式的变革，要求教师在教学过程中注重培养学生的独立性和自主性，引导学生质疑、调查、探究，促进学生在教师指导下主动地、富有个性化地学习，从而转变学生的学习方式，培养学生的创新精神与实践能力。学生提问问题是一个过程，不能急功近利，一开始，只要学生能问出来即可，之后再从质量从精彩程度、思维含量、挑战性上加以划分，加以评判鼓励。还可以由小组共同提出问题，再过渡到学生自己提出问题，尤其是有个性的问题。四、从评价方式上肯定学生的努力在课堂教学中，教师应精心备课，提出每一堂课的核心问题。这个问题可以牵一发而动全身，能够囊括本课的教学内容，成为课堂学习的主线；这个问题应从学生的问题总结修正出来，于是课堂上绝大多数学生可以体会到学习提问的快乐，因为他们总能从课堂问题解决中看到自己所提问题的影子。很重要的一点就是要营造民主的氛围，鼓励学生提问并进行适当的奖励。课上你创设了民主氛围，学生才能放言，民主的关键在于允许学生说错话。即使说错话，教师也应在指出错误时给予积极的鼓励和表扬，从而维护他们的面子。在教学中我充分利用新课程关注学生的学习过程的特点，制定了提问奖励制度，在学生学习过程评价上一周设定100分奖励，一节课提问五次即得满分，由于门坎低，大多数学生能完成，除了极少数在初中、小学就留下了提问心理阴影的同学（他们回答问题时没有答好，曾被老师批评，以后害怕回答问题）。对于学生提出的最佳问题，还有适当的奖励，学生会因为这不起眼的奖励而获得“荣耀”。这样的课堂常常是师生互动自然而热烈，学生也能够因提问感觉到学习的乐趣，这样就能够提高语文的教学效果，能够提高学生的语文探究能力，直至培养出充满“问题意识”的学生，进而真正落实新课标精神。第六章树与森林学习要点树的递归定义和森林的基本概念。树与森林的存储结构树与森林的遍历算法树、森林与二叉树的相互转换§6.1树及其相关概念6.1.1树的基本概念1、树的基本概念树(Tree)是一个由n(n20)个结点构成的有限集合T。①当n=0时,称T为“空树②当n≠0时,T中诸元素满足下述条件●有且仅有一个特定数据元素没有前驱,称其为T的根结点●除根结点外其余数据元素,又可分为m(0≤m<n)个互不相交的有限集合:T1,T2,…,Tm,每一个集合T;(0≤≤m)又是棵树,称为根的子树6.1.1树的基本概念1、树的基本概念2树的特性空树是树的一个特例;棵非空树,至少有一个根结点,只有根结点的树为最小树;在有多个结点的树里,除根结点外,其余结点分属若干个子树,各子树间互不相交除根结点外,树中其他结点有且只有一个前驱结点,但可以有零个或多个后继结点oO⑥⑥O④①⑩46.1.1树的基本概念、树的基本概念有序树与无序树如果树T中各子树从左至右按照一定此序排列,不得互换,则称T是有序树(ordertree),否则为无序树(inordertree)。由此可知,二叉树是一种特殊的有序树,但不是一般树的特森林n(n≌0)棵互不相交的树的集合,称为森林(forest)。6.1.1树的基本概念22、树的表示方法①树形表示法②文氏图表示法③凹入表示法⑥⑥O①①○④括弧表示法(A(B(D)(E()(J))(F))(C(G)(H)))6.12结点及其基本概念1、结点结点的度:结点拥有的子树数目,即该结点的后继结点的个数结点的深度(层次):结点位于树的层次数树的度:一棵树中各结点度的最大值树的深度:一棵树中各结点深度的最大值结点间路径:从树中一个结点到另一个结点之间的分支路径长度:一条路径上边即连接两个结点的线段的个数称为该路径的长度6.12结点及其基本概念22、结点分类(1)根结点:树T中