2008计算机第6章树和二叉树

皖江学院2007计算机第6章树和二叉树数据结构教案陈少军第1页共5页安徽师范大学数学计算机科学学院授课章节第6章树和二叉树课时安排10课时+2实验一、教学目标掌握1、树和二叉树的性质，相关术语及基本概念。2、二叉树的两种存储方法，重点是链式存储据。3、二叉树三种顺序遍历及其递归实现算法。4、二叉树的层次遍历5、创建链式存储的二叉树的算法。6、中序线索二叉树的算法：中序线索二叉树上基本算法（遍历、求指定结点的前驱和后继、查找指定值的结点）。7、树的遍历算法（先根遍历、后根遍历）；森林的遍历算法（前序遍历，后序遍历）8、哈夫曼树的概念；哈夫曼树的构造算法；哈夫曼编码9、通过本章的算法的学习，让学生认识到递归定义的数据结构之下求解相应问题，思路清晰和简洁算法设计方法是采用递归的方式。理解1、二叉树三种遍历的非递归算法及其与栈的关系2、在中序线索树指定结点下插入新结点的算法，学会在复杂情形下分类讨论的方法。3、树的三种存储结构（双亲表示法、孩子表示法、孩子兄弟表示法）及各自的特点（优点、缺点）4、掌握树、森林和对应的二叉树相互转换算法。二、教学重点1、二叉树的性质；二叉树的链式存储。2、二叉树三种顺序遍历算法，遍历算法的应用。3、中序线索二叉树的算法及其简单应用。4、哈夫曼树的构造和编码算法—注意程序实现的编程技巧。三、教学难点1、二叉树性质的运用2、二叉树三种遍历的非递归算法。3、中序线索二叉树的理解及先序后序线索算法的实现。4、二叉树中，学会递归的思想求解问题，用遍历的典型算法解决一些具体问题。四、主要教学内容1、树的定义及其相关概念（如节点的度、终端节点、树的深度、有序树、无序树、森林等）2、树的表示（四种表示方法）3、二叉树的定义4、二叉树的基本性质（5条性质）5、二叉树的存储结构（顺序存储、链式存储）6、二叉树遍历的定义7、先序遍历、中序遍历、后序遍历的递归算法。8、利用栈实现遍历的对应非递归算法。9、二叉树层次遍历10、线索的概念；中序线索二叉树；中序线索二叉树的应用11、树的三种存储结构（双亲表示法、孩子表示法、孩子兄弟表示法）。12、树、森林和对应二叉树间的相互转换（自然语言描述）13、树和森林的遍历（简要陈述）14、哈夫曼树的概念；哈夫曼树的构造算法；哈夫曼编码五、教学过程设计1.整体教学设计1.1第1次课（2学时）皖江学院2007计算机第6章树和二叉树数据结构教案陈少军第2页共5页安徽师范大学数学计算机科学学院现实世界存在一类事物（如机构的组织）需要用一种特殊的数据结构—树去描述。引入树的定义树相关基本概念树的表示特例：二叉树概念及定义研究二叉树树、森林与二叉树的相互转换二叉树的基本性质如何表示二叉树二叉树的存储课时小结1.2第2次课（2学时）按一定规则依次访问二叉树节点（把二叉树的结点按规则线形排列）提出二叉树的遍历1、先根、中根、后根遍历的递归算法2、层次遍历（用队列）总结特点并对比思考遍历的递归算法如何转换为非递归算法讲解中根遍历非递归算法，其它留做思考（提示）遍历算法的实际应用讲解遍历算法的应用例子（教材）课时小结1.3第3次课（2学时）上次课介绍的遍历可看出，访问某个结点指定遍历次序下的前驱、后继可以通过遍历的方法。能否有简便的方法呢？１、增加结点的指针域，用来指向它在某种遍历次序下的前驱和后继２、利用二叉树中结点的空指针域，使得这些指针域指向它可能存在的前驱和后继。提出线索二叉树介绍线索二叉树的逻辑和存储示意图讲解如何实现线索（线索二叉树的算法）１、讲解中序线索二叉树２、提出问题：如何实现非递归算法线索二叉树的遍历１、线索下的遍历+对比非线２、查找结点（指定值前驱、后继、实现）+索二叉树课时小结1.4第4次课（2学时）二叉树只是树的特例，现实中很多事物需要用树来描述或者用多棵树（森林）表示。由于我们已经在二叉树上进行了很多研究，能否将树或森林的问题转换成二叉树的问题呢？提出树和森林转换成对应二叉树首先介绍树的存储表示（三种方式）介绍树、森林转换成对应的二叉树算法（抽象算法，不依赖具体存储结构）二叉树还原成对应的树和森林（二叉树转换成对应的树和森林的算法）回顾二叉树有遍历的定义定义树和森林的遍历（对比二叉树遍历的定义，无中根遍历）树和森林的遍历算法对比分析树或森林与其对应的二叉树遍历的对应关系课时小结1.5第5次课（2学时）通过前几节课内容的学习，基本上已经完成介绍树和二叉树的内容，下面介绍二叉树的一个特殊应用，也是一种特殊的二叉树。通信系统中的编码问题皖江学院2007计算机第6章树和二叉树数据结构教案陈少军第3页共5页安徽师范大学数学计算机科学学院解决方法：最优二叉树—哈夫曼树，最优二叉树及其相关概念介绍具体的几种不同带权树及其代价，建立哈夫曼树的感性认识。介绍手工建立哈夫曼树的过程介绍在哈夫曼树上生成哈夫曼编码介绍建立哈夫曼树及哈夫曼编码的C语言算法本章知识点小结知识点列表树树的定义和性质和树相关的概念树的存储结构树和森林的遍历二叉树二叉树的定义二叉树的性质二叉树的存储结构二叉树的遍历二叉树的线索化哈夫曼树哈夫曼树的定义哈夫曼树的建立手工建立哈夫曼树C语言算法哈夫曼编码知识点联系图2.新课内容2.1第1次课（2学时）1)树的定义和特点2)树的表示（直观表示、嵌套集合表示、凹入表示、广义表示）3)树的基本术语性质进入本章定义提出非线性结构—树遍历算法二叉树相关概念三种存储结构特例性质利用基本性质求解问题遍历二叉树的线索非递归遍历利用遍历求解问题递归遍历存储结构定义树、森林与二叉树的转换哈夫曼树哈夫曼编码定义性质皖江学院2007计算机第6章树和二叉树数据结构教案陈少军第4页共5页安徽师范大学数学计算机科学学院4)二叉树的定义和特点5）二叉树的性质a)在二叉树的第i层上最多有2^(i-1)个结点（i=1）b)深度为K的二叉树最多有2^K-1个结点（K=1）c)对于任意一颗二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。d)具有n个结点的完全二叉树的深度为」log2n」+1e)对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i（1=i=n），都有：①如果i=1，则结点i是这颗完全二叉树的根，没有双亲；否则其双亲结点的编号为i/2;②如果2in，则结点i没有左孩子，否则其左孩子结点的编号为2i；③如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1;6)介绍二叉树顺序和链式存储结构并进行比较。2.2第2次课（2学时）1)定义二叉树的遍历2)定义先根、中根、后根遍历和层次遍历3)先根、中根、后根遍历的递归算法4）中根遍历的非递归算法，提出问题；思考先根、后根的非递归算法。5）二叉树的层次遍历6）提出思考：树有先根、中根、后根遍历吗？为什么？7）讲解二叉树的遍历算法的具体应用（计算二叉树结点个数、求二叉树高度、建立二叉树等）2.3第3次课（2学时）1)线索的概念及其对应结点存储结构（赠加标志位）2）中序先作二叉树的算法3）在中序线索二叉树上查找指定结点的前驱和后继的算法；中序线索二叉树的遍历算法。4）在中序线索二叉树上查找指定值X的结点的算法。2.4第4次课（2学时）1）树的三种存储结构（双亲表示法、孩子表示法、孩子兄弟表示法）和各自特点分析。2)树转换为二叉树；森林转换为二叉树；二叉树还原成对应的树或森林。3）树的遍历（先根遍历、后根遍历）；森林的遍历（前序遍历、后序遍历）2.5第5次课（2学时）1）介绍通讯编码最短问题。2）介绍最优二叉树（哈夫曼树）及其相关概念。3）介绍手工构造哈夫曼树以及进行哈夫曼编码的过程4）讲解构造哈夫曼树及进行哈夫曼编码的算法。5）树和二叉树一章小结3.新课内容要点提示l）介绍树的定义和二叉树的定义时要强调定义的方式是递归，定义的递归特征是后面很多算法采用递归的最直接理由。2）二叉树的基本性质是很多习题解题方法和根源所在，不仅要记住，更要理解，学会用证明二叉树基本性质的方法去求解问题。3）提醒二叉树的两种存储结构会给具体的算法实现代来什么样的差异。皖江学院2007计算机第6章树和二叉树数据结构教案陈少军第5页共5页安徽师范大学数学计算机科学学院4）备课时注意二叉树遍历的递归算法转换成非递归算法的思路，如何利用栈实现？转换的关键是理解递归的执行过程与栈的关系，也可以介绍清华教材上介绍的机械式转换算法。5）通过实例强调遍历算法对于二叉树应用问题求解的重要性。6）讲解通过先序遍历算法建立二叉树时，强调或者通过提问来明确递归建立二叉树时输入的字符序列应该是什么，为什么是这样？加强学生对递归算法执行过程的理解；同时让学生思考如何实现中序和后序建立二叉树的算法。7）强调线索二叉树之前需要对原来二叉树结点做一定的改造（添加标志域：ltag和rtag)；对于线索二叉树算法，介绍中序线索二叉树的递归算法，让学生思考如何实现先序和后序线索二树，以及编写它们所对应的非递归算法。8）强调建立线索二叉树带来的访问上的便利，同时这种遍历是用牺牲空间来赢得时间上的效率的提高。9）对于树、森林和对应二叉树之间的相互转换，应让学生认识到，这种转换是确定的，结果是唯一的；因此树、森林和对应二叉树之间的映射关系是一种一一映射。10）哈夫曼树一般是采用线性结构一数组实现其存储的，结点之间链接是一种静态链接。4.布置作业和实验（指定题目）5.下一章课程预习要点现实同样存在树不能描述的更复杂的事物及其之间的关系，如城市之间的交通网、电话网络等，需要我们用更复杂的数据结构去描述，去解决实际问题，这就下一章的内容一图；同时请同学们预习时注意以下几点问题：(l)什么是图，它是递归定义的吗？(2)图的存储有几种方法，各自的特点？(3)理解图的深度和广度遍历算法，及其在实际问题中应用；同时注意，对于图来说，给出的定义是非递归的，而教材实现的深度遍历算法是递归的，注意算法设计时的技巧。(4)提醒大家复习离散数学相关的内容。六、执行情况七、实践安排八、课后反馈九、期末总结