n个结点的二叉树的平均高度是多少?

来源：百度知道 编辑：UC知道 时间：2024/06/25 22:25:04
有n个结点的所有二叉树的平均高度是多少?
要求每个非叶子节点有两个孩子结点.可以用归纳法证明,有n个结点的正则二叉树,平均高度>log(n).

高度为h≥0的二叉树至少有h+1个结点；
高度不超过h(≥0)的二叉树至多有2h+1-1个结点；

含有n≥1个结点的二叉树的高度至多为n-1；
含有n≥1个结点的二叉树的高度至少为logn，因此其高度为Ω(logn)。

大于：《对＜（2的n次方）的对数＞取整》＋1
小于：n

大于：《对＜（2的n次方）的对数＞取整》＋1
小于：n