為什麼這篇二元樹高度計算鄉民發文收入到精華區：因為在二元樹高度計算這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者redspeed (RED)看板Grad-ProbAsk標題[理工] 資料結構 二元樹高度時間M...
題目：
若樹的 height 是由樹根到樹葉的最長路徑長度，
則含有200個節點的二元樹其高度至少為何?
(A) 200 (B) 7 (C) 8 (D) 9
正解：(B) 7
我的理解：
樹的 height 是由樹根到樹葉的最長路徑長度 → 樹的 level 應該為 0
我想這一題應該是要問完全二元樹的高度，
而完全二元樹得最多節點為(2^K)-1 (K為高度)
於是我套用公式，
(2^K)-1=200
(2^K)=201
算出K值取下限大約為8
但是答案是高度 7，所以我推論高度8，要在-1 (因為樹的 level 為 0)，
才會得到7，不知道這樣推論對不對，感覺有點怪怪的，
因此請求前輩的協助，先謝謝各位前輩的回答
--
╔══════════════════════════════════╗
║╔════════════════════════════════╗║
║║ 節電， ║║
║║ 才是最環保、最省錢的發電！ ║║
║╚════════════════════════════════╝║
╚══════════════════════════════════╝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.42.114.39
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1488784092.A.7F5.html
推 hibiscus520: 沒錯,但是公式用1+2+...+2^（h）=2^(h+1) 比較好 03/06 15:47
→ hibiscus520: 因為root level=0. log200取上限＝h+1 , h=7 03/06 15:48
了解，謝謝h大
※ 編輯: redspeed (114.42.114.39), 03/06/2017 15:57:09
推 mloop: 是取下限才對吧 我是都記取下限啦 03/06 22:27
推 yupog2003: 做法同h大 03/06 23:08
推 mloop: 呃呃 如果你要用取上限再減1 要先把點數加1 03/07 10:58
推 alan23273850: 也可利用補滿的方式，補到2^n - 1，以這題來說比200 03/09 23:01
→ alan23273850: 再多一點就是255，是8次方，但拿小樹來觀察會發現 03/09 23:01
→ alan23273850: height=power-1，所以8-1=7 03/09 23:01
→ alan23273850: 取上下限的題目通常陷阱就是在這種小細節，用小圖觀 03/09 23:03
→ alan23273850: 察法會有還不錯的效果～ 03/09 23:03
→ alan23273850: 這樣就不用記要取上限還是下限了 03/10 21:59