[課業] 王致強的資料結構-二元樹

[aaaa0000 (孩子氣滴我)]

因為是函授的關係，所以沒有辦法找到老師幫忙解答

有些書的疑惑，想請問一下，希望有會的人可以幫我

1、若有200個節點的二元樹其高度至少為何？

    我用公式[logn]+1<=d

    高度不是應該至少為8嗎？可是答案是7，為什麼呢？？？

2、高度h，度數為d的樹，最多可以包含多少個空指標？

   答案是d的h次方

   為什麼呢？？


希望有人能幫忙，非常感激^^

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.236.120
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1421336236.A.272.html
推 Sunofgod: 第一題看有無定義第0階高度是0或1 如果第0階高度是0答案
→ Sunofgod: 是7 如果第0階高度是1答案則是8
→ rexkinkikids: Binary Tree 不是7次方就能超過兩百了嗎@@?
→ rexkinkikids: 128+64+32+16+8+4+2+1>200  這其實不用公式
→ Sunofgod: 第二題整個題目只有這樣嗎?
→ rexkinkikids: 第二題的話，其實自己畫圖出來就知道了
推 ianwuzack: 第一題的公式應該是log(n+1)再取高斯吧?
推 gunhello: 根據第一題，可知道根節點高度為0，所以第二題的高度h也
→ gunhello: 是有h+1層，因為最多空指標是在完滿樹的狀態，所以就是
→ gunhello: d的h次方，有些書會寫最後一層為d的(h-1)次方，完全看
→ gunhello: 節點的定義，這種題目必須先說明根節點的定義。祝福您。
推 gunhello: 原POST的公式，適用在根節點高度定義為1的時候使用。y
推 gunhello: ian大的公式和原post的公式有異曲同工之妙。
推 gunhello: 推re大不用公式的說法，的確能夠理解且長期記憶。
→ aaaa0000: 謝謝以上大大的說明，很清楚^^