2.5.2-二叉树及其基本性质ppt课件

.,2基本数据结构及其运算,2.1数据结构的基本概念2.2线性表及其顺序存储结构2.3线性链表及其运算2.4数组2.5树与二叉树2.6图,.,2.5树与二叉树,2.5.1树的基本概念2.5.2二叉树及其基本性质2.5.3二叉树的遍历2.5.4二叉树的存储结构2.5.5穿线二叉树2.5.6表达式的线性化,.,1.什么是二叉树2.二叉树的基本性质3.满二叉树与完全二叉树,2.5.2二叉树及其基本性质,.,1.什么是二叉树(BinaryTree),(1)非空二叉树只有一个根结点；(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。,p116,.,补充定义,二叉树是n(n0)个结点的有限集,它或者是空集(n=0),或者由一个根结点及两棵不相交的分别称为这个根的左子树和右子树的二叉树组成,.,二叉树的五种基本形态,(a),(b),(c),(d),(e),.,二叉树的度为2二叉树是无序树二叉树是有序树,思考:树与二叉树有何区别?,二叉树,.,二叉树和树是两种不同的数据结构,补充,两棵不同的二叉树,.,补充习题:分别画出具有3个结点的树和3个结点的二叉树的所有不同形态,树,二叉树,无序树,.,2.二叉树的基本性质,证明:数学归纳法,性质1:在二叉树的第k层上,最多有2k-1(k1)个结点。,21-1,22-1,23-1,24-1,.,性质2:深度为m的二叉树最多有2m-1个结点,21-1+22-1+2m-1=2m-1,21-1,22-1,23-1,24-1,.,性质3:在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个,n0:度为0的结点个数(叶子结点)n1:度为1的结点个数n2:度为2的结点个数,n0+n1+n2,结点总数,n0=n2+1,=射出分支总数+根结点,=进入分支总数+根结点,=,n1+2n2,+1,.,课堂练习,1.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数为_,11,.,性质4:具有n个结点的二叉树，其深度至少为log2n1其中log2n表示取log2n的整数部分,证明:反证法,假设mlog2n1,因为m为整数,所以mlog2nlog2n,结点总数,mlog2n1,.,例:具有8个结点的二叉树，其深度至少为log281=4,.,3.满二叉树与完全二叉树,(1)满二叉树:除了最后一层外,每一层上的所有结点都有两个子结点,.,第k层上的结点数:2k-1,深度为m的满二叉树,共有结点:2m-1,(c)深度为4的满二叉树,.,(2)完全二叉树:除了最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点,(a)深度为3的完全二叉树,.,b.深度为4的完全二叉树,.,深度为3的满二叉树,深度为3的完全二叉树,1,2,3,4,5,6,7,1,2,3,4,5,.,补充习题,一棵高度为h的完全二叉树至少有_个结点,A.2h-1,B.2h-1-1,C.2h-1,D.2h,C,.,补充习题,一棵高度为h的完全二叉树至多有_个结点,A.2h-1,B.2h-1-1,C.2h-1,D.2h,A,.,性质5:具有n个结点的完全二叉树的深度m=log2n1,深度为m的完全二叉树的前m-1层是深度为m-1的满二叉树前m-1层的结点总数为2m-1-1因为深度为m,所以第m层结点数不为0,则2m-1-1n2m-12m-1n2mm-1log2nmm-1=log2n,.,性质6:设完全二叉树共有n个结点如果从根结点开始，按层序(每一层从左到右)用自然数1，2，n给结点进行编号，则对于编号为k(k=1,2,n)的结点有以下结论:,(1)若k=1,则该结点是根结点,无父结点若k1,则该结点的父结点编号为INT(k/2),如何确定一个结点的父结点,.,(2)若2kn,则编号为k的结点的左子结点编号为2k；否则该结点无左子结点(显然也没有右子结点),如何确定一个结点的左