二叉树性质的性质及证明整理

大家好，又见面了，我是你们的朋友全栈君。

——整理于2020.4.29

二叉树的性质及证明

性质1：在二叉树的第i层上至多有2(i-1)个结点 (i>=1)

证明：数学归纳法 (1) i=1时只有一个根节点。显然 2(i-1)= 20= 1是对的 (2) 假设对所有的 j, 1<= j <i, 命题成立，即第j层上至多有2(j-1)个结点 (3) 由归纳假设可得: 第i-1层上至多有2(i-2)个结点。由于二叉树的每个结点的度数至多为2,所以在第i层上的结点数最多为i-1层上的两倍，即2*2(i-2)=2(i-1)，即得出第i层上结点数至多为2(i-1)

性质2：深度为k的二叉树至多有2(k-1)个结点（k>=1）

证明：等比数列求和（ Sn=a1(1-qn) / 1-q ) 由性质一( 在二叉树的第i层上至多有2(i-1)个结点(i>=1) )可知，深度为k的二叉树的最大结点数为：

在这里插入图片描述

性质3：对任何一棵二叉树T, 如果其终端结点(叶子结点)数为 n0, 度数为2的结点数为 n2, 则n0=n2+1

证明： 设n1为二叉树T中度数为1的结点数,n为二叉树结点总数，则有: n=n0+n1+n2 ① 又因为二叉树中除根节点外每一个结点都对应一个分支,则分支数B=n-1, 由于这些分支是由度为一和二的结点射出的，所以有B=n1+2*n2,所以有： n=n1+2*n2+1 ② 联立①②可得 n0=n2+1

完全二叉树的两个重要性质

性质4： 具有n个结点的完全二叉树的深度为 ⌊log2n⌋+1 注：⌊x⌋表示不大于x的最大整数

证明：假设完全二叉树的深度为k,则根据性质2和完全二叉树的定义有 2(k-1) -1 < n <= 2k -1 由于n为整数，上式可变为: 2(k-1) <= n < 2k 两边同时取对数得： k-1 <= log2n < k 因k为整数，即得k= ⌊log2n⌋+1

性质5: 如果对一颗有n个结点得完全二叉树(其深度为⌊log2n⌋ +1)得结点按层序编号(从第1层到第⌊log2n⌋ +1层，每层从左到右),对任一结点 i (1<= i <= n)有: 1.如果 i =1,则结点 i 是二叉树得根,无双亲；如果 i>1,则其双亲是结点⌊i/2⌋ 2.如果 2i > n,则结点 i 无左孩子(结点 i 为叶子结点); 否则其左孩子是结点 2i 3.如果 2i+1 > n,则结点 i 无右孩子; 否则其右孩子是结点2i+1

证明：（暂时简单说明，有空再补）

参考大话数据结构/北京大学出版社/程杰

/图片来自大话数据结构/北京大学出版社

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/138222.html原文链接：https://javaforall.cn