对于二叉树,假设有n个节点,我可以构造多少个不同的结构？

Question

考虑具有n个节点的二叉树.有多少种不同的二叉树结构？

我尝试过类似的东西:

n   number of different structure:

1        1
2        4
3        16

对于n> 1,4(n-1)也是如此; 1 = n == 1？

Answer 1

可以使用n个节点形成的不同二叉树的数量由第n个加泰罗尼亚数给出.

number of nodes (n)   binary trees C(n)  
1                     1  
2                     2  
3                     5  
4                     14

看到:

Answer 2

Adrian Toman之前的回答是正确的,当节点的值不重要时,只考虑树的结构(参考相同的维基百科链接).

当节点值也很重要时,计算也不同.加泰罗尼亚数字为您提供树的不同可能结构的数量.现在,您可以在每个结构(排列)中排列节点.因此,节点值很重要的n个节点的不同树的总数由公式给出 -

加泰罗尼亚语编号*n!

nodes (n)    trees C(n) * n!
1            1
2            4 (= 2 * 2)
3            30 (= 5 * 6)
4            336 (= 14 * 24)