二叉树高度

Question

我需要一个通用公式来计算二叉树的最小高度和二叉树的最大高度。 （不是二叉查找树）

Answer 1

想想如何改变树的结构。

例如，如果树完全不平衡，那么这是最糟糕的情况 - 每个节点只有一个孩子。在最好的情况下，树完成平衡，每个节点有两个孩子。

由于听起来像是功课，我会把它留在那里。

Answer 2

的最大高度为n和最小高度（即一个完美的二进制树）的（对数基座2（N + 1）） - 1

Answer 3

如果有N个元素，二进制的最小高度树将是log2（N）+1。

对于完整的二叉树，最大高度将为N/2。

对于非完全二叉树，最大高度为N.

Answer 4

首先可能会有一些差异，以计算机科学是如何计算的 高度一棵树的，与高度的方法是在离散确定数学 （图论），这可能是由于在任何一个节点（或顶点）存在数据，而在数学中，它是一种纯粹的理论方法。

所以，也许最好你澄清你需要哪一个。

在离散数学中，树被归类为m-ary树，所以bin-ary树是2元树。同样在任何给定的高度，最多可以有 2^h = L（叶）。这一点很重要，因为它确认了根在高度为零，因此2^0 = 1叶...... 1个顶点......根。

所以给定的n个顶点，树的高度由下式给出 N = 2 ^（H + 1） - 1

由于你正在寻找小时，你必须采取二者的log 2的 公式n = 2侧面^（H + 1） - 1

对于一个完整的二进制树时，最大高度为 的log 2（N + 1）= LOG 2（2 ^（H + 1）） 此等于上限（log2（n + 1） - 1）= h

对于非满二叉树，最大高度=（n - 1） 因此，如果您有n个顶点，由于上述公式（2^h = L），必须扣除根部以获得最大高度

对于最小高度，根据上述规则进行外插。

Answer 5

对于任何二叉树，最小高度为h = ceiling（log（n + 1）/ log（2）-1） 。

Answer 6

如果根最多可以有2（0,1,2）任何数量的叶片，则：

• 的最大高度为n-1个。当你的树只有一片树叶时就是这种情况。没有节点有多个分支。
• 最小高度为[log2（n）]其中[x]是x的整数部分。

为了获得最小高度，每个根必须有尽可能多的分支。在这种情况下，你会注意到，对于n = 1，height = 0;对于n = 2到n = 3，高度= 1;对于n = 4到n = 7，高度= 2;对于n = 8到n = 15，高度= 3等等

由此可以注意到，对于每个n，存在AP使得：

2^P < = N < 2 ^（P + 1）和p =高度，因此高度= [log2（n）]

Answer 7

N-节点数量。
H - 二叉树的高度。

完全二叉树：
然后，用H高度N将位于之间：

2^H <= N <= (2^(H+1) - 1) 

因此，解决这个不等式;我们得到：

H <= lg(N) and H >= (lg(N+1) - 1) 

因此，我们最终得到：

H = floor(lg(N)) = ceil((lg(N+1) - 1)) //as H is integer 

（LG：日志基地2）

二叉树（不一定完成）：

Max height = N; 

Min Height = floor(lg(N)) = ceil((lg(N+1) - 1)) 

二叉树完成时，我们获得最小高度。

Answer 8

With n-nodes可能的最大高度是floor(log(n)) = ceil (log(n+1))-1。

随着n-nodes可能的最小高度是n-1。