考試

王致強的資料結構-二元樹 - 考試

Steve avatarSteve · 2015-01-15

Table of Contents

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

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

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

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

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

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

答案是d的h次方

為什麼呢？？


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

--
考試

All Comments

Yuri avatarYuri2015-01-19
第一題看有無定義第0階高度是0或1 如果第0階高度是0答案
Joseph avatarJoseph2015-01-22
是7 如果第0階高度是1答案則是8
Agnes avatarAgnes2015-01-26
Binary Tree 不是7次方就能超過兩百了嗎@@?
Megan avatarMegan2015-01-27
128+64+32+16+8+4+2+1>200 這其實不用公式
Kristin avatarKristin2015-01-29
第二題整個題目只有這樣嗎?
Queena avatarQueena2015-01-30
第二題的話，其實自己畫圖出來就知道了
Hedy avatarHedy2015-01-31
第一題的公式應該是log(n+1)再取高斯吧?
Dorothy avatarDorothy2015-02-01
根據第一題，可知道根節點高度為0，所以第二題的高度h也
Audriana avatarAudriana2015-02-04
是有h+1層，因為最多空指標是在完滿樹的狀態，所以就是
Catherine avatarCatherine2015-02-05
d的h次方，有些書會寫最後一層為d的(h-1)次方，完全看
節點的定義，這種題目必須先說明根節點的定義。祝福您。
Christine avatarChristine2015-02-06
原POST的公式，適用在根節點高度定義為1的時候使用。y
Sierra Rose avatarSierra Rose2015-02-06
ian大的公式和原post的公式有異曲同工之妙。
Jack avatarJack2015-02-10
推re大不用公式的說法，的確能夠理解且長期記憶。
Ingrid avatarIngrid2015-02-12
謝謝以上大大的說明，很清楚^^