华师本科生数据结构课件第6章二叉树和树.ppt
《华师本科生数据结构课件第6章二叉树和树.ppt》由会员分享,可在线阅读,更多相关《华师本科生数据结构课件第6章二叉树和树.ppt(185页珍藏版)》请在启牛文库网上搜索。
1、树型结构是一类重要的非线性结构。树型结构是结点之间有分支,并且具有层次关系的结构,它非常类似于自然界中的树。树结构在客观世界中是大量存在的。例如家谱、行政组织机构都可用树形象地表示。树结构在计算机领域中也有着广泛的应用,例如在编译程序中,用树结构来表示源程序的语法结构;在数据库系统中,可用树结构来组织信息;在分析算法的行为时,可用树结构来描述其执行过程等等。,华中师范大学,课前导学 6.1 二叉树 6.2 遍历二叉树和线索二叉树 6.3 树和森林 6.4 树的应用,第六章 二叉树和树,【学习目标】,领会树和二叉树的类型定义,理解树和二叉树的结构差别。熟记二叉树的主要特性,并掌握它们的证明熟练掌
2、握二叉树的各种遍历算法,并能灵活运用遍历算法实现二叉树的其它操作。理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。熟练掌握二叉树和树的各种存储结构及其建立的算法。学会编写实现树的各种操作的算法。了解最优树的特性,掌握建立最优树和赫夫曼编码的方法。,【重点和难点】,重点:二叉树和树的遍历及其应用 难点:编写实现二叉树和树的各种 操作的递归算法知识点树的类型定义二叉树的类型定义二叉树的存储表示二叉树的遍历以及其它操作的实现线索二叉树树和森林的存储表示树和森林的遍历以及其它操作的实现最优树和赫夫曼编码,【学习指南】,本章是整个课程的第三个学习重点,也是整个课程中的一大难点。在
3、本章的学习过程中主要应该学会如何根据二叉树和树的结构及其操作的递归定义编写递归算法。本章必须完成的算法设计题为:6.1,6.3,6.4,6.5,6.6,6.7,6.8,6.9,6.10,6.11,6.12,6.14,6.16,6.17,6.18,6.20,6.21,6.24,6.25,6.26,6.1 二叉树,二、二叉树的基本性质,一、二叉树的定义和基本术语,三、二叉树的存储结构,一、二叉树的定义和基本术语,1、二叉树的定义2、二叉树的基本术语3、二叉树的应用举例4、二叉树的基本操作,1、二叉树定义,二叉树T是n个结点的有限集合,其中n0,当n=0时,为空树,否则,其中有一个结点为根结点,其余
4、结点划分为两个互不相交的子集TL、TR,并且TL、TR分别构成叫作左、右子树的二叉树。,二叉树或为空树;或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,E,F,二叉树的五种基本形态:,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,二叉树的注意点,二叉树每个结点的孩子都有左右之分,每个结点都有左右两个子树。,三个节点的二叉树(五棵),每个结点最多只有两棵子树(不存在度大于2的结点);左子树和右子树次序不能颠倒(有序树)。,2、基本术语,结点(node)表示树中的元素,包括数据项及若干指向其子树的分
5、支结点的度(degree)结点拥有的子树数叶子(leaf)度为0的结点孩子(child)结点子树的根称为该结点的孩子双亲(parents)孩子结点的上层结点叫该结点的双亲深度树中结点的最大层次数结点的层次从根结点算起,根为第一层,它的孩子为第二层,,即根结点(没有前驱)即上层的那个结点(直接前驱)即下层结点的子树的根(直接后继)同一双亲下的同层结点(孩子之间互称兄弟)即双亲位于同一层的结点(但并非同一双亲)即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点,根双亲孩子兄弟堂兄弟祖先子孙,结点A的度:3结点B的度:2结点M的度:0,叶子:K,L,F,G,M,I,J,结点A的孩子:B,C
6、,D结点B的孩子:E,F,结点I的双亲:D结点L的双亲:E,结点B,C,D为兄弟结点K,L为兄弟,树的度:3,结点A的层次:1结点M的层次:4,树的深度:4,结点F,G为堂兄弟结点A是结点F,G的祖先,3、二叉树的应用举例,国际Morse码,变色力缺陷遗传图(隔代遗传),InitBiTree(,二叉树的基本操作,查 找 类,插 入 类,删 除 类,二、二叉树的基本性质,1、层与结点数2、深度与结点数3、叶子与结点数4、完全二叉树与深度5、完全二叉树与结点序号,1.一棵非空二叉树的第i 层最多有2i1个结点(i1)。,证明(采用归纳法)(1).当i=1时,结论显然正确。非空二叉树的第1层有且仅有
7、一个结点,即树的根结点.,(2).假设对于第j层(1ji1)结论也正确,即第j层最多有2j-1个结点.,(3).有定义可知,二叉树中每个结点最多只能有两个孩子结点。若第i1层的每个结点都有两棵非空子树,则第i层的结点数目达到最大.而第i1层最多有2i2个结点已由假设证明,于是,应有22i2=2i1,证毕.,讨论1:第i层的结点数至多是多少?(利用二进制性质可轻松求出),提问:第i层上至少有 个结点?,2.深度为h 的非空二叉树最多有2h-1个结点.,证明:,由性质1可知,若深度为h的二叉树的每一层的结点数目都达到各自所在层的最大值,则二叉树的结点总数一定达到最大。即有 20+21+22+2i-
8、1+2h-1=2h-1,证毕.,讨论2:深度为k的二叉树,至多有多少个结点?(利用二进制性质可轻松求出),提问:深度为k时至少有 个结点?,3.若非空二叉树有n0个叶结点,有n2个度为2的结点,则 n0=n2+1,证明:设该二叉树有n1个度为1的结点,结点总数为n,有 n=n0+n1+n2-(1),设二叉树的分支数目为B,有 B=n-1-(2),这些分支来自度于为1的结点与度度为2结点,即 B=n1+2n2-(3),联列关系(1),(2)与(3),可得到 n0=n2+1,证毕.,推论:n0=n2+2n3+3n4+(m-1)nm+1,讨论3:二叉树的叶子数和度为2的结点数之间有关系吗?,实际意义
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 本科生 数据结构 课件 二叉