⼆叉树计算公式和例题
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)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。