如果节点数为"N"，那么可能有多少个不同的二进制和二进制搜索树? [英] With ' N ' no of nodes, how many different Binary and Binary Search Trees possible?

问题描述

对于二叉树:无需考虑树节点值，我只对具有'N'个节点的不同树拓扑感兴趣.

For Binary trees: There's no need to consider tree node values, I am only interested in different tree topologies with 'N' nodes.

对于二叉搜索树:我们必须考虑树节点值.

For Binary Search Tree: We have to consider tree node values.

推荐答案

我推荐这篇文章由我的同事尼克·帕兰特(Nick Parlante)所写(从他还在斯坦福大学的那一刻起).在结构上不同的二叉树(问题12)的数量具有一个简单的递归解决方案(以封闭形式最终是加泰罗尼亚语公式，@ codeka的答案已经提到过).

I recommend this article by my colleague Nick Parlante (from back when he was still at Stanford). The count of structurally different binary trees (problem 12) has a simple recursive solution (which in closed form ends up being the Catalan formula which @codeka's answer already mentioned).

我不确定结构不同的二元搜索树(简称BST)的数量与普通"二叉树的数量有何不同-除非通过考虑树节点"值"是指每个节点可能是任何与BST条件兼容的数字，那么不同(但并非所有在结构上不同！)BST的数量是无限的.我怀疑您的意思，所以，请举例说明您的意思.

I'm not sure how the number of structurally different binary search trees (BSTs for short) would differ from that of "plain" binary trees -- except that, if by "consider tree node values" you mean that each node may be e.g. any number compatible with the BST condition, then the number of different (but not all structurally different!-) BSTs is infinite. I doubt you mean that, so, please clarify what you do mean with an example!

这篇关于如果节点数为"N"，那么可能有多少个不同的二进制和二进制搜索树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！