[理工] 資料結構 二元樹高度

[redspeed (RED)]

題目：

若樹的 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) 比較好
→ hibiscus520: 因為root level=0. log200取上限＝h+1 , h=7

了解，謝謝h大
※ 編輯: redspeed (114.42.114.39), 03/06/2017 15:57:09
推 mloop: 是取下限才對吧 我是都記取下限啦
推 yupog2003: 做法同h大
推 mloop: 呃呃 如果你要用取上限再減1 要先把點數加1
推 alan23273850: 也可利用補滿的方式，補到2^n - 1，以這題來說比200
→ alan23273850: 再多一點就是255，是8次方，但拿小樹來觀察會發現
→ alan23273850: height=power-1，所以8-1=7
→ alan23273850: 取上下限的題目通常陷阱就是在這種小細節，用小圖觀
→ alan23273850: 察法會有還不錯的效果～
→ alan23273850: 這樣就不用記要取上限還是下限了