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

Question

考虑具有n 个节点的二叉树。有多少种可能的二叉树结构？

我试过类似的东西：

n   number of different structure:

1        1
2        4
3        16

n > 1 的 4(n-1) 也是如此；1 代表 n == 1？

score 5 · Accepted Answer

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

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

看：

score 5 · Accepted Answer

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

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

第 n 个加泰罗尼亚数字 * n!

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

2 回答 2