作者whiteshirts (MJIB)
站內Examination
標題[考題] 88年國安資料結構
時間Sat Apr 27 14:56:31 2013
高度為h且度數為d之樹，至多可包含多少節點? 至多可包含多少個空指標?
A:(王致強老師/資料結構)
(1) 1+d+...+d(h-1次方)=d(h次方)-1除以d-1
想法：這邊沒問題，用等比級數
(2) 當節點最多時，空指標數也多=d(h次方)
想法：不太清楚這邊的空指標是指?
如果是終端節點，那應該是d(h-1次方)，也不是d(h次方)
謝謝回覆了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.167.51.72
1F：推 asdd:終端節點的高度+1 你可以先用簡單的d=3的full tree 代入看看 04/27 15:24
2F：→ asdd:通常也是看你高度是多少開始算 不過看你(1)應該是從0開始 04/27 15:25
3F：→ whiteshirts:對了 這題從0開始 所以我帶入3階二元樹 樹葉是4 04/27 15:34
4F：→ whiteshirts:所以d的h次方 就是2的2次方 就沒錯 謝謝 04/27 15:34
5F：推 asdd:這裡的空指標是指終端節點的分支 因為它們沒有再指向其他節點 04/27 18:11
6F：推 smalldulan:怎麼我看w大你的敘述高度是從1開始阿... 04/27 22:10
7F：→ smalldulan:是我搞錯了嗎?請多多指點~ 04/27 22:10
8F：推 asdd:是1沒錯 這題簡單來說就是d^(h-1)(節點數) * d(分支) 04/27 23:00