数据结构教案第六章.doc

1、安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称 数据结构 教学对象 新华软工教 材 数据结构（C 语言）授课内容 第六章 树和二叉树 课 时 2教学目的与要求了解树、森林的定义；掌握二叉树的定义、性质、存储结构；掌握二叉树的遍历、树和森林的存储，哈夫曼树的应用重点、难点重点：二叉树相关操作难点：二叉树的三种遍历课 型 电脑理论 教学方法 投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务一、树的有关概念前言：树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用；树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象的表示

2、出来等等。一、树的概念 树形结构是一种重要的非线性结构，讨论的是层次和分支关系。树是 n 个结点的有限集合，在任一棵非空树中：（1）有且仅有一个称为根的结点。（2）其余结点可分为个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。教学过程设计(续表)树是递归结构，在树的定义中又用到了树的概念例：上面的图是一棵树T=A, B, C, D, E, F, G, H, I, J，K，L，MA 是根，其余结点可以划分为 3 个互不相交的集合：T1=B, E, F，K，L , T2=C, G , T3=D, H, I, J，M这些集合中的每一集合都本身又是一棵树，它们是 A 的子树。

3、例如 对于 T11，B 是根，其余结点可以划分为 2 个互不相交的集合：T11=E，K ，L，T12=F，T11,T12 是 B 的子树。从逻辑结构看：1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构 （除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。二、树的应用1、树可表示具有分枝结构关系的对象例 1家族族谱例 2单位行政机构的组织关系2、树是常用的数据组织形式有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数

4、据，将它们用树的形式来组织。例 3 计算机的文件系统不论是 DOS 文件系统还是 window 文件系统，所有的文件是用树的形式来组织的。JIACB DHGFEK L M教学过程设计(续表)三、树的表示1）图示表示 2）二元组表示3）嵌套集合表示 4）凹入表示法（类似书的目录）四、树的 基本术语树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；双亲结点：B 结点是 A 结点的孩子，则 A结点是 B 结点的双亲；兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该

5、结点的子孙结点层：根结点的层定义为 1；根的孩子为第二层结点，依此类推；树的深度：树中最大的结点层结点的度：结点子树的个数树的度： 树中最大的结点度。叶子结点：也叫终端结点，是度为 0 的结点；分枝结点：度不为 0 的结点；有序树：子树有序的树，如：家族树；无序树：不考虑子树的顺序；森林；互不相交的树集合；森林和树之间的联系是：一棵树去掉根 ，其子树构成一个森林；一个森林增加一个根结点成为树。复习思考题作 业上机任务案例分析：例 1家族族谱例 2单位行政机构的组织关系参考文献课后记（或归纳小结）本章主要介绍树的定义，日常应用，树的概念 ；为以后的二叉树学习带来好的理解安徽新华电脑专修学院课堂教

6、学教案（电脑应用课使用）课程名称 数据结构 教学对象 新华软工教 材 数据结构（C 语言）授课内容 第六章 树和二叉树 课 时 2教学目的与要求了解树、森林的定义；掌握二叉树的定义、性质、存储结构；掌握二叉树的遍历、树和森林的存储，哈夫曼树的应用重点、难点重点：二叉树相关操作难点：二叉树的三种遍历课 型 电脑理论 教学方法 投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务一、树的有关概念（续）复习上一次的内容，然后提出问学生，接着从上一次内容进入今天新的课程，让课程内容的完整性五、树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：

7、1）initiate (T); T 树的初始化，包括建树。2） root (T); 求 T 树的根。3）parent (T , x ): 求 T 树中 x 结点的双亲结点。4）Child (T, x, i )： 求 T 树中 x 结点的第 i 个孩子结点。教学过程设计(续表)5）right_sibling (T, x ): 求 T 树中 x 结点的右兄弟6）insert_Child (y, i, x ): 将根为 x 的子树置为 y 结点的第 i 个孩子7） del_child (x, i); 删除 x 结点的第 i 个孩子8）traverse (T); 遍历 T 树。按某个次序依次访问树中每

8、一个结点，并使每个结点都被 访问且只被访问一次。9）clear (T); 置空 T 树任务二、二 叉 树树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树二叉树一、二叉树的概念二叉树： 或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。说明1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于 2;2）左、右子树不能颠倒有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;二、二叉树的基本形态(a) 空树(b) 仅有根(c) 右子树空(d) 左、右子树均在(e) 左子树空三

9、、应用举例AFGE DC B教学过程设计(续表)例 1 可以用二叉树表示表达式a+b*(c-d)-e/f例 2 双人比赛的所有可能的结局 开局连赢两局或五局三胜四、 二叉树性质性质 1 在二叉树的第 i 层上最多有 2i-1 个结点性质 2 深度为 k 的二叉树最多有 2k-1 个结点性质 3 设二叉树叶子结点数为 n0，度为 2 的结点 n2，则 n0 = n2 +1此三个性质是对任何一棵二叉树都实用的复习思考题作 业上机任务案例分析：例 1 ：已知二叉树有 50 个叶子结点，则该二叉树的总结点数是多少（99）例 2：已知完全二叉树的第七层有 8 个结点，则其叶子结点数是（36）参考文献课后

10、记（或归纳小结）本章主要介绍二叉树的定义，二叉树的五种形态、还有它的性质，并举例说明这些性质安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称 数据结构 教学对象 新华软工教 材 数据结构（C 语言）授课内容 第六章 树和二叉树 课 时 2教学目的与要求了解树、森林的定义；掌握二叉树的定义、性质、存储结构；掌握二叉树的遍历、树和森林的存储，哈夫曼树的应用重点、难点重点：二叉树相关操作难点：二叉树的三种遍历课 型 电脑理论 教学方法 投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务二、二 叉 树（续）复习上一次的内容，然后提问学生，接着从上一次内容进入

11、今天新的课程，让课程内容的完整性满二叉树：如果深度为 k 的二叉树，有 2k-1 个结点则称为满二叉树。完全二叉树：如果深度为 k 的二叉树，有 2k-1 个结点则称为满二叉树；对其中的结点的编号：根的号为 1，从上到下，从左到右每个结点依次加 1 为其编号且一一对应，称之为完全二叉树。下面是两个关于完全二叉树的性质：性质 4 ：具有 n 个结点的完全二叉树的深度为：trunc(log2 n)+1. trunc(x) 为取整函数。教学过程设计(续表)对完全二叉树的结点编号：从上到下，每一层从左到右性质 5：在完全二叉树中编号为 i 的结点1）若有左孩子，则左孩编号为 2i2）若有右孩子，则右孩

12、子结点编号为 2i+13）若有双亲，则双亲结点编号为 trunc(i/2)三二叉树存贮结构1、二叉树的顺序结构满二叉树或完全二叉树的顺序结构：用一组连续的内存单元，按编号顺序依次存储完全二叉树的元素.例如，用一维数组 bt 存放一棵完全二叉树，将标号为 i 的结点的数据元素存放在分量 bti-1中。存储位置隐含了树中的关系，树中的关系是通过完全二叉树的性质实现的。例如，bt5（i=6) 的双亲结点标号是 k=trunc(i/2)=3,双亲结点所对应的数组分量 btk-1=bt2非完全二叉树的顺序结构：按完全二叉树的形式补齐二叉树所缺少的那些结点，对二叉树结点编号,将二叉树原有的结点按编号存储到内存单元“相应 ”的位置上。但这种方式对于畸形二叉树，浪费较大空间。2、 二叉链表二叉链表中每个结点包含三个域：数据域、左指针域、右指针域 ；图见课件 Struct node int data;struct node *lch,*rch;注：在含有 n 个结点的二叉链表中有 n+1 个空链域，这在线索二叉树中将利用到这些空的链域3、三叉链表三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域Struct node int data;struct node *lch,*rch,*parent;见课件和笔记