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

《数据结构Java》课程/项目教案单元教案首页单元CU

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

1.讲评一一课后作业

2.互动一一演示二叉树的基本操作教学组

3.讲解一一树与二叉树的基本概念，二叉树的建立、遍历算法，哈夫曼树及哈夫曼编码织方式算法4,操作一一编程实现二叉树的建立、遍历算法【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案单元教案首页单元CU5学时2周次第13教学周教学环境设计与组课堂，笔记本电脑，小组合作织安排单元名单元项目图图的建立及遍历称名称理论知识理解并掌握图形结构的建立及遍历学标达度对根据具体的问题进行数据结构抽象化的能力熟练运用程序设计语言实现数专业技能教据结构算法的能力具有较强的口头表述能力目及成能够正确认识人生价值的自我实现和对他人所负的责任职业道德具有正直并勇于负责的职业道德和敬业精神图形的表示法（邻接数组表示法、邻接列表表示法）；教学重图形的遍历算法（深度优先法、广度优先法）点难点学法教学方法讲授、讨论、演示、练习、实验、研究性学习、案例、合作学习、指导教学、任段手介务分析、自主学习、读书、问题教学媒教教学媒介教科书、板书、多媒体方

1.讲评一一课后作业学织

2.互动一一分组理解图这种数据结构，了解图的应用，全班汇报式教

3.讲解一一图的基本概念，图的存储及遍历算法组方注释教学设计按每次课2学时撰写.课内实践环节编程实现图的遍历算法实践环节【教学进程安排】重点设计教学步骤与具体内容安排

一、课外学习讲评

二、内容导入..现实生活中还有一种结点间是多对多的关系如城市交通、管线等

三、主要内容设计

1.图的基本概念【讲授】1各结点之间的关系是多对多的系2图的相关术语完全图、稠密图、稀疏图、邻接点、度、入度、出度、子图、权、网、路径、回路、路径长度、无向图的连通图、连通分量、有向图的强连通图、强连通分量【案例】【讲授】

2.图的两种存储结构3讲授】1邻接矩阵表示顶点表，邻接矩阵2邻接表表示顶点表，边表

3.无向图和有向图的区别

3.网的两种存储结构【讲授】1邻接矩阵表示顶点表，邻接矩阵1邻接表表示顶点表，边表3,无向网和有向网的区别

4.网和图在存储上的区别【实验】无向图和有向图、无向网和有向网的程序【归纳总结】术语较多，容易混淆重在对比分析【课外学习要求】学习巩固术语，理解图的存储结构【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案单元教案首页单元CU7学时8周次第14-15教学周教学环境设计与组课堂，笔记本电脑，小组合作织安排单元名单元项目排序常用的排序算法实现称名称理论知识理解并掌握常用排序算法的思想和实现方法学标具有较强的技术文档写作能力达度具有科技资料与文献的收集与检索能力专业技能教目具有自我学习能力及新技术开发与研究的能力及成理解工程师职业道德规范职业道德具备一名优秀工程师的基本素质交换式排序法（冒泡排序法和快速排序法）；教学重选择式排序法（选择排序法）；点难点插入式排序法（插入排序法和二叉排序法）学法教学方法讲授、讨论、演示、练习、实验、研究性学习、案例、合作学习、指导教学、任段手介务分析、自主学习、读书、问题教学媒教教学媒介教科书、板书、多媒体方

1.讲评一一课后作业学织

2.互动一一分组学习多种排序算法式教

3.讲解一一学生将排序算法做为动画或PPT,做全班讲解组方

4.操作一一编程实现排序算法课内实践环节编程实现排序算法实践环节课外实践环节平时成绩管理系统中，对学生平时成绩、考勤成绩、作业成绩用不同的排序算法排序【教学进程安排】重点设计教学步骤与具体内容安排

一、课外学习讲评

二、内容导入

三、主要内容设计

5.排序的定义【讲授】将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列【案例】2排序的分类【讲授】按待排序记录所在位置内部排序待排序记录存放在内存外部排序排序过程中需对外存进行访问的排序按排序依据原则插入排序直接插入排序交换排序冒泡排序选择排序简单选择排序归并排序2-路归并排序

6.冒泡排序【讲授】1两辆比较，后面的小,则交换位置N个数比较NT遍（外重循环）第1遍比较NT次，…第NT遍比较1次（内重循环）2改进的冒泡排序若某遍比较没有发生交换，则排序结束【实验】冒泡排序程序【归纳总结】教学重难点是对顺序栈及其操作的理解【课外学习要求】完成四级项目第三阶段学生信息按顺序栈存储实现【课后分析及改进】注释教学设教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节计按每次课2学时撰写.的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案【教学进程安排】注释教学设计按每次课2重点设计教学步骤与具体内容安排学时撰写.

一、课外学习讲评

二、内容导入

三、主要内容设计

1.选择排序【讲授】永远用第一个与后面的比较,后面的小,则交换位置【实验】选择排序程序

2.插入排序【讲授】把数组看成两个序列，一个是已排好的序列，在数组的前面，另一个是未排序的序列，在数组的后面刚开始时，认为a

[0]已排好的序列，a[l]及其以后是未排序的序列把未排序序列的第一当作待插数，其排序过程如下一）待插数与已排序序列的最后一个比较，1）待插数大于已排序的的最后一个，待插数原位不动，作为已排序序列的最后一个2）待插数小于已排序的的最后一个，则待插数应插入在已排序序列前面某个位置这是一个边比较边移位的过程二边比较边移位的过程如下从已排序序列的最后一个开始，逐个与待插数比较若待插数小，则一排序序列数据向后移位自到待插数大为止，该位置就是插入位置【实验】插入排序程序【归纳总结】教学重难点是对顺序栈及其操作的理解【课外学习要求】完成四级项目第三阶段学生信息按顺序栈存储实现【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案【教学进程安排】注释教学设计按每次课2重点设计教学步骤与具体内容安排学时撰写.

一、课外学习讲评

二、内容导入

三、主要内容设计

1.归并排序【讲授】归并一一将两个或两个以上的有序表组合成一个新的有序表，叫〜2-路归并排序排序过程设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1两两合并，得到1n/2」个长度为2或1的有序子序列再两两合并，……如此重复，直至得到一个长度为n的有序序列为止【实验】归并排序程序【归纳总结】教学重难点是对顺序栈及其操作的理解【课外学习要求】完成四级项目第三阶段学生信息按顺序栈存储实现【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案【教学进程安排】注释教学设计按每次课2重点设计教学步骤与具体内容安排学时撰写

一、课外学习讲评讲评习题

二、内容导入

三、主要内容设计

1.【讨论】学生分组演示三级项目1演示+讲解2评委组提问小组回答问题3评委打分

2.【讲授】教师讲评1公布名次2讲评三级项目的完成情况3总结学生完成的三级项目的优缺点4布置假期改进方案【归纳总结】对所有作品进行讲评【课外学习要求】完成教材习题及复习，准备好期末考试【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案单元教案首页单元CU6学时4周次第16教学周教学环境设计与组课堂，笔记本电脑，小组合作织安排单元名单元项目查找常用的查找算法实现称名称理论知识理解并掌握常用查找算法的思想和实现方法学标具有较强的技术文档写作能力达度具有科技资料与文献的收集与检索能力专业技能教目具有自我学习能力及新技术开发与研究的能力及成具有正直并勇于负责的职业道德和敬业精神职业道德具备一名优秀工程师的基本素质线性查找算法；教学重折半查找算法；点难点二叉树查找算法学法教学方法讲授、讨论、演示、练习、实验、研究性学习、案例、合作学习、指导教学、任段手介务分析、自主学习、读书、问题教学媒教教学媒介教科书、板书、多媒体方

1.讲评一一课后作业学织

2.互动一一分组学习多种查找算法式教3,讲解一一学生将查找算法做为动画或PPT,做全班讲解组方4,操作一一编程实现查找算法课内实践环节编程实现查找算法实践环节课外实践环节平时成绩管理系统中，对学生学号、平时成绩、考勤成绩、作业成绩实现查找功能【教学进程安排】注释教学设计按每次课2重点设计教学步骤与具体内容安排学时撰写.

一、课外学习讲评讲评排序习题

二、内容导入,大家能想到的查找方法？

三、主要内容设计

1.线性查找【讲授】适用于无序线性结构【实验】线性查找程序2折半查找【讲授】适用于有序线性结构,可以大大节约时间，对于长度为2，°最多查找30次就能找到【实验】折半查找程序【归纳总结】折半查找的时间复杂度，优缺点【课外学习要求】用折半查找完成第一个四级项目的查找部分【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案课内实践环节编程实现二叉树的建立、遍历算法，哈夫曼编码实践环节课外实践环节平时成绩管理系统中，学生成绩按排序二叉树方式建立，实现基本操作算法【教学进程安排】注释教学设计按每次课2重点设计教学步骤与具体内容安排学时撰写.

一、课外学习讲评讲评学生用折半查找算法完成的其它小项目

二、内容导入.・复习二叉树知识

三、主要内容设计二叉树查找【讲授】在二叉排序树上进行查找的过程类似于折半查找【实验】学生完成二叉树的实训【归纳总结】教学重难点是对顺序栈及其操作的理解【课外学习要求】完成四级项目第三阶段学生信息按顺序栈存储实现【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案【教学进程安排】注释教学设计按每次课2重点设计教学步骤与具体内容安排学时撰写

一、课外学习讲评树形结构是非线性结构其特点是数据元素只能有一个前驱，可以有零个或多个后继

二、内容导入树是一种常用的非线性结构树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点树中所有结点可以有零个或多个后继结点

三、主要内容设计1,树的定义【讲授】树的定义树是n n20个结点的有限集合若n=0,则称为空树；否则，有且仅有一个特定的结点被称为根，当n〉l时，其余结点被分成m m0个互不相交的子集T1,T2,Tm,每个子集又是一棵树由此可以看出，树的定义是递归树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点树中所有结点可以有零个或多个后继结点【案例】行政机构，公司机构

2.树的基本术语【讲授】结点表示树中的元素，包括数据项及若干指向其子树的分支结点的度结点拥有的子树的个数叶子结点叶子度为0的结点分支结点度不为0的结点结点的层次树中根结点的层次为1,根结点子树的根为第2层，以此类推树的度树中所有结点度的最大值树的深度树中所有结点层次的最大值有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树【归纳总结】教学重是对树的概念理解，对术语的记忆【课外学习要求】思考怎样存储树？既要保存数据，乂要包含数据之间的关系【课后分析及改进】【教学进程安排】注释教学设计按每次课2重点设计教学步骤与具体内容安排学时撰写.

一、课外学习讲评在建立单链表的基础上引入二叉链的概念

二、内容导入任意一颗树都可以转化成二叉树反之二叉树叶可以转化成普通树

三、主要内容设计

3.二叉树的定义【讲授】二叉树也可以用递归的形式定义即二叉树是n n20个结点的有限集合当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树【案例】【讲授】

4.满二叉树和完全二叉树【讲授】如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树有一棵深度为h,具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为Pn的结点位置一一对应，则称这棵二叉树为完全二叉树

5.二叉树的性质【讲授】5个性质均不用硬记，只要画一个二叉树图就知道了最重要的是性质5,是根据结点编号建二叉树的依据【案例】【讲授】

6.二又树的顺序存储结构【讲授】按完全二叉树对结点编号，结点编号与数组的下标相同，根据下标可以得倒双亲和孩子的关系此种存储方式对于数据较简单的二叉树使用比较方便如果数据是大结构体，则可能浪费较大空间【案例】【讲授】【归纳总结】【课外学习要求】实现并阅读程序【教学进程安排】注释教学设计按每次课2重点设计教学步骤与具体内容安排学时撰写.

一、课外学习讲评提问二叉树为什么要用链式存储？

二、内容导入二叉树是一种非常重要的树形结构，其它的树形结构文体可以变化为二叉树

三、主要内容设计

1.二叉树的链式存储【讲授】根据二叉树的性质5,按完全二叉树的编号，输入结点编号和结点值,就可生成二叉链表由于后面结点的指针要赋予前面结点的左、右孩子指针域，故应设计一个指针数组，用于保存结点的指针根据结点编号可以得出其双亲结点的编号，及其结点是双亲的左孩子还是右孩子这样就可以根据结点编号建立二叉树【实验】按结点编号建立二叉树结点编号整除2得双亲编号若结点编号是偶数，则是左孩子，该结点的指针赋予双亲结点的左孩子指针域；若结点编号是奇数，则是右孩子，该结点的指针赋予双亲结点的右孩子指针域教学重难点是建立二叉树和显示二叉树2显示二叉树【讲授】用缩进显示出结点间的层次关系【实验】按结点编号建立二叉树，并用缩进显示二叉树【归纳总结】教学重难点是对程序的阅读和理解【课外学习要求】实现并阅读程序【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案【教学进程安排】注释教学设计按每次课2重点设计教学步骤与具体内容安排学时撰写

一、课外学习讲评

1.提问二叉树的存储方式

2.提问顺序存储和链式存储的编程思路

二、内容导入对二叉树的很多处理都是以遍历为基础,因此我们要熟练的掌握遍历（顺序表和单链表也存在遍历的问题，由于比较简单，没有单独作为问题讲解）

三、主要内容设计

1.先根遍历【讲授】先访问根结点，然后分别先序遍历左子树、右子树【案例】【讲授】

2.中根遍历【讲授】先中序遍历左子树，然后访问根结点，最后中序遍历右子树［案例】【实验】

3.后根遍历【讲授】先后序遍历左、右子树，然后访问根结点【案例】【实验】建立一颗二叉树，用三种方法遍历，显示遍历的结果【归纳总结】教学重难点是对遍历方式的递归过程的理解【课外学习要求】完成并实现程序的运行深入理解遍历的递归过程【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案【教学进程安排】注释教学设计按每次课2重点设计教学步骤与具体内容安排学时撰写.

一、课外学习讲评.深入理解二叉链

二、内容导入.・叶子结点没有孩子，其指针域为空为了利用空的指针域，引入线索二叉树的概念.

三、主要内容设计

1.线索二叉树【讲授】叶子结点没有孩子，其指针域为空为了利用空的指针域，可以令左孩子指针指向该结点的直接前驱，令右孩子指针指向该结点的直接后继某结点的左指针可以指向左孩子，也可以指向直接前驱；同样，右指针也可以指向右孩子,也可以直线直接后继因此又增加两个标志，左标志为0,左指针指向左孩子；左标志为1,左指针指向直接前驱右标志为0,右指针指向右孩子；右标志为1,右标志指向直接后继所谓直接前驱和直接后继，是由按什么方式遍历有关【案例】中序遍历的线索二叉树程序2,森林转化成二叉树3讲授】1将各棵树分别转换成二叉树2将每棵树的根结点用线相连3以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

4.二叉树转换成森林【讲授】1加线若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与P的双亲用线连起来2抹线抹掉原二叉树中双亲与右孩子之间的连线3调整将结点按层次排列，形成树结构【实验】练习森林转化成二叉树，二叉树转换成森林的步骤【归纳总结】线索二叉树的程序【课外学习要求】运行并阅读理解线索二叉树的程序【课后分析及改进】教学团队对课程/项目教学设计的可行性、知识与能力指标的达成度、教与学环节的设计、教学重点与难点的把握、教学方法手段的有效性、师生双边活动的设计、课内与课外的结合、教与学的效果等课堂教学过程情况进行总结与分析，共同研讨确定改进措施与方案【教学进程安排】注释教学设计按每次课2重点设计教学步骤与具体内容安排学时撰写.

一、课外学习讲评

二、内容导入,在通讯中，电文是以二进制的

0、1序列传送的在发送端，将电文中的字符转换成二进制的

0、1序列，在接受端，则需要将收到的

0、1序列还原成对应的字符序列设给出一段报文CASTSATA；希望的是传送电文时长度尽可能的短，试写出对应的二进制

0、1序列

三、主要内容设计

1.哈夫曼树的概念【讲授】把若干个带权的叶子结点生成一颗二叉树，要求结点的权乘以边条数之和为最小【案例】在通讯中的应用

2.哈夫曼树的生成【讲授】原则权小的结点离根结点远，权大的结点离根结点近方法先选两个权小的生成一颗二叉树，并形成一个有编号的新的根结点该结点的权为左、右子树权之和逐级进行，每次都是选两个权小的结点（包括新生成的根结点）生成二叉树，（注意，选择时，是从编号小的结点开始，若新结点的权和老结点的权相同，则选出的是老结点）直到选完全部结点

1.哈夫曼树应用举例一哈夫曼编码【讲授】把字母出现的频率作为字母的权权小的结点离根结点远，权大的结点离根结点近这样生成的二叉树就是哈夫曼树把左子树的边当作0,右子树的边当作1,由根结点到叶子结点的边就组成哈夫曼编码哈夫曼编码可以使文本的编码最短【练习】设给出一段报文CAST CASTSAT ATA TASA希望的是传送电文时长度尽可能的短

（1）画出构造的哈夫曼树

（2）计算带权路径长度

（3）求各字符的哈夫曼编码【归纳总结】何为哈夫曼树？哈夫曼编码？其作用是什么？【课外学习要求】

1.给定一组数列（10,18,16,25,6,9,16）分别代表字符A,B,C,D,E,F,G出现的频度，试画出哈夫曼树，给出各字符的编码

2.阅读理解哈夫曼编码的程序。