对于二叉树，假设有n个节点，我可以构造多少种不同的结构？
考虑一个具有 n 个节点的二叉树。有多少种不同的可能的二叉树结构？
我尝试过类似的操作：
n number of different structure:
1 1
2 4
3 16
n > 1 的 4(n-1) 也是如此； 1 代表 n == 1？
Consider a binary tree with n nodes. How many different possible binary trees structures are there?
I tried something like:
n number of different structure:
1 1
2 4
3 16
so is that 4(n-1) for n >1 ; 1 for n == 1?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
使用 n 个节点可以形成的不同二叉树的数量由第 n 个加泰罗尼亚数给出。
请参阅：
http://en.wikipedia.org/wiki/Binary_tree
http://en.wikipedia.org/wiki/Catalan_number
The number of different binary trees that can be formed using n nodes is given by the nth Catalan number.
See:
http://en.wikipedia.org/wiki/Binary_tree
http://en.wikipedia.org/wiki/Catalan_number
当节点的值不重要，只考虑树的结构时，Adrian Toman 之前的回答是正确的（请参阅相同的维基百科链接）。
当节点值也很重要时，计算方式有所不同。加泰罗尼亚数给出了树的不同可能结构的数量。现在，您可以排列每个结构中的节点（排列）。因此，节点值很重要的 n 个节点的不同树的总数由以下公式给出 -
第 n 个加泰罗尼亚数 * n！
The previous answer by Adrian Toman is true when the value of the node is not important, only the structure of the tree is considered (Refer the same wikipedia link).
When the node value is also important, the calculation is different. The Catalan number gives you the number of different possible structures of the tree. Now, you can arrange the nodes in each of those structures (permutation). Hence total number of different trees for n nodes where value of node is important is given by the formula -
nth Catalan number * n!