几种特殊形式的二叉树.ppt

  1. 1、本文档共52页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
几种特殊形式的二叉树 满二叉树 定义: 6.2.2 二叉树的性质 (3+2) 求二叉树的深度 void BiTreeDepth(BiTree T, int level, int depth) {// T指向二叉树的根,level 为 T 所指结点所在层次,其初值为1,depth 为当前求得的最大层次,其初值为0   if(T){    if(leveldepth) depth=level;    BiTreeDepth(T-Lchild, level+1, depth);    BiTreeDepth(T-Rchild, level+1, depth);   }  } 在二叉树上查询某个结点 void locate(BiTree T,ElemType x,BiTree p) {  // 若二叉树 T 中存在和 x 相同的元素,则 p 指向该结点,否则 p 的值不变,p 的初值为 NULL  if (T)  { if (T-data==x) p=T;   locate(T-lchild, x, p);   locate(T-rchild, x, p);  } } 如果一棵具有n个结点的深度为k的二叉树,它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应,这棵二叉树称为完全二叉树。 可以根据公式进行推导,假设n0是度为0的结点总数(即叶子结点数),n1是度为1的结点总数,n2是度为2的结点总数,由二叉树的性质可知:n0=n2+1,则n= n0+n1+n2(其中n为完全二叉树的结点总数),由上述公式把n2消去得:n= 2n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n0=(n+1)/2或n0=n/2,合并成一个公式:n0=?(n+1)/2 ?,就可根据完全二叉树的结点总数计算出叶子结点数。 * 6.2.1 二叉树的定义 定义:是n(n≥0)个结点的有限集合,由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构: 一对二(1:2) 基本特征: ① 每个结点最多只有两棵子树(不存在度大于2的结点); ② 左子树和右子树次序不能颠倒。 问:具有3个结点的二叉树可能有几种不同形态? 有5种 基本形态: * 二叉树的抽象数据类型定义(见教材P121-122) ADT BinaryTree{ 数据对象D: 数据关系R: 基本操作 P: }ADT BinaryTree D是具有相同特性的数据元素的集合。 若D=Φ,则R= Φ ; 若D≠Φ,则R= {H};存在二元关系: ① root 唯一 //关于根的说明 ② Dj∩Dk= Φ //关于子树不相交的说明 ③ …… //关于数据元素的说明 ④ …… //关于左子树和右子树的说明 //至少有20个,如返回某结点的左孩子,或中序遍历,等等 特点:每一层上的结点数都是最大结点数 完全二叉树 定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树 特点 叶子结点只可能在层次最大的两层上出现 对任一结点,若其右分支下子孙的最大层次为L,则其左分支下子孙的最大层次必为L 或L+1 A B C K D E H I L F G J 1 2 3 4 5 6 7 8 9 10 11 12 A B C K D E H I L M F G J N O 1 2 3 4 5 6 7 8 9 10 11 13 14 15 A B C D E J K 1 2 3 4 5 6 7 A B C D E G 1 2 3 4 5 6 * 讨论1:第i层的结点数最多是多少? (利用二进制性质可轻松求出) 性质1: 在二叉树的第i层上至多有2i-1个结点(i0)。 性质2: 深度为k的二叉树至多有2k-1个结点(k0)。 再提问:第i层上至少有 个结点? 1 讨论2:深度为k的二叉树,最多有多少个结点? (利用二进制性质可轻松求出) 2i-1个 2k-1个 * 6.2.2 二叉树的性质 (3+2) 性质1: 在二叉树的第i层上至多有2i-1个结点(i0) 性质2: 深度为k的二叉树至多有2k-1个结点(k0) 性质3: 对于任何一棵二叉树,若2度的结点数有n2个,则叶子数(n0)必定为n2+1 (即n0=n2+1) 性质4: 具有n个结点的完全二叉树的深度必为?log2n?+1 性质5: 对完全二叉树,

文档评论(0)

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

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

1亿VIP精品文档

相关文档