Re: [問題] 請問資料結構樹的終端節點
看板CSSE (電腦科學及軟體工程)作者CindyLinz (Cindy Wang)時間10年前 (2014/08/29 02:19)推噓2(2推 0噓 0→)留言2則, 2人參與討論串2/2 (看更多)
※ 引述《bbggorin (無心)》之銘言：
: 請教一個關於資料結構的問題
: 題目:假如有一個非空樹，其分支度為5，已知分支度為i的節點數有i個，其中 1 <= i <=5，
: 請問終端節點數總數是多少？
: 答案是==>41
: 請問是怎麼算出來的?
假設你已有一個終端節點數為 k 的樹,
現在對它加入一個分支度為 i 的節點在一個終端節點上,
它會吃掉一個終端結點, 然後再貢獻 i 個新的終端節點,
使得這個長大的樹終端節點數為 k + i - 1,
也就是每加一個分支度為 i 的點, 終端節點數就增加 i - 1,
而且跟節點加入的順序無關.
不失一般性, 我們把這個題目描述的樹的 root 前面再延伸一個 super root.
這個加上 super root 的樹, 其終端節點數和原本的樹應該是一樣的.
而這個新的樹的終端節點數應該是....
1 + (只有 super root 自己時, 終端節點數是 1)
1 * (1-1) +
2 * (2-1) +
3 * (3-1) +
4 * (4-1) +
5 * (5-1)
= 1 + 0 + 2 + 6 + 12 + 20
= 41
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.121.80.249
※ 文章網址: http://www.ptt.cc/bbs/CSSE/M.1409249952.A.55E.html
推
10/01 18:49, , 1F
10/01 18:49, 1F
推
01/13 10:27, , 2F
01/13 10:27, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
