第10章教案 基本数据结构的扩展《Python程序设计基础教程》.docxVIP

PAGE 25 第10章 基本数据结构的扩展 课程名称 Python程序设计基础教程 章名 基本数据结构的扩展 教学内容 基本数据结构的扩展 课时 4 项目性质 □演示性 □验证性 □设计性 √综合性 授课班级 授课日期 授课地点 教学目标 掌握Python中二叉树的递归遍历 掌握Python中的堆排序 掌握Python中的队列 教学内容 Python中二叉树的递归遍历 Python中的堆排序 Python中的队列 教学重点 Python中的队列 教学难点 Python中的队列 教学准备 装有Python的计算机 教学课件PPT 教材：《Python程序设计基础教程（慕课版）》 作业设计 教学过程 教学环节 教学内容与过程 （教学内容、教学方法、组织形式、教学手段） 课前组织 做好上课前的各项准备工作（打开计算机、打开课件、打开软件、打开授课计划、教案等），吸引学生注意力。 课程说明 【课前说明】 从二叉树的基本概念引入本章学习内容。 【目的】 使学生从了解本节课的学习目标、学习重点、考评方式等方面明确课程学习的要求和目标。 课程内容描述 10.1 Python中二叉树的递归遍历 10.1.1 二叉树的基本概念 计算机中，数据元素在不同的场合还可以被称作“结点”“顶点”“记录”等。在二叉树这种数据结构中，把数据元素统称为“结点”。 “二叉树”是一个由结点组成的有限集合。这个集合或者为空，或者由一个称为“根”的结点及两棵不相交的二叉树组成，这两棵二叉树分别称为这个根结点的“左子树”和“右子树”。 当二叉树非空时，是通过结点之间想象中的一条线来表示从一个结点到它的两个子树结点（如果有的话）间的联系的，这个上层的结点称为“父结点”，两个子结点就称为父结点的“孩子结点”或“叶结点”。 由二叉树的定义可以知道，它其实是一个递归式的定义，因为在定义一棵二叉树时，又用到了二叉树这个术语：一个结点的左、右子树也是二叉树。如果子树是空的，那么这时就说该结点没有“左孩子”或者没有“右孩子”。 综上所述，二叉树有如下的特征： ● 二叉树可以是空的，空二叉树没有任何结点。 ● 二叉树上的每个结点最多可以有两棵子树，这两棵子树是不相交的。 ● 二叉树上一个结点的两棵子树有左、右之分，次序是不能颠倒的。 例10-1 下图所示的是二叉树的几种图形表示。 上图（a）所示为一棵空二叉树，我们用符号“Ф”来表示；上图（b）所示为一棵只有一个结点的二叉树，这个结点就是这棵二叉树的根结点，由于该二叉树只有一个根结点，所以也可以说这是一棵左、右子树都为空的二叉树；上图（c）所示为由一个根结点、左子树的根结点B、右子树的根结点C组成的一棵二叉树；上图（d）所示为一棵只含左子树的二叉树（当然，也可以有只含右子树的二叉树，这里没有给出）；上图（e）所示为一棵普通的二叉树，其左子树只有根结点B，右子树则由若干个结点组成，整棵二叉树可以划分为4层，分别是第0层～第3层。 二叉树是一种非线性结构，人们无法使用熟悉的顺序（也就是线性）方法知道一个结点的“下一个”是谁，只有人为地做出限定，才能去访问某结点中的数据。 所谓“遍历”二叉树，是指按照规定的路线对二叉树进行有哪些信誉好的足球投注网站，以保证里面的每个结点被访问一次，而且只被访问一次。 由于一棵非空二叉树是由根结点及两棵不相交的左、右子树3个部分组成的，因此如果人为规定一种顺序，在到达每一个结点时，都按照这个规定去访问与该结点有关的3个部分，那么就可以访问二叉树上的所有结点，且每个结点只被访问一次。 若用T、L和R分别表示二叉树的根结点、左子树和右子树，那么在到达每一个结点时，访问结点的顺序可以有以下6种不同的组合形式： ● TLR——先访问根结点，再访问左子树，最后访问右子树。 ● LTR——先访问左子树，再访问根结点，最后访问右子树。 ● LRT——先访问左子树，再访问右子树，最后访问根结点。 ● TRL——先访问根结点，再访问右子树，最后访问左子树。 ● RTL——先访问右子树，再访问根结点，最后访问左子树。 ● RLT——先访问右子树，再访问左子树，最后访问根结点。 前3个规定的特点是到达一个结点后，对左、右子树来说，总是“先访左、后访右”；后3个规定的特点是到达一个结点后，对左、右子树来说，总是“先访右、后访左”。如果对左、右子树，我们约定总是“先访左、后访右”，那么访问结点的6种顺序就只剩下3种不同的组合形式：TLR、LTR、LRT。通常，称TLR为二叉树的先根遍历或先序遍历（因为T在最前面），称LTR为中根遍历或中序遍历（因为T在中间），称LRT为后根遍历或后序遍历（因为T在最后面）。 例10-2 以先根遍历（TLR）的顺序访问下图所示的二叉树，并给出遍历后的结点访问序列。 先根遍历的总体规定是每到达二