资源预览内容
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
第9页 / 共12页
第10页 / 共12页
亲,该文档总共12页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第五章 树和二叉树,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,证明: 设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n k 因为 k 只能是整数,所以, log2n取其整数部分 log2n 得: k =log2n + 1 。,5.2 二叉树及其基本性质,性质5: 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号,则对完全二叉树中任意一个编号为 i 的结点: (1) 若 i=1,则该结点是二叉树的根,无双亲,否则,编号为 i/2 的结点为其双亲结点; (2) 若 2in,则该结点无左孩子,否则,编号为 2i 的结点为其左孩子结点; (3) 若 2i+1n,则该 结点无右孩子结点, 否则,编号为2i+1 的 结点为其右孩子结点。,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号