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