作者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