树和二叉树教案1.docx

树和二叉树教案1

第一篇：树和二叉树教案1教学过程一、导入树是一类重要的非线性数据结构，是以分支关系定义的层次结构。在日常生活同学们经常见到树。树有一个树根。有许多树枝，在树枝上长有很多树叶。就象我们今天要讲的树，是一种层次结构。二、新授(一)树1．树的定义树（tree）是由n(n≥0)个结点组成的有限集合。它是树型结构的简称，是一种重要的非线性数据结构，应用广泛。如：磁盘上的文件目录结构、家族成员关系、单位的组织机构、书的内容组织、算术表达式等。任何一棵非空树是一个二元组：Tree=（root，F）其中：root被称为根结点，F被称为子树森林2．基本术语森林：是m（m≥0）棵互不相交的树的集合有向树：有确定的根，树根和子树根之间为有向关系（自上到下，自左到右）有序树：树中结点的各子树从左到右是有次序的，不能互换无序树：树中结点的各子树从左到右是没有次序的子女：结点的子树的根是该结点的孩子双亲：孩子结点的根结点兄弟：具有同一双亲的结点堂兄弟：双亲在同一层的结点祖先：从根到该结点所经历分支上的所有结点子孙：以某结点为根的子树中的任一结点学生活动：请同学门总结树形与线形的异同(二)二叉树1.二叉树的定义二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。2．二叉树的五种基本形态二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。3．二叉树不是树的特例（1）二叉树与无序树不同二叉树中，每个结点最多只能有两棵子树，并且有左右之分。二叉树并非是树的特殊情形，它们是两种不同的数据结构。（2）二叉树与度数为2的有序树不同在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。4、满二叉树和完全二叉树是二叉树的两种特殊情形。a、满二叉树一棵深度为k且有2k-1个结点的二又树称为满二叉树。满二叉树的特点：（1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。（2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。b、完全二叉树(CompleteBinaryTree)若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。特点：（1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。（2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。（3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。5、二叉树的性质性质1二叉树第i层上的结点数目最多为2i-1(i≥1)。性质2深度为k的二叉树至多有2k-1个结点(k≥1)。性质3在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。性质4具有n个结点的完全二叉树的深度为小结：这节课介绍了树的一些基本术语，二叉树的概念和二叉树的基本性质，希望同学们牢记二叉树的基本性质。作业：习题五1,2第二篇：第四章树和二叉树说课教案第五章树和二叉树说课教案姓名：仇环单位：信息工程系年级与科目：08级计算机应用《数据结构》课题：树和二叉树职称：讲师教龄：1年（各位老师下午好，我说课的题目是树和二叉树）说课的内容包括：一．教学大纲分析二．教材分析三、学情分析四．教学目标五、教学重点与难点六、教学方法七、教学过程八、教学效果预测及教学后记一、教学大纲分析：高职高专教育的人才培养特征是高级技术应用型人才，具体到计算机专业来说，就是培养从事计算机产品生产、维修和编程和实际应用的技术人才。在计算机专业的课程体系中，《数据结构》不仅是一门重要的专业基础课程，而且是计算机程序设计重要的理论基础，更是计算机等级、专升本等考试的必考课程之一。它在整个学科体系中具有重要作用，有着不可替代的地位。本课程的教学不仅重视学生对理论知识的理解和掌握，锻炼学生抽象思维能力和想象能力，更注重实践动手的能力，要求学生能够设计出结构清晰、可读性好、运行效率高的算法，并能够用一种或多种计算机高级程序设计语言实现。学好这门课程，对培养学生程序设计的能力、设计算法的能力和运用计算机进行数据处理的能力有着深远的意义。其前导课程为：《C语言程序设计》或《C++语言》。二、教材分析本教材属于“21世纪高职高专规划教材”，这套教材主要面向高职高专院校学生。教材内容力求体现以应用为主体，强调理论知识的理解和运用，实现专科教学以实践体系及技术应用能力培养为主的目标。1、教材特点：本教材的特点可总结为：（1）基础理论知识的阐述由浅入