binary-tree - 二叉树高度

Question

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

Answer 1

首先，计算机科学如何计算
树的高度与离散数学中确定高度的方式的关系
(图论)，这可能是由于任一节点上都存在数据
(或顶点)，而在数学中，这是一种纯粹的理论方法。

因此，也许最好的办法是弄清楚您需要哪一个。

在离散数学中，树被分类为m元树，因此
二叉树是二叉树。同样在任何给定的高度，
最多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)

对于最小高度，请根据上述规则进行推断。