第2节二叉树及其基本性质.ppt
《第2节二叉树及其基本性质.ppt》由会员分享,可在线阅读,更多相关《第2节二叉树及其基本性质.ppt(12页珍藏版)》请在三一文库上搜索。
1、第五章 树和二叉树,5.2 二叉树及其基本性质,一、二叉树的定义 二叉树是n(n=0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为左子树和右子树的,互不相交的 二叉树构成。,5.2 二叉树及其基本性质,(一)二叉树的特点,每个结点至多有二棵子树(即不存在度大于2的结点); 二叉树的子树有左、右之分,且其次序不能任意颠倒。,A,(二)二叉树的五种基本形态,1.空二叉树,2.只有根结点的二叉树,3.右子树为空,4.左子树为空,5.左、右子树均非空,5.2 二叉树及其基本性质,二、二叉树的基本特性,性质 1 : 在二叉树的第 i 层上至多有2i-1 个结点。 (i1),证明:用
2、归纳法证明之 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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 及其 基本 性质
链接地址:https://www.31doc.com/p-3425348.html