二叉樹高度

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。