Question

n个节点的平衡二叉树,最大高度和最小高度是多少

Answer 1

高度为log2(n+1)，seethepic

数据结构课本上有最大高度。

最小高度就是完全二叉树了。

设N是深度为h的平衡二叉树的最少结点数，对于 h >= 1，有 N = F(h + 2) - 1 成立，其中的F(n)为Fibonacci 数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

于是最大高度H为F(H + 2) - 1 <= n < F(H + 3) - 1

扩展资料：

若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点： 

当i=1时，该节点为根，它无双亲节点。

当i>1时，该节点的双亲节点的编号为i/2。

若2i≤n，则有编号为2的左叶子，否则没有左叶子。

若2+1≤n，则有编号为2i+1的右叶子，否则没有右叶子。

参考资料来源：百度百科-二叉树

Answer 2

数据结构课本上有最大高度。
最小高度就是完全二叉树了。高度为log
2
(n+1)，see
the
pic:

Answer 3

nh表示深度为h的平衡树
n0＝0，n1＝1，n2＝2
nh＝n(h－1)+n(h-2)+1
利用递推公式可以推得h
书上还有一个结论就是log2n