二叉树计算公式和例题

1.完全二叉树，只有度为0和度为2的节点

设总节点个数为N, 度为i的节点个数为Ni

则完全二叉树： N = N0 + N2

2.度和边的关系，由完全二叉树可得：

N - 1 = 2 * N2
即：N = 2 * N2 + 1
3.节点总数N： N = N0 + N1 + N2

度和边的关系： N - 1 = 0 * N0 + 1 * N1 + 2 * N2

例：设根结点的深度为1，则一个拥有n个结点的二叉树的深度一定在（ ）区间内
A.[logn + 1，n]
B.[logn，n]
C.[logn + 1，n - 1]
D.[logn + 1，n + 1]

解析：

最大深度： 此树为单边树，则深度为n

最小深度： 此树为完全二叉树， 如果是完全二叉树，假设高度为h, 

     则前h-1层为满二叉树，故n满足： 

     2^(h - 1) - 1 < n <= 2^h - 1

     即：

     2^(h - 1)< n + 1 <= 2^h

     两边取对数得：

     h - 1 < log(n + 1) <= h

     故：

     log(n + 1) <= h < log(n + 1) + 1

     log(n + 1) <= h < log(2(n + 1)) //对数性质log(ab) = log(a) + log(b)

和题目选项比对： 只有A，B可选， 但是B选项得下界 log(n)是小于h得下界log(n + 1),只有A选项的区间符合。 A选项得下界： logn + 1 = log(2n)