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

看板Examination作者 (孩子氣滴我)時間11年前 (2015/01/15 23:37), 編輯推噓6(6推 0噓 9→)
留言15則, 5人參與, 最新討論串1/1
因為是函授的關係，所以沒有辦法找到老師幫忙解答 有些書的疑惑，想請問一下，希望有會的人可以幫我 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
推
01/16 00:33, , 1F
第一題看有無定義第0階高度是0或1 如果第0階高度是0答案
01/16 00:33, 1F
→
01/16 00:34, , 2F
是7 如果第0階高度是1答案則是8
01/16 00:34, 2F
→
01/16 00:34, , 3F
Binary Tree 不是7次方就能超過兩百了嗎@@?
01/16 00:34, 3F
→
01/16 00:35, , 4F
128+64+32+16+8+4+2+1>200 這其實不用公式
01/16 00:35, 4F
→
01/16 00:36, , 5F
第二題整個題目只有這樣嗎?
01/16 00:36, 5F
→
01/16 00:37, , 6F
第二題的話，其實自己畫圖出來就知道了
01/16 00:37, 6F
推
01/16 00:44, , 7F
第一題的公式應該是log(n+1)再取高斯吧?
01/16 00:44, 7F
推
01/16 08:06, , 8F
根據第一題，可知道根節點高度為0，所以第二題的高度h也
01/16 08:06, 8F
→
01/16 08:07, , 9F
是有h+1層，因為最多空指標是在完滿樹的狀態，所以就是
01/16 08:07, 9F
→
01/16 08:09, , 10F
d的h次方，有些書會寫最後一層為d的(h-1)次方，完全看
01/16 08:09, 10F
→
01/16 08:09, , 11F
節點的定義，這種題目必須先說明根節點的定義。祝福您。
01/16 08:09, 11F
推
01/16 08:12, , 12F
原POST的公式，適用在根節點高度定義為1的時候使用。y
01/16 08:12, 12F
推
01/16 08:19, , 13F
ian大的公式和原post的公式有異曲同工之妙。
01/16 08:19, 13F
推
01/16 08:51, , 14F
推re大不用公式的說法，的確能夠理解且長期記憶。
01/16 08:51, 14F
→
01/16 09:50, , 15F
謝謝以上大大的說明，很清楚^^
01/16 09:50, 15F
‣ 更多 aaaa0000 的文章
文章代碼(AID): #1Kjzwi9o (Examination)