第2节-二叉树及其基本性质.ppt_第1页
第2节-二叉树及其基本性质.ppt_第2页
第2节-二叉树及其基本性质.ppt_第3页
第2节-二叉树及其基本性质.ppt_第4页
第2节-二叉树及其基本性质.ppt_第5页
免费预览已结束，剩余7页可下载查看

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第五章树和二叉树,5.2二叉树及其基本性质,一、二叉树的定义二叉树是n(n=0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的，互不相交的二叉树构成。,5.2二叉树及其基本性质,（一）二叉树的特点,每个结点至多有二棵子树(即不存在度大于2的结点)；二叉树的子树有左、右之分，且其次序不能任意颠倒。,A,（二）二叉树的五种基本形态,1.空二叉树,2.只有根结点的二叉树,3.右子树为空,4.左子树为空,5.左、右子树均非空,5.2二叉树及其基本性质,二、二叉树的基本特性,性质1：在二叉树的第i层上至多有2i-1个结点。(i1),证明：用归纳法证明之i=1时，只有一个根结点，2i-1=20=1是对的;假设对所有j(1ji)命题成立，即第j层上至多有2j-1个结点那么，第i-1层至多有2i-2个结点又二叉树每个结点的度至多为2第i层上最大结点数是第i-1层的2倍，即22i-2=2i-1故命题得证,5.2二叉树及其基本性质,性质2：深度为k的二叉树上至多含2k-1个结点（k1）。,证明：深度为k的二叉树是指二叉树共有k层。由性质1，可得深度为k的二叉树最大结点数是21-1+22-1+2k-1=2k-1,5.2二叉树及其基本性质,性质3：对任何一棵二叉树，度为0的叶子结点总是比度为2的结点多一个，则必存在关系式：n0=n2+1。,证明：n1为二叉树T中度为1的结点数因为：二叉树中所有结点的度均小于或等于2所以：其结点总数n=n0+n1+n2又二叉树中，除根结点外，其余结点都只有一个分支进入。设m为分支总数，则二叉树中总结点数又为：n=m+1又：分支由度为1和度为2的结点射出，m=n1+2n2于是，n=m+1=n1+2n2+1=n0+n1+n2所以：n0=n2+1,5.2二叉树及其基本性质,三、满二叉树与完全二叉树,第层上有2k-1个结点；深度为的满二叉树有2m-1个结点。,5.2二叉树及其基本性质,（一）满二叉树的定义除最后一层外，每一层上的所有结点都有两个子结点。特点：每一层上的结点数都是最大结点数,5.2二叉树及其基本性质,（二）完全二叉树的定义除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。特点：1.叶子结点只可能在层次最大的两层上出现;2.对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L或L+1。,（三）满二叉树与完全二叉树的性质,性质：具有n个结点的完全二叉树的深度为log2n+1,证明：设完全二叉
人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论