教师课时授课计划
教师姓名 刘荣胜 课程 数据结构 授课时数 3 累计课时_15
授课日期
班 次
课 题
树
教学目的
掌握树的基本概念;了解二叉树;熟练掌握二叉树的遍历;掌握树和森林;掌握堆和优先权队列;熟练掌握哈夫曼树和哈夫曼编码
重 点
二叉树的遍历;哈夫曼树和哈夫曼编码
难 点
二叉树的遍历;哈夫曼树和哈夫曼编码
教 具
教室
作 业
自用参考书
《数据结构(C语言)》曲健民,刘元红,郑陶然
教学过程
一、复习
?
二、引入
三、学习任务
四、课堂讲解
1)树的基本概;2)二叉树及其遍历;3)树和森林;4)堆和优先权队列;5)哈夫曼树和哈夫曼编码
五、重点内容分析
二叉树的遍历;哈夫曼树和哈夫曼编码
六、难点内容分析
二叉树的遍历;哈夫曼树和哈夫曼编码
七、课堂
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
课后小结:
树
1.引入
树形结构是元素之间有着分层关系的结构,它类似于自然界中的树。这是一类很重要的非线性数据结构。 一方面,计算机应用中,常常出现嵌套的数据,树结构提供了对该类数据的自然
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示。另一方面利用树结构,我们可以有效地解决一些算法问题。
2.学习任务
掌握树的基本概念;
了解二叉树;
熟练掌握二叉树的遍历;
掌握树和森林;
掌握堆和优先权队列;
熟练掌握哈夫曼树和哈夫曼编码
3.课堂讲解
1)树的基本概念
定义5.1 树是包括n个结点的有限非空集合D,R是D中元素的序偶的集合,R满足以下特性:
(1)有且仅有一个结点rD,不存在任何结点vD,vr,使得
R,称r为树的根 ;
(2)除根r以外的所有结点uD,都有且仅有一个结点vD,vu,使得R。
这样定义的树也称有根树,简称树。
定义5.2 树是包括n个结点的有限非空集合T,其中,一个特定的结点r称为根,其余结点 T-{r}划分成m(m0)个互不相交的子集T1,T2,,Tm,其中,每个子集都是树,被称为树根r的子树。
树中元素常称为结点 。根和它的子树根(如果存在)之间形成一条边 。如果从某个结点沿着树中的边可到达另一个结点,则称这两个结点间存在一条路径 。
若一个结点有子树,那么该结点称为子树根的双亲,子树的根是该结点的孩子。有相同双亲的结点互为兄弟。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点路径上的所有结点都是该结点的祖先 。
一个结点拥有的子树数称为该结点的度。度为零的结点称为叶子,其余结点称为分支结点。树中结点的最大的度称为树的度。
树是层次结构的,规定根结点的层次为1,其结点的层次等于其双亲结点的层次加1。树中结点的最大层次称为该树的高度。
如果树中结点的各子树之间的次序是不重要的,可以交换位置,这样的树称为无序树。也就是我们通常所说的树。如果将树中结点的各棵子树看成是从左到右有次序的,则称该树为有序树。从左到右,可分别称这些子树为第一子树,第二子树等等。
森林是树的集合。果园或称有序森林是有序树的有序集合。
2)二叉树
定义5.3 二叉树是结点的有限集合,该集合或者为空集,或者是由一个根和两棵互不相交的,称为该根的左子树和右子树的二叉树组成。
二叉树的五种基本形态
二叉树与树的区别
二叉树可以为空二叉树
二叉树结点的子树分为左、右子树
3)二叉树的性质
性质5.1 二叉树的第i(i1)层上至多有2i-1 个结点。
性质5.2 高度为h的二叉树上至多有2h –1个结点。
性质5.3 包含n个元素的二叉树的高度至少为log2 (n+1)
性质5.4 任意一棵二叉树中,若叶结点的个数为n0,度为2的结点的个数为n2,则必有n0=n2+1。
定义5.5 一棵二叉树中,只有最下面两层结点的度可以小于2,并且最下一层的叶结点集中在靠左的若干位置上,这样的二叉树称为完全二叉树 。
定义5.6 扩充二叉树 也称2-树,扩充二叉树中除叶子结点外,其余结点都必须有两个孩子。
性质5.5 具有n个结点的完全二叉树的高度为log2 (n+1)。
性质5.6 假定对一棵有n个结点的完全二叉树中的结点,按从上到下、从左到右的顺序,从0到n-1编号,设树中某个结点的序号为i,0i0,则该结点的双亲的序号为
(i-1)/2;
(3)若2i+1
本文档为【数据结构第5讲】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。