推 expiate : 你的二元樹是有限制在 complete還是節點數只要是 N 08/22 05:15
→ expiate : 都算？ 08/22 05:15
→ Ifault : 不用完整 傾斜也可以 08/22 05:34
→ Ifault : 不平衡也可以 08/22 05:34
推 hwanger : 如果不區別這個n個節點 令f(n)為有n個節點的二元樹 08/22 09:04
→ hwanger : 則有下列遞歸式 f(0)=f(1)=1 08/22 09:06
→ hwanger : f(n)={sum over k from 0 to n-1}f(k)*f(n-1-k) 08/22 09:07
推 hwanger : 上面是"令f(n)為有n個節點的二元樹的個數" 08/22 09:11
→ hwanger : 會有這個遞歸式 是因為二元樹是有分左右的 然後用 08/22 09:13
→ hwanger : 二元樹的遞迴定義得到的 08/22 09:14
→ hwanger : 同樣地 如果這個n個節點皆相異 08/22 09:14
→ hwanger : 令g(n)為有n個相異節點的二元樹的個數 則 08/22 09:17
→ hwanger : g(0)=g(1)=1 08/22 09:18
→ hwanger : g(n)=n*(ΣC(n-1,k)f(k)*f(n-1-k)) where k runs 08/22 09:20
→ hwanger : over 1,2,...,n-1 08/22 09:21
推 hwanger : 我看不太懂"答案是c 2n取n ? n+1" 這一行 不過你已 08/22 09:23
→ hwanger : 經有答案的話 用數學歸納法就可以做了 08/22 09:25
→ Ifault : 感謝你 我在想想 08/22 09:34
推 hwanger : 上面g(n)打錯 應該是 08/22 09:34
→ hwanger : g(n)=n*(ΣC(n-1,k)g(k)*g(n-1-k)) 不過也不用這麼 08/22 09:35
→ hwanger : 麻煩 就是g(n)=n!*f(n) 08/22 09:35
推 hwanger : 分類應該是"離散" 不過好像沒有這個選項 XDDD 08/22 09:47
推 hwanger : Ok 離散離我太久遠了 f(n)就是Catalan number 08/22 10:08
→ hwanger : 所以可以用generating function去證 08/22 10:09
→ hwanger : f(n)=C(2n,n)/(n+1) 冏 08/22 10:11
→ Ifault : 哈 謝謝你 沒發現/打成? 08/22 12:26