数据结构说课教案

《数据结构说课教案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程教案课程名称：数据结构授课专业：计算机科学与技术主讲教师：2013年10月19日讲授主题遍历二叉树及二叉树的遍历算法举例授课时数1教学目的：1.掌握二叉树遍历的算法。教材中介绍了三种（先、中、后序）方法。2.遍历算法是基础，由此导出许多实用的算法，如求二叉树的高度、各结点的层次数、度为0、1、2的结点数等。3．由二叉树的遍历的前序和中序序列或后序和中序序列可以唯一构造一棵二叉树，要会手工模拟及编写算法。由前序和后序序列不能唯一确定一棵二叉树。4.通过典型算法加深的二叉树的理解。本章节的教学重点、难点：重点

2、是二叉树的递归遍历算法难点是遍历算法的应用教学方法、教学手段：1.二叉树的遍历算法（20分钟）3.二叉树的遍历算法举例（25分钟）使用教具：计算机和投影仪教学内容（讲授提纲）1.二叉树的遍历的定义：按某种规律，访问二叉树的结点，使每个结点被访问一次且仅一次。访问的含义包括查询、打印、计算、修改等对结点的操作。遍历的过程，实际上是按某种规律，将一个非线性结构的结点排成一个线性序列，使每个结点在这种遍历中有唯一前驱和后继关系。一棵二叉树的遍历序列（在某种遍历方式下）是唯一的，但一般说，二叉树不能由某一遍历序列唯一

3、确定。2.二叉树的递归遍历算法二叉树=根结点+左子树+右子树将树的遍历转变为子树的遍历。若二叉树为空，则空操作，否则：访问根结点；（）遍历左子树；（）遍历右子树；一句话，根据“访问根结点；”在三句话中位置的不同，分为前序、中序、后序遍历。3.二叉树的先序遍历先序算法：根左右①二叉树为空，结束②访问根结点③先序遍历左子树④先序遍历右子树4.二叉树的中序遍历中序算法：左根右①二叉树为空，结束②序遍历左子树③问根结点④中序遍历右子树5.二叉树的后序遍历后序算法：左右根①二叉树为空，结束②序遍历左子树③序遍历右子树④

4、访问根结点6.应用举例先序序列：根左右ABDECF中序序列：左根右DBEAFC后序序列：左右根DEBFCA遍历序列与二叉树不是一一对应的。例：若前序序列为123，对应的二叉树有5种。7.由二叉树遍历得到的一些重要性质已知二叉树的先序序列和中序序列，可以唯一确定一棵二叉树。已知二叉树的后序序列和中序序列，可以唯一确定一棵二叉树；已知二叉树的先序序列和后序序列，不能唯一确定一棵二叉树；已知二叉树的层次序列和中序序列，可以唯一确定一棵二叉树。讨论：二叉树和其遍历序列是否一一对应？先序+中序=>二叉树示例：先序:AB

5、HFDECKG中序:HBDFAEKCG递归问题：分解策略，最终小问题的解决方案。后序+中序=>二叉树OK先序+后序=>二叉树NO8、实例：再论表达式的存储结构表达式可以用二叉树表示，对二叉树进行前序、中序和后序遍历可以得到表达式的前缀、中缀和后缀表示。用二叉树表示表达式:((a+b)+c*(d+e)+f)*(g+h)前序遍历：*+++ab*c+def+gh中序遍历：a+b+c*d+e+f*g+h后序遍历：ab+cde+*+f+gh+*本章节的教学重点、难点：重点是二叉树的递归遍历算法难点是遍历算法的应用教学方

6、法、教学手段：1.二叉树的遍历算法（20分钟）3.二叉树的遍历算法举例（25分钟）使用教具：计算机和投影仪自测题：6.9对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左、右孩子中，其左孩子的编号小于其右孩子的编号，是采用何种次序的遍历实现编号的。6.12对任意一棵树，设它有n个结点，这n个结点的度数之和为多少？作业与上机：：1、根据含空标志的先序序列，建立二叉树2、根据先序序列、中序序列，建立二叉树参考资料：1．陈守孔等著《算法与数据结构C语言版》机械工业出版社200

7、72．陈守孔等著《算法与数据结构考研试题精析》机械工业出版社20083．严蔚敏等著《数据结构C语言版》清华大学出版社2005