当前位置: 动力学知识库 > 问答 > 编程问答 >

algorithm - Is there link between the number of possible binary trees as a function of the tree's height?

问题描述:

Dealing with balanced and unbalanced binary trees.

height = 0, possible trees = 1 (nothing)

height = 1, possible trees = 1 (leaf)

height = 2, possible trees = 3

I'm looking at the Catalan function but it has not lead me anywhere beneficial, mostly because I think it might be counting trees less than height h. For example, if height it 2, it will count height 1 too (and maybe height 0) I believe.

网友答案:

You appear to be looking for integer sequence A001699, "Number of binary trees of height n". One possible algorithm to generate them being:

a(n+1) = 2*a(n)*(a(0)+...+a(n-1))+a(n)^2

Unfortunately, there doesn't seem to be a closed-form version. Each formula is itself recursive, or uses A003095, which is also recursive.

分享给朋友:
您可能感兴趣的文章:
随机阅读: