数据结构与算法“二叉树”教学设计 北京大学信息科学技术学院王腾蛟 1、二叉树在课程中的定位和前测知识点 二叉树是非常重要的树形数据结构。很多从实际问题中抽象出来的数据是二叉树形 的;而且许多算法如果采用二叉树形式解决则非常方便、高效。此外,以后将看到一般 树或森林都可通过简单的转换,得到与之相对应的二叉树,从而为一般树和森林的存储 和处理提供了有效方法 二叉树一章主要介绍了二叉树的周游,包括前序法、中序法、后序法,希望学生能 够掌握二叉树的周游算法及从二叉树周游结果得到二叉树的方法,并能根据要求,编写 合适的递归算法。 前测知识点要求如下,可以根据需要给学生补充 (1)线性表的实现和优缺点。 (2)栈与递归。 (3)队列的实现和比较 2、学习目标 (1)理解二叉树的主要概念与相关性质 (2)掌握二叉树的抽象数据类型、存储表示与实现效率 (3)熟练掌握二叉树的周游策略 (4)掌握二叉搜索树及其应用。 (5)理解堆的概念、性质,重点掌握堆的构造。 (6)理解 Huffman树的主要思想与具体应用。 3、知识点和学时分配 理论授课6学时,建议安排实验12学时。 各知识点建议授课时间如下 二叉树的基本概念 0.5小时 二叉树的抽象数据类型15小时 二叉树的存储结构 0.5小时1 数据结构与算法“二叉树”教学设计 北京大学信息科学技术学院 王腾蛟 1、二叉树在课程中的定位和前测知识点 二叉树是非常重要的树形数据结构。很多从实际问题中抽象出来的数据是二叉树形 的；而且许多算法如果采用二叉树形式解决则非常方便、高效。此外，以后将看到一般 树或森林都可通过简单的转换，得到与之相对应的二叉树，从而为一般树和森林的存储 和处理提供了有效方法。 二叉树一章主要介绍了二叉树的周游，包括前序法、中序法、后序法，希望学生能 够掌握二叉树的周游算法及从二叉树周游结果得到二叉树的方法，并能根据要求，编写 合适的递归算法。 前测知识点要求如下，可以根据需要给学生补充 （1） 线性表的实现和优缺点。 （2） 栈与递归。 （3） 队列的实现和比较。 2、学习目标 （1） 理解二叉树的主要概念与相关性质。 （2） 掌握二叉树的抽象数据类型、存储表示与实现效率。 （3） 熟练掌握二叉树的周游策略。 （4） 掌握二叉搜索树及其应用。 （5） 理解堆的概念、性质，重点掌握堆的构造。 （6） 理解 Huffman 树的主要思想与具体应用。 3、知识点和学时分配 理论授课 6 学时，建议安排实验 12 学时。 各知识点建议授课时间如下： 二叉树的基本概念 0.5 小时 二叉树的抽象数据类型 1.5 小时 二叉树的存储结构 0.5 小时