数据结构（Java语言版）-教案 李春葆 第10-16 教学周 二叉树的建立、二叉树遍历和哈夫曼树-常用的查找算法实现

成都东软学院《数据结构(Java)》课程/项目教案2-《数据结构(Java)》课程/项目教案1-《数据结构（Java）》课程/项目教案单元教案首页单元CU（4）学时12周次第10－12教学周教学环境设计与组织安排课堂，笔记本电脑，小组合作单元名称树和二叉树单元项目名称二叉树的建立、二叉树遍历和哈夫曼树教学目标及达成度理论知识理解并掌握树形结构的概念和算法专业技能对根据具体的问题进行数据结构抽象化的能力熟练运用程序设计语言实现数据结构算法的能力具有科技资料与文献的收集与检索能力具有自我学习能力及新技术开发与研究的能力职业道德理解工程师职业道德规范具备一名优秀工程师的基本素质教学重点难点二叉树的二叉链表、三叉链表表示法；二叉树的建立算法；三种二叉树的遍历算法（前序、中序、后序）；二叉树的节点删除算法；哈夫曼树教学方法手段媒介教学方法：讲授、讨论、演示、练习、实验、研究性学习、案例、合作学习、指导教学、任务分析、自主学习、读书、问题教学。教学媒介：教科书、板书、多媒体。教学组织方式1.讲评——课后作业2.互动——演示二叉树的基本操作3.讲解——树与二叉树的基本概念，二叉树的建立、遍历算法，哈夫曼树及哈夫曼编码算法4.操作――编程实现二叉树的建立、遍历算法实践环节课内实践环节：编程实现二叉树的建立、遍历算法，哈夫曼编码课外实践环节：平时成绩管理系统中，学生成绩按排序二叉树方式建立，实现基本操作算法

教学设计【教学进程安排】重点设计教学步骤与具体内容安排。一、课外学习讲评树形结构是非线性结构。其特点是数据元素只能有一个前驱，可以有零个或多个后继。二、内容导入树是一种常用的非线性结构。树的根结点没有前驱结点,除根结点之外的所有结点有且只有一个前驱结点。树中所有结点可以有零个或多个后继结点。三、主要内容设计1.树的定义【讲授】树的定义树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。树的根结点没有前驱结点,除根结点之外的所有结点有且只有一个前驱结点。树中所有结点可以有零个或多个后继结点。【案例】行政机构，公司机构2.树的基本术语【讲授】结点表示树中的元素，包括数据项及若干指向其子树的分支。结点的度结点拥有的子树的个数。叶子结点（叶子）度为0的结点。分支结点度不为0的结点。结点的层次树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的度树中所有结点度的最大值。树的深度树中所有结点层次的最大值。有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。【归纳总结】教学重是对树的概念理解，对术语的记忆。【课外学习要求】思考：怎样存储树？既要保存数据，又要包含数据之间的关系。【课后分析及改进】注释：教学设计按每次课2学时撰写。教学设计【教学进程安排】重点设计教学步骤与具体内容安排。一、课外学习讲评在建立单链表的基础上引入二叉链的概念。二、内容导入任意一颗树都可以转化成二叉树。反之二叉树叶可以转化成普通树。三、主要内容设计1．二叉树的定义【讲授】二叉树也可以用递归的形式定义。即：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。【案例】【讲授】2．满二叉树和完全二叉树【讲授】如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树。３．二叉树的性质【讲授】５个性质。均不用硬记，只要画一个二叉树图就知道了。最重要的是性质5，是根据结点编号建二叉树的依据。【案例】【讲授】４.二叉树的顺序存储结构【讲授】按完全二叉树对结点编号，结点编号与数组的下标相同，根据下标可以得倒双亲和孩子的关系。此种存储方式对于数据较简单的二叉树使用比较方便。如果数据是大结构体，则可能浪费较大空间。【案例】【讲授】【归纳总结】【课外学习要求】实现并阅读程序。【课后分析及改进】注释：教学设计按每次课2学时撰写。教学设计【教学进程安排】重点设计教学步骤与具体内容安排。一、课外学习讲评提问：二叉树为什么要用链式存储？二、内容导入二叉树是一种非常重要的树形结构,其它的树形结构文体可以变化为二叉树三、主要内容设计１．二叉树的链式存储【讲授】根据二叉树的性质5，按完全二叉树的编号，输入结点编号和结点值，就可生成二叉链表。由于后面结点的指针要赋予前面结点的左、右孩子指针域，故应设计一个指针数组，用于保存结点的指针。根据结点编号可以得出其双亲结点的编号，及其结点是双亲的左孩子还是右孩子。这样就可以根据结点编号建立二叉树。【实验】按结点编号建立二叉树结点编号整除2得双亲编号。若结点编号是偶数，则是左孩子，该结点的指针赋予双亲结点的左孩子指针域；若结点编号是奇数，则是右孩子，该结点的指针赋予双亲结点的右孩子指针域。教学重难点是建立二叉树和显示二叉树。2显示二叉树【讲授】用缩进显示出结点间的层次关系【实验】按结点编号建立二叉树，并用缩进显示二叉树【归纳总结】教学重难点是对程序的阅读和理解。【课外学习要求】实现并阅读程序。【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案。注释：教学设计按每次课2学时撰写。教学设计【教学进程安排】重点设计教学步骤与具体内容安排。一、课外学习讲评1.提问：二叉树的存储方式。2.提问：顺序存储和链式存储的编程思路。二、内容导入对二叉树的很多处理都是以遍历为基础,因此我们要熟练的掌握遍历。（顺序表和单链表也存在遍历的问题，由于比较简单，没有单独作为问题讲解。）三、主要内容设计１.先根遍历【讲授】先访问根结点,然后分别先序遍历左子树、右子树。【案例】【讲授】２．中根遍历【讲授】先中序遍历左子树，然后访问根结点，最后中序遍历右子树。【案例】【实验】３.后根遍历【讲授】先后序遍历左、右子树，然后访问根结点。【案例】【实验】建立一颗二叉树，用三种方法遍历，显示遍历的结果。【归纳总结】教学重难点是对遍历方式的递归过程的理解。【课外学习要求】完成并实现程序的运行。深入理解遍历的递归过程。【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案。注释：教学设计按每次课2学时撰写。教学设计【教学进程安排】重点设计教学步骤与具体内容安排。一、课外学习讲评深入理解二叉链。二、内容导入叶子结点没有孩子，其指针域为空。为了利用空的指针域，引入线索二叉树的概念。三、主要内容设计1．线索二叉树【讲授】。叶子结点没有孩子，其指针域为空。为了利用空的指针域，可以令左孩子指针指向该结点的直接前驱，令右孩子指针指向该结点的直接后继。某结点的左指针可以指向左孩子，也可以指向直接前驱；同样，右指针也可以指向右孩子，也可以直线直接后继。因此又增加两个标志，左标志为0，左指针指向左孩子；左标志为1，左指针指向直接前驱。右标志为0，右指针指向右孩子；右标志为1，右标志指向直接后继。所谓直接前驱和直接后继，是由按什么方式遍历有关。【案例】中序遍历的线索二叉树程序。2.森林转化成二叉树【讲授】1将各棵树分别转换成二叉树2将每棵树的根结点用线相连3以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构3.二叉树转换成森林【讲授】1加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来2抹线：抹掉原二叉树中双亲与右孩子之间的连线3调整：将结点按层次排列，形成树结构【实验】练习森林转化成二叉树，二叉树转换成森林的步骤。【归纳总结】线索二叉树的程序。【课外学习要求】运行并阅读理解线索二叉树的程序。【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案。注释：教学设计按每次课2学时撰写。教学设计【教学进程安排】重点设计教学步骤与具体内容安排。一、课外学习讲评二、内容导入在通讯中，电文是以二进制的0、1序列传送的。在发送端，将电文中的字符转换成二进制的0、1序列，在接受端，则需要将收到的0、1序列还原成对应的字符序列。设给出一段报文：CASTSATA；希望的是传送电文时长度尽可能的短，试写出对应的二进制0、1序列。三、主要内容设计1．哈夫曼树的概念【讲授】把若干个带权的叶子结点生成一颗二叉树，要求结点的权乘以边条数之和为最小。【案例】在通讯中的应用。2.哈夫曼树的生成【讲授】原则：权小的结点离根结点远，权大的结点离根结点近。方法：先选两个权小的生成一颗二叉树，并形成一个有编号的新的根结点该结点的权为左、右子树权之和。逐级进行，每次都是选两个权小的结点（包括新生成的根结点）生成二叉树，（注意，选择时，是从编号小的结点开始，若新结点的权和老结点的权相同，则选出的是老结点）。直到选完全部结点。哈夫曼树应用举例—哈夫曼编码。【讲授】把字母出现的频率作为字母的权。权小的结点离根结点远，权大的结点离根结点近。这样生成的二叉树就是哈夫曼树。把左子树的边当作0，右子树的边当作1，由根结点到叶子结点的边就组成哈夫曼编码。哈夫曼编码可以使文本的编码最短。【练习】设给出一段报文：CASTCASTSATATATASA希望的是传送电文时长度尽可能的短（1）画出构造的哈夫曼树（2）计算带权路径长度（3）求各字符的哈夫曼编码【归纳总结】何为哈夫曼树？哈夫曼编码？其作用是什么？【课外学习要求】1.给定一组数列（10,18,16,25,6,

9,16）分别代表字符A,B,C,D,E,F,G出现的频度，试画出哈夫曼树，给出各字符的编码。2.阅读理解哈夫曼编码的程序。【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案。注释：教学设计按每次课2学时撰写。单元教案首页单元CU（5）学时2周次第13教学周教学环境设计与组织安排课堂，笔记本电脑，小组合作单元名称图单元项目名称图的建立及遍历教学目标及达成度理论知识理解并掌握图形结构的建立及遍历专业技能对根据具体的问题进行数据结构抽象化的能力熟练运用程序设计语言实现数据结构算法的能力具有较强的口头表述能力职业道德能够正确认识人生价值的自我实现和对他人所负的责任具有正直并勇于负责的职业道德和敬业精神教学重点难点图形的表示法（邻接数组表示法、邻接列表表示法）；图形的遍历算法（深度优先法、广度优先法）教学方法手段媒介教学方法：讲授、讨论、演示、练习、实验、研究性学习、案例、合作学习、指导教学、任务分析、自主学习、读书、问题教学。教学媒介：教科书、板书、多媒体。教学组织方式1.讲评——课后作业2.互动——分组理解图这种数据结构，了解图的应用，全班汇报3.讲解——图的基本概念，图的存储及遍历算法实践环节课内实践环节：编程实现图的遍历算法教学设计【教学进程安排】重点设计教学步骤与具体内容安排。一、课外学习讲评二、内容导入现实生活中还有一种结点间是多对多的关系。如城市交通、管线等。三、主要内容设计1．图的基本概念【讲授】1各结点之间的关系是多对多的系。2图的相关术语：完全图、稠密图、稀疏图、邻接点、度、入度、出度、子图、权、网、路径、回路、路径长度、无向图的连通图、连通分量、有向图的强连通图、强连通分量。【案例】【讲授】2.图的两种存储结构【讲授】1邻接矩阵表示：顶点表，邻接矩阵。2邻接表表示：顶点表，边表。3.无向图和有向图的区别。3.网的两种存储结构【讲授】1邻接矩阵表示：顶点表，邻接矩阵。2邻接表表示：顶点表，边表。3.无向网和有向网的区别。４.网和图在存储上的区别。【实验】无向图和有向图、无向网和有向网的程序。【归纳总结】术语较多，容易混淆。重在对比分析。【课外学习要求】学习巩固术语，理解图的存储结构。【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案。注释：教学设计按每次课2学时撰写。单元教案首页单元CU（7）学时8周次第14－15教学周教学环境设计与组织安排课堂，笔记本电脑，小组合作单元名称排序单元项目名称常用的排序算法实现教学目标及达成度理论知识理解并掌握常用排序算法的思想和实现方法专业技能具有较强的技术文档写作能力具有科技资料与文献的收集与检索能力具有自我学习能力及新技术开发与研究的能力职业道德理解工程师职业道德规范具备一名优秀工程师的基本素质教学重点难点交换式排序法（冒泡排序法和快速排序法）；选择式排序法（选择排序法）；插入式排序法（插入排序法和二叉排序法）。教学方法手段媒介教学方法：讲授、讨论、演示、练习、实验、研究性学习、案例、合作学习、指导教学、任务分析、自主学习、读书、问题教学。教学媒介：教科书、板书、多媒体。教学组织方式1.讲评——课后作业2.互动——分组学习多种排序算法3.讲解——学生将排序算法做为动画或PPT，做全班讲解4.操作――编程实现排序算法实践环节课内实践环节：编程实现排序算法课外实践环节：平时成绩管理系统中，对学生平时成绩、考勤成绩、作业成绩用不同的排序算法排序。教学设计【教学进程安排】重点设计教学步骤与具体内容安排。一、课外学习讲评二、内容导入三、主要内容设计1．排序的定义【讲授】将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列【案例】2排序的分类【讲授】按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序交换排序：冒泡排序选择排序：简单选择排序归并排序：2-路归并排序2.冒泡排序【讲授】1两辆比较,后面的小,则交换位置。N个数比较N-1遍（外重循环）第1遍比较N-1次，…第N-1遍比较1次（内重循环）2改进的冒泡排序若某遍比较没有发生交换，则排序结束。【实验】冒泡排序程序。【归纳总结】教学重难点是对顺序栈及其操作的理解。【课外学习要求】完成四级项目第三阶段：学生信息按顺序栈存储实现。【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案。注释：教学设计按每次课2学时撰写。教学设计【教学进程安排】重点设计教学步骤与具体内容安排。一、课外学习讲评二、内容导入三、主要内容设计1．选择排序【讲授】永远用第一个与后面的比较,后面的小,则交换位置。【实验】选择排序程序2.插入排序【讲授】把数组看成两个序列，一个是已排好的序列，在数组的前面，另一个是未排序的序列，在数组的后面刚开始时，认为a[0]已排好的序列，a[1]及其以后是未排序的序列把未排序序列的第一当作待插数，其排序过程如下：一）待插数与已排序序列的最后一个比较，1）待插数大于已排序的的最后一个，待插数原位不动，作为已排序序列的最后一个2）待插数小于已排序的的最后一个，则待插数应插入在已排序序列前面某个位置这是一个边比较边移位的过程。二边比较边移位的过程如下：从已排序序列的最后一个开始，逐个与待插数比较若待插数小，则一排序序列数据向后移位自到待插数大为止，该位置就是插入位置【实验】插入排序程序。【归纳总结】教学重难点是对顺序栈及其操作的理解。【课外学习要求】完成四级项目第三阶段：学生信息按顺序栈存储实现。【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案。注释：教学设计按每次课2学时撰写。教学设计【教学进程安排】重点设计教学步骤与具体内容安排。一、课外学习讲评二、内容导入三、主要内容设计1．归并排序【讲授】归并——将两个或两个以上的有序表组合成一个新的有序表，叫~2-路归并排序排序过程设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1两两合并，得到ën/2û个长度为2或1的有序子序列再两两合并，……如此重复，直至得到一个长度为n的有序序列为止【实验】归并排序程序【归纳总结】教学重难点是对顺序栈及其操作的理解。【课外学习要求】完成四级项目第三阶段：学生信息按顺序栈存储实现。【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案。注释：教学设计按每次课2学时撰写。教学设计【教学进程安排】重点设计教学步骤与具体内容安排。一、课外学习讲评讲评习题。二、内容导入三、主要内容设计1.【讨论】学生分组演示三级项目（1）演示+讲解（2）评委组提问：小组回答问题（3）评委打分2.【讲授】教师讲评（1）公布名次（2）讲评三级项目的完成情况（3）总结学生完成的三级项目的优缺点（4）布置假期改进方案【归纳总结】对所有作品进行讲评。【课外学习要求】完成教材习题及复习，准备好期末考试【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案。注释：教学设计按每次课2学时撰写。单元教案首页单元CU（6）学时4周次第16教学周教学环境设计与组织安排课堂，笔记本电脑，小组合作单元名称查找单元项目名称常用的查找算法实现教学目标及达成度理论知识理解并掌握常用查找算法的思想和实现方法专业技能具有较强的技术文档写作能力具有科技资料与文献的收集与检索能力具有自我学习能力及新技术开发与研究的能力职业道德具有正直并勇于负责的职业道德和敬业精神具备一名优秀工程师的基本素质教