generate all distinct full binary trees with n leaves - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

generate all distinct full binary trees with n leaves

generate all distinct full binary trees with n leaves# JobHunting - 待字闺中

s*12012-09-04 07:09

1 楼

大家好
有道binary Tree 的题请教大家，generate all structurally distinct full binary
trees with n leaves， "full" means all internal (non-leaf) nodes have
exactly two children. For example, there are 5 distinct full binary trees
with 4 leaves each.
着重想问下如何用DP解决呢？
多谢多谢！

x*y2012-09-04 07:09

2 楼

Let F(n, k) to be # of different structures with n leaves and k leaves in
the lowest level. k must be even to be valid.
F(n, k) =
sum{ k/2 <= i <= n-k/2 and i is even } F(n-k/2, i) C(i, k/2)
with F(j, j) = 1 when j is power of 2
and F(j, j) is invalid if not.
For your example, it's F(4,4)+F(4,2)
F(4,4) =1
F(4,2) = F(3, 2) C(2, 1) = F(2,2)C(2,1)C(2,1) = 4
So totaly 5.

s*12012-09-04 07:09

3 楼

Thank you so much. Would you please walk me through the algorithm a little,
because the hardest part k/2 <= i <= n-k/2 I haven't figured out.
Thanks again.
In addition, if I want to print out all the trees in dotted parenthesized
form, recursion is a good way? Or iterator? I have no clue on that? Can you
please give me some hint?
Thanks again.

【在 x***y 的大作中提到】

: Let F(n, k) to be # of different structures with n leaves and k leaves in
: the lowest level. k must be even to be valid.
: F(n, k) =
: sum{ k/2 <= i <= n-k/2 and i is even } F(n-k/2, i) C(i, k/2)
: with F(j, j) = 1 when j is power of 2
: and F(j, j) is invalid if not.
: For your example, it's F(4,4)+F(4,2)
: F(4,4) =1
: F(4,2) = F(3, 2) C(2, 1) = F(2,2)C(2,1)C(2,1) = 4
: So totaly 5.

i*h2012-09-04 07:09

4 楼

F(n) = F(1)*F(n-1) + F(2)*F(n-2) + ... + F(k)*F(n-k) + ...

s*12012-09-04 07:09

5 楼

Thank you All.
Allow me to summarize the Dynamic Programming:
Let T(n) be the number of distinct full trees and n the parameter for the
number of leaves
So T(n) = T(n-1)*T(1)+T(n-2)*T(2)+...+T(2)*T(n-2)+T(1)*T(n-1)
and T(1)=1 T(2)=1
Thus, build up a table first, lookup the table if there is we want then use
it, if not update the table for the future use.