二叉树高度

Question

我需要一个通用公式来计算二叉树的最小高度和二叉树的最大高度.(不是二叉搜索树)

Answer 1

首先,计算机科学如何计算树的高度与离散数学中的高度确定方式(图论)可能存在一些差异,这可能是由于任何一个节点(或顶点)存在数据,而在数学方面,它是一种纯粹的理论方法.

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

在离散数学中,树被分类为m-ary树,因此bin-ary树是2-ary树.同样在任何给定高度,最多可以有2 ^ h = L(叶子).这一点很重要,因为它确认根位于零高度,因此2 ^ 0 = 1叶... 1顶点...根.

因此,给定n个顶点,树的高度由公式n = 2 ^(h + 1)-1给出

既然你正在寻找h,你必须得到公式两边的log2 n = 2 ^(h + 1) - 1

对于完整的二叉树,最大高度为log2(n + 1)= log2(2 ^(h + 1))这等于上限(log2(n + 1) - 1)= h

对于非完整二叉树,最大高度=(n - 1)因此,如果您有n个顶点,必须减去根以获得最大高度,因为上面的上述公式(2 ^ h = L)

对于最小高度,从上述规则推断.

Answer 2

如果有 N 个元素，二叉树的最小高度将为 log2(N)+1。

对于满二叉树，最大高度为 N/2。

对于非满二叉树，最大高度为 N。

Answer 3

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 4

想想树的结构会如何改变。

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

因为这听起来像是家庭作业，所以我就把它留在那里。