二叉树的性质总结_完全二叉树的性质
二叉树的性质总结由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“完全二叉树的性质”。
一、二叉树的性质
性质
1、二叉树的第i层上至多有2 i-1（i 1）个结点。用数学归纳法证明
推广：k叉树(或度为k的树)的第i层上至多有k i-1（i 1）个结点
性质
2、度为h的二叉树中至多含有2h-1个结点。
21-1 + 2 2-1+……+ 2 h-1 = 2 h-1
推广：深度为h的k叉树(或度为k的树)中至多含有(k h-1)/(k-1)个结点
k1-1 + k 2-1+……+ k h-1 =(k h-1)/(k-1)
性质
3、若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1
证明：设：有n0个叶子结点，有n1个度为1的结点，有n2个度为2的结点，则二叉树中结点总数为：n=n0+n1+ n2(1)
设分支的总数为m,则：m= n1+2 n2(2)
因为n=m+1（3）
所以： n0+n1+ n2 = n1+2 n2 +1
整理得：n0= n2+1
推广: 度为k的树有n1个度为1的结点，n2个度为2的结点，nk个度为k的结点则n0为:
i=1 k(i-1)ni+
1性质3推广的证明于性质3的证明
设：有n0个叶子结点，有n1个度为1的结点，n2个度为2的结点，nk个度为k的结点则结点总数为：n=n0+n1+ n2 +……+nk(1)
设分支的总数为m,则：m= n1+2 n2+……+knk
因为n=m+1（3）
所以：n0+n1+ n2 +……+nk = n1+2 n2+……+knk +1
整理得：n0= 0n1+1n2+……+(k-1)nk+1
性质
4、具有n个结点的完全二叉树，其深度为㏒2n+1
证明：设n个结点的完全二叉树的深度为k，根据性质2可知，k-1层满二叉树的结点总数为： 2k-1-1
k层满二叉树的结点总数为： 2k-1
显然有：
2k-1-1
取对数有：k-1 log2n
因为k是整数，所以k-1 = log2n，k= ㏒2n+1
结论成立。
推广: 具有n个结点的完全k叉树，其深度为 logk(k-1)n +1
设n个结点的完全k叉树的深度为h，根据性质2推广可知，h-1层满k叉树的结点总数为：(k h-1-1)/(k-1)
h层满二叉树的结点总数为：(k h-1)/(k-1)
显然有：
(k h-1-1)/(k-1)
k h-1-1
k h-1 (k-1)n
取对数有：h-1 logk(k-1)n
因为h是整数，所以h-1 = logk(k-1)n ，h= logk(k-1)n +1
性质
5、设完全二叉树共有n个结点。如果从根结点开始，按层序(每一层从左到右)用自然数1，2，3……,n给结点进行编号，则对于编号为k(k=1,2,……n)的结点有以下结论：
(1)若k=1,则该结点为根结点，它没有双亲结点；若k>1,则该结点的双亲结点编号为 [k/2 ]。
(2)若2k
(3)若2k+1
推广:一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：
1）各层的结点的数目是多少？
2）编号为n的结点的双亲结点（若存在）的编号是多少？
3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？
4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 答:
h-1(1)k(h为层数)
h-1（2）因为该树每层上均有K个结点，从根开始编号为1，则结点i的从右向左数第２个
孩子的结点编号为ki。设n 为结点i的子女，则关系式(i-1)k+2
(3)结点n(n>1)的前一结点编号为n-1（其最右边子女编号是(n-1)*k+1），故结点 n的第 i个孩子的编号是(n-1)*k+1+i。
(4)根据以上分析，结点n有右兄弟的条件是，它不是双亲的从右数的第一子女，即(n-1)%k!=0，其右兄弟编号是n+1。
二：满二叉树：
一棵深度为k且有2k-1个结点的二叉树
特点：每一层上都含有最大结点数。叶子结点在同一层次上；无度为1的结点
具有n个结点的满二叉树则
叶子结点的个数为：（n+1)/2
度为2的结点的个数为：（n-1)/2
三、无度为1的结点
1: 具有n个结点的无度为1的结点的二叉树，求叶子结点的个数
n1=0
n=n1+n2+n0=n0+n2+0
n=2n0-1
n0=（n+1）/2n2=（n-1）/2
2:若已知叶子结点个数n0求总的结点的个数n
N=n0+n2=2n0-1
四、完全二叉树：深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的编号从1至n的结点一一对应
特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。
叶子结点在最后两层上，度为1的结点的个数最多为1
1:具有n个结点的完全二叉树，求叶子结点的个数
n是偶数：
则n1=1
n=n1+n2+n0=n0+n2+1
n=2n0
n0=n/2n2=n/2-1
n是奇数：
则n1=0
n=n1+n2+n0=n0+n2+0
n=2n0-1
n0=（n+1）/2n2=（n-1）/2
2:若已知完全二叉树叶子结点个数：求总的结点的个数
n=n0+n1+n2
n1=1 或n1=0n2=n0-1
n最大为2n0,最小为2n0-1
3:若已知完全二叉树第k层上具有n个叶子结点，求最多的结点个数及最少的结点个数最多的结点个数：共有k+1层
前k层共有2k-1个结点
k+1层: 第k+1层结点数最多为第k层的非叶子结点数乘以2；第k层的结点数为2k-1，叶子结点数为n, 非叶子结点数为(2k-1-n)，所以第k+1层结点数最多为2(2k-1-n)个结点,所以最多结点数为2k-1+ 2(2k-1-n)
最少的结点个数：共有k层 前k-1层具有2k-1-1个结点，k层有n个共有2k-1-1+n
