1、二叉树的深层特性
性质1
在二叉树的第i层录多有2i-1上个结点。(i≧1)
第一层最多有21-1 = 1个结点
第二层最多有22-1 = 2个结点
第三层最多有23-1= 4个结点
.......
性质2
高度为k的二叉树最多有2k-1个结点(k≧0)
如果有一层,最多有1=21-1=1个结点
如果有两层,最多有1+2=22-1=3个结点
如果有三层,最多有1+2+4=23-1=7个结点
.......
性质3
对任何一棵二叉树,如果其叶结点有n0个,度为2的非叶结点有n2
个,则有n0= n2+1。
证明:假设二叉树中度1的结点有n1个且总结点为n个,则:
n=n0 + n1 + n2
假设二叉树中连接父结点与子结点间的边为e条,则:
e = n1 + 2n2 = n - 1
所以:
n0 = n2+1性质4
具有n个结点的完全二叉树的高度为⌊log2n⌋+1。 (⌊X⌋表示
不大于X的最大整数)
证明:假设这n个结点组成的完全二叉树高度为k 、则:
2k-1-1< n ≤ 2k - 1
因为n为整数,所以:
2k-1 ≤ n < 2k
取对数:
k-1 ≤ log2n < k
因为k为整数,所以:
k = ⌊log2n⌋ + 1
性质5 (这个只针对完全二叉树)
一棵有n个结点的完全二叉树(高度为⌊log2n⌋+1) ,按层次对
结点进行编号(从上到下,从左到右),对任意结点i有:
如果i = 1 , 则结点i是二叉树的根
如果i > 1 则其双亲结点力⌊i/2⌋
如果2i <= n , 则结点i的左孩子力2i
如果2i > n , 则结点i无左孩子
如果2i+1 <= n , 则结点i的右孩子力2i+l
如果2i+1 > n , 则结点i无右孩子
2、实战预告
To be continued…
思考:
如何实现二叉树的存储结构?
如何实现二叉树对应的 数据类型?