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

看板Grad-ProbAsk作者redspeed (RED)時間7年前 (2017/03/06 15:08)推噓5(5推 0噓 6→)

留言11則, 4人參與討論串1/1

題目：若樹的 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

03/06 15:47, , 1^F

03/06 15:47, 1^F

→

hibiscus520

03/06 15:48, , 2^F

03/06 15:48, 2^F

了解，謝謝h大 ※ 編輯: redspeed (114.42.114.39), 03/06/2017 15:57:09

推

mloop

03/06 22:27, , 3^F