2022年数据结构教案第六章.docx
( 4.5 )《2022年数据结构教案第六章.docx》由会员分享，可在线阅读，更多相关《2022年数据结构教案第六章.docx（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选学习资料 - - - - - - - - - 名师精编 优秀教案安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称 数据结构 教学对象 新华软工教 材 数据结构（ C语言）授课内容 第六章 树和二叉树 课 时 2 教学目的 明白树、森林的定义；把握二叉树的定义、性质、储备结与要求 构；把握二叉树的遍历、树和森林的储备,哈夫曼树的应用重点 ：二叉树相关操作重点、难点难点： 二叉树的三种遍历投影、争论、板书课型电脑理论教学方法教学过程 设计（包括讲授 学问、演示 内容及案 例、提问及 同学演示内任务一、树的有关概念 前言：树型结构是一类重要的非线性数据结构；其中以树和二叉树最为常用；树
2、结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可 用树形象的表示出来等等；一、 树的概念树形结构是一种重要的非线性结构,争论的是层次和分支关系；树是n 个结点的有限集合,在任一棵非空树中：（1）有且仅有一个称为根的结点；（2）其余结点可分为个互不相交的集合,而且这些集合中的每一集合都本身又是一棵树,称为根的子树；容）名师归纳总结 - - - - - - -第 1 页,共 31 页精选学习资料 - - - - - - - - - 名师精编 优秀教案A K E B F C H D J L G I M 树是递归结构,在树的定义中又用到了树的概念例：上面的图是一棵树T=A, B, C,
3、 D, E, F, G, H, I, J,K,L,M A 是根,其余结点可以划分为3 个互不相交的集合：教 学 过 程 设 计 续表 T1=B, E, F,K, L , T2=C, G , T3=D, H, I, J ,M 这些集合中的每一集合都本身又是一棵树,它们是A 的子树；例如对于 T11,B 是根,其余结点可以划分为2 个互不相交的集合：T11=E,K,L ,T12=F ,T11,T12 是 B 的子树；从规律结构看：1）树中只有根结点没有前趋；2）除根外,其余结点都有且仅一个前趋；3）树的结点,可以有零个或多个后继；4）除根外的其他结点,都存在唯独条从根到该结点的路径；5）树是一种分
4、枝结构（除了一个称为根的结点外）每个元素都有且仅有一 个直接前趋,有且仅有零个或多个直接后继；二、树的应用1、树可表示具有分枝结构关系的对象 例 1家族族谱 例 2单位行政机构的组织关系2、树是常用的数据组织形式有些应用中数据元素之间并不存在间分支结构关系,但是为了便于治理和使用数据,将它们用树的形式来组织；例 3 运算机的文件系统不论是 DOS 文件系统仍是 window 文件系统,全部的文件是用树的 形式来组织的；名师归纳总结 - - - - - - -第 2 页,共 31 页精选学习资料 - - - - - - - - - 名师精编 优秀教案三、树的表示 1）图示表示 2）二元组表示 3
5、）嵌套集合表示 4）凹入表示法（类似书的目录）四、树的 基本术语树的结点：包含一个数据元素及如干指 向子树的分支；孩子结点：结点的子树的根称为该结点 的孩子；双亲结点： B 结点是 A 结点的孩子,就 A 结点是 B 结点的双亲；兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；教 学 过 程 设 计 续表 祖先结点 : 从根到该结点的所经分支上的全部结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙结点层：根结点的层定义为1；根的孩子为其次层结点,依此类推；树的深度：树中最大的结点层 结点的度：结点子树的个数树的度：树中最大的结点度；叶子结点：也叫终端结点,是度为0 的结点；分
6、枝结点：度不为0 的结点；有序树：子树有序的树,如：家族树；无序树：不考虑子树的次序；森林；互不相交的树集合；森林和树之间的联系是：一棵树去掉根,其子树构成一个森林；一个森林增加一个根结点成为树；名师归纳总结 - - - - - - -第 3 页,共 31 页精选学习资料 - - - - - - - - - 复习摸索题案例分析：名师精编优秀教案作业例 1家族族谱例 2单位行政机构的组织关系上机任务参考文献课后记本章主要介绍树的定义,日常应用,树的概念；为以后的二叉树学习（或归纳小带来好的懂得结）名师归纳总结 - - - - - - -第 4 页,共 31 页精选学习资料 - - - - - -
7、 - - - 名师精编 优秀教案安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称 数据结构 教学对象 新华软工教 材 数据结构（ C语言）授课内容 第六章 树和二叉树 课 时 2 教学目的 明白树、森林的定义；把握二叉树的定义、性质、储备结与要求 构；把握二叉树的遍历、树和森林的储备,哈夫曼树的应用重点 ：二叉树相关操作重点、难点难点： 二叉树的三种遍历投影、争论、板书课型电脑理论教学方法教学过程 设计（包括讲授 学问、演示 内容及案 例、提问及 同学演示内任务一、树的有关概念（续）复习上一次的内容,然后提出问同学,接着从上一次内容进入今日新的课 程,让课程内容的完整性五、树的基本操
8、作树的应用很广,应用不同基本操作也不同；下面列举了树的一些基本操作：1）initiate T; T 树的初始化,包括建树；2） root T; 求 T 树的根；3）parent T , x : 求 T 树中 x 结点的双亲结点；4）Child T, x, i ： 求 T 树中 x 结点的第i 个孩子结点；容）名师归纳总结 - - - - - - -第 5 页,共 31 页精选学习资料 - - - - - - - - - 名师精编 优秀教案5）right_sibling T, x : 求 T 树中 x 结点的右兄弟6）insert_Child y, i, x : 将根为 x 的子树置为y 结点的
9、第i 个孩子7） del_child x, i; 删除 x 结点的第 i 个孩子 8）traverse T; 遍历 T 树；按某个次序依次拜访树中每一个结点,并使 每个结点都被 拜访且只被拜访一次；9）clear T; 置空 T 树任务二、二 叉 树树是一种分枝结构的对象, 在树的概念中, 对每一个结点孩子的个数没 有限制,因此树的形状多种多样,本章我们主要争论一种最简洁的树 二叉树一、 二叉树的概念二叉树： 或为空树,或由根及两颗不相交的左子树、 右子树构成, 并且左、教右子树本身也是二叉树；EACFB学过程D设计续表 G说明1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于 2;
10、 2）左、右子树不能颠倒 有序树 ; 3）二叉树是递归结构,在二叉树的定义中又用到了二叉树的概念 ; 二、 二叉树的基本形状a 空树 b 仅有根 c 右子树空 d 左、右子树均在 e 左子树空三、应用举例名师归纳总结 - - - - - - -第 6 页,共 31 页精选学习资料 - - - - - - - - - 名师精编 优秀教案例 1 可以用二叉树表示表达式 a+b*c-d-e/f 例 2 双人竞赛的全部可能的结局 开局连赢两局或五局三胜四、 二叉树性质性质 1 在二叉树的第 i 层上最多有 2 i-1 个结点 性质 2 深度为 k 的二叉树最多有 2 k-1 个结点 性质 3 设二叉树
11、叶子结点数为 n0,度为 2 的结点 n2,就 n0 = n2 +1 此三个性质是对任何一棵二叉树都有用的教 学 过 程 设 计 续表 名师归纳总结 - - - - - - -第 7 页,共 31 页精选学习资料 - - - - - - - - - 复习摸索题案例分析：名师精编优秀教案作业例 1 ：已知二叉树有 50 个叶子结点,就该二叉树的总结点数是多少 （99）例 2：已知完全二叉树的第七层有8 个结点,就其叶子结点数是（36）上机任务参考文献课后记 本章主要介绍二叉树的定义,二叉树的五种形状、仍有它的性质,并举（或归纳小例说明这些性质结）名师归纳总结 - - - - - - -第 8 页
12、,共 31 页精选学习资料 - - - - - - - - - 名师精编 优秀教案安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称 数据结构 教学对象 新华软工教 材 数据结构（ C语言）授课内容 第六章 树和二叉树 课 时 2 教学目的 明白树、森林的定义；把握二叉树的定义、性质、储备结与要求 构；把握二叉树的遍历、树和森林的储备,哈夫曼树的应用重点 ：二叉树相关操作重点、难点难点： 二叉树的三种遍历投影、争论、板书课型电脑理论教学方法名师归纳总结 教学过程任务二、二叉 树（续）设计复习上一次的内容, 然后提问同学, 接着从上一次内容进入今日新的课程,（包括讲授让课程内容的完整性学
13、问、演示满二叉树：假如深度为k 的二叉树,有 2 k-1 个结点就称为满二叉树；内容及案完全二叉树：假如深度为k 的二叉树,有 2 k-1 个结点就称为满二叉树；对其中的结点的编号：根的号为1,从上到下,从左到右每个结点依次加1 为其例、提问及编号且一一对应,称之为完全二叉树；同学演示内下面是两个关于完全二叉树的性质：性质 4 ：具有 n 个结点的完全二叉树的深度为：trunclog2 n+1. truncx 为容）取整函数；第 9 页,共 31 页- - - - - - -精选学习资料 - - - - - - - - - 名师精编 优秀教案对完全二叉树的结点编号：从上到下,每一层从左到右性质
14、 5：在完全二叉树中编号为 i 的结点1）如有左孩子,就左孩编号为 2i 2）如有右孩子,就右孩子结点编号为 2i+1 3）如有双亲,就双亲结点编号为 trunci/2 三二叉树存贮结构1、二叉树的次序结构满二叉树或完全二叉树的次序结构：用一组连续的内存单元,按编号次序依教 学 过 程 设 计 续表 次储备完全二叉树的元素 .例如,用一维数组 bt 存放一棵完全二叉树,将标号为 i 的结点的数据元素存放在重量bti-1 中；储备位置隐含了树中的关系,树中的关系是通过完全二叉树的性质实现的；例如,bt5（i=6的双亲结点标号是 k=trunci/2=3, 双亲结点所对应的数组重量btk-1=bt
15、2 非完全二叉树的次序结构：按完全二叉树的形式补齐二叉树所缺少的那些结点,对二叉树结点编号,将二叉树原有的结点按编号储备到内存单元“相应”的位置上；但这种方式对于畸形二叉树,铺张较大空间；2、 二叉链表二叉链表中每个结点包含三个域：数据域、左指针域、右指针域；图见课件Struct node int data; struct node *lch,*rch; ; 注：在含有 n 个结点的二叉链表中有用到这些空的链域3、三叉链表n+1 个空链域,这在线索二叉树中将利三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指 针域 Struct node int data; struct nod
16、e *lch,*rch,*parent; ; 见课件和笔记名师归纳总结 - - - - - - -第 10 页,共 31 页精选学习资料 - - - - - - - - - 复习摸索题案例分析：名师精编优秀教案作业例：给一个二叉树画这棵树的次序储备和二叉链表的储备形式,另给一个次序的储备形式来画出这棵二叉树上机任务参考文献课后记 本章主要介绍完全二叉树和满二叉树的定义,仍有它的两个性质；然后（或归纳小介绍二叉树的储备形式：次序,二叉链表,三叉链表的形式结）名师归纳总结 - - - - - - -第 11 页,共 31 页精选学习资料 - - - - - - - - - 名师精编 优秀教案安徽新
17、华电脑专修学院课堂教学教案（电脑应用课使用）课程名称 数据结构 教学对象 新华软工教 材 数据结构（ C语言）授课内容 第六章 树和二叉树 课 时 2 教学目的 明白树、森林的定义；把握二叉树的定义、性质、储备结与要求 构；把握二叉树的遍历、树和森林的储备,哈夫曼树的应用重点 ：二叉树相关操作重点、难点难点： 二叉树的三种遍历投影、争论、板书课型电脑理论教学方法教学过程 任务三、二叉树的遍历设计（包括讲授 学问、演示 内容及案 例、提问及 同学演示内 容）复习上一次的内容, 然后提问同学, 接着从上一次内容进入今日新的课程,让课程内容的完整性一、二叉树的遍历方法遍历：按某种搜寻路径拜访二叉树的
18、每个结点,而且每个结点仅被拜访一 次；拜访：含义很广,可以是对结点的各种处理,如修改结点数据、输出结点 数据；遍历是各种数据结构最基本的操作,很多其他的操作可以在遍历基础上 实现；二叉树由根、左子树、右子树三部分组成二叉树的遍历可以分解为：拜访根,遍历左子树和遍历右子树名师归纳总结 - - - - - - -第 12 页,共 31 页精选学习资料 - - - - - - - - - 名师精编 优秀教案令： L：遍历左子树 T：拜访根结点 R：遍历右子树 有六种遍历方法：T L R,L T R,L R T,T R L,R T L,R L T 先序遍历（ T L R ）如二叉树非空（1）拜访根结点
19、；（2）先序遍历左子树；（3）先序遍历右子树 ；例：先序遍历右图所示的二叉树（1）拜访根结点 A 教 学（2）先序遍历左子树：即按 T L R 的次序遍历左子树（3）先序遍历右子树：即按 T L R 的次序遍历右子树中序遍历（ L T R ）如二叉树非空过（1）中序遍历左子树L T R 的次序遍历左子树程（2）拜访根结点设（3）中序遍历右子树计例：中序遍历右图所示的二叉树续表 （1）中序遍历左子树：即按（2）拜访根结点 A （3）中序遍历右子树：即按后序遍历（ L R T ）如二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）拜访根结点例：后序遍历右图所示的二叉树（1）后序遍历左子树：即
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 2022 数据结构 教案 第六
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内