二叉树高度 [英] Binary Tree Height

问题描述

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

I need a general formula to calculate the minimum height of the binary tree and the maximum height of the binary tree. (not the binary search tree)

推荐答案

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

First there may be some difference as to how computer science calculates the height of a tree, versus the way height is determined in discrete mathematics (graph theory), this may be due to the existence of data at any one node (or vertice), while in mathematics, its a pure theory approach.

所以也许最好的办法是弄清楚您需要哪一个.

So maybe its best you clarify which one you need.

在离散数学中，树被分类为m元树，因此 二叉树是二叉树.同样在任何给定的高度， 最多2 ^ h = L(叶).注意这一点很重要，因为它确认了 根的高度为零，因此2 ^ 0 = 1叶... 1个顶点...根.

In discrete mathematics, trees are classified as m-ary trees, so a bin-ary tree is a 2-ary tree. Also at any given height, there can be at most 2^h = L (leaves). This is important to notice, since it confirms that the root is at height zero, hence 2^0 = 1 leaf...1 vertice...the root.

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

So given n vertices, the height of a tree is given by the formula n = 2^( h + 1 ) - 1

因为您要寻找h，所以必须取两边的log2 公式n = 2 ^(h + 1)-1

Since you are looking for h, you have to take the log2 of both sides of the formula n = 2^( h + 1 ) - 1

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

For a full binary tree, the max height is log2( n + 1 ) = log2( 2^( h + 1 ) ) this equals ceiling( log2( n + 1 ) - 1 ) = h

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

For a non-full binary tree, the max height = ( n - 1 ) therefore if you have n vertices, the root must be subtracted to get the max height, because of the previous formula above (2^h = L)

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

For min heights, extrapolate from the above rules.

这篇关于二叉树高度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！