data-structures - 如果您知道二叉树的节点数，如何找到二叉树的最小高度？

Question

设n为一棵二叉树的节点数，那么求出二叉树最小高度的泛函项是什么？

我认为它将是 n=floor(log2(n))+1。但是，我想，我错了。

Answer 1

看到记住这个概念就是

for height to be minimum you will have to give each level, the maximum no of nodes it can accomodate

所以对于一棵高度为h的树，树最多可以容纳的节点数=2^(h+1)-1，所以 n<=2^(h+1)-1
解决后你会得到
h>=log(n+1)base2 -1
现在要决定日志的地板或天花板，这样想

If my logn is coming 3.56.. then it means that till height 3 each level is fully consumed, last level is not completely filled. So as the definition of height says that it is the longest path from root to the leaf, so in height we will include that last level also.

因此 ceil 比 floor 更受欢迎。通过这种方法，您还可以找到 m-ary 树。