※ 引述《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://webptt.com/m.aspx?n=bbs/CSSE/M.1409249952.A.55E.html