严版教材义4.ppt

  1. 1、本文档共163页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
严版教材义4

第三章 栈和队列 3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.4 行编辑程序 3.2.5 迷宫求解 3.2.5 表达式求值 第四章 串 4.1 串类型的定义 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示 第五章 数组和广义表 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构 第六章 树和二叉树 6.1 树的定义和基本概念 6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 第六章 树和二叉树 6.1 树的定义和基本概念 6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.2 二叉树 二叉树在树结构的应用中起着非常重要的作用,因为对二叉树的许多操作算法简单,而任何树都可以与二叉树 相互转换,这样就解决了树的 存储结构及其运算中存在的复杂性。 6.2.1 二叉树的定义 定义:二叉树是由n(n=0)个结点的有限集合构成,此集合或者为空集,或者由一个根结点及两棵互不相交的左右子树组成,并且左右子树都是二叉树。 这也是一个递归定义。二叉树可以是空集合,根可以有空的左子树或空的右子树。二查树不是树的特殊情况,它们是两个概念。 二叉树结点的子树要区分左子树和右子树,即使只有一棵子树也要进行区分,说明它是左子树,还是右子树。这是二叉树与树的最主要的差别。图6.8列出二差树的5种基本形态,图6.8(C) 和图6.8(d)是不同的两棵二叉树。 6.2.2 二叉树的性质 二叉树具有下列重要性质: 性质1: 在二叉树的第i层上至多有2i-1个结点(i=1)。 采用归纳法证明此性质。 当i=1时,只有一个根结点,2i-1=20 =1,命题成立。 现在假定多所有的j,1=ji,命题成立,即第j层上至多有2j-2个结点,那么可以证明j=i时命题也成立。由归纳假设可知,第i-1层上至多有2i-2个结点。 由于二叉树每个结点的度最大为2,故在第i层上最大结点数为第i-1层上最大结点数的二倍, 即2×2i-2=2i-1。 命题得到证明。 性质2:深度为k的二叉树至多有2k-1个结点(k=1). 深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和,由性质1得到每层上的最大结点数,: EkI=1(第i层上的最大结点数)= EkI=12i-1=2k –1 性质3: 对任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。 设二叉树中度为1的结点数为n1,二叉树中总结点数为N,因为二叉树中所有结点均小于或等于2,所以有:N=n0+n1+n2 (6-1) 再看二叉树中的分支数,除根结点外,其余结点都有一个进入分支,设B为二叉树中的分支总数, 则有:N=B+1。 如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应, 完全二叉树的特点是: (1)所有的叶结点都出现在第k层或k-1层。 (2)错任一结点,如果其右子树的最大层次为1,则其左子树的最大层次为1或l+1。 性质4:具有n个结点的完全二叉树的深度为[log2n]+1。 符号【x】表示不大于x的最大整数。 假设此二叉树的深度为k,则根据性质2及完全二叉树的定义得到:2k-1-1n=2k-1 或

文档评论(0)

1444168621 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档