二叉樹的高度範圍

我可以用數學方法證明二叉樹的可能高度爲：logN < =高度< = N-1（N是節點數）。但是，如何用一兩句話來解釋這個答案呢？二叉樹的高度範圍

2013-11-01 FlowerFire

什麼是Logn和n-1在高度方面的含義是什麼？ – progrenhard

@progenhard所以你的意思是我需要解釋爲什麼logN是最小的，爲什麼N-1是最大值？ – FlowerFire

那麼有一個節點的樹的高度爲0？那很奇怪。空樹的高度是多少？ –

考慮最小高度和最大高度發生時的兩種情況。

最低高度：當每個非葉結點具有正好兩個孩子

最大高度：當每個非葉結點具有正好一個孩子，即線性

2013-11-01 06:09:52 sam092

Upvote比使用數學證明更容易提供答案。謝謝。 – FlowerFire

@FlowerFire事實上，如果你畫一個簡單的圖來解釋，它可能會更容易。對於例如，以說明最大的情況。高度，你可以畫'1-2-3-4-5-6-7'這樣的東西來形象化一個具有線性結構的樹:) – sam092

正確。這將是退化的二叉樹，這是最糟糕的情況。 – FlowerFire

完全平衡的樹（非葉節點有2個孩子）的大小爲N = 2^n-1個節點，log2（N）= n個級別。

樹的退化情況（每個節點都有單個子節點）是一個列表，大小N有N個級別。

2013-11-01 06:23:00 ChuckCottrill

對於退化情況，就身高而言，應該是「高度= N -1」。但是，提高你的答案。 – FlowerFire

回答