对于二叉树：不需要考虑树节点的值，我只关注拥有 'N' 个节点的不同树形结构。
对于二叉搜索树：我们必须考虑树节点的值。
11个回答
90
二叉树的总数为=
对 i 求和可得 n 个节点的二叉搜索树的总数。
基本情况是 t(0) = 1 和 t(1) = 1，即有一个空的 BST 和一个带有一个节点的 BST。
因此，一般来说，您可以使用上述公式计算二叉搜索树的总数。我在谷歌面试中被问到了与该公式相关的问题。问题是有多少个具有 6 个顶点的二叉搜索树。 回答是 t(6) = 132。
我想我给了你一些想法...
- Black_Rider
3
7请注意，1和2实际上是表达同一公式的不同方式，而不是针对不同量的公式，以防不清楚。 - Todd O'Bryan
2@Black_Rider - 我尝试使用上述公式计算100个唯一节点的可能树的数量。但是它失败了。我使用DP来解决这个问题。您可以在此处找到代码。答案是错误的。期望的答案是25666077，但实际输出是7159379471982673992。您能帮我吗？ - Dany
如果有些树具有相同的键怎么办？例如对于树1，1，2，2，不可能将相似的键压缩到一个顶点中。 - Evgeny
47
二叉树的数量可以使用卡特兰数进行计算。
二叉搜索树的数量可以看作是一个递归解决方案。 即，二叉搜索子树的数量=（左侧二叉搜索子树的数量）*（右侧二叉搜索子树的数量）*（选择根的方式）。
在BST中，只有元素之间的相对顺序重要。因此，不失一般性，我们可以假设树中的不同元素为1、2、3、4、....、n。并且，让BST的数量表示为f(n)对于n个元素。
现在我们有多种情况来选择根节点。
二叉搜索树的数量可以看作是一个递归解决方案。 即，二叉搜索子树的数量=（左侧二叉搜索子树的数量）*（右侧二叉搜索子树的数量）*（选择根的方式）。
在BST中，只有元素之间的相对顺序重要。因此，不失一般性，我们可以假设树中的不同元素为1、2、3、4、....、n。并且，让BST的数量表示为f(n)对于n个元素。
现在我们有多种情况来选择根节点。
- 选择1作为根节点，左子树不可插入元素，右子树可以插入n-1个元素。
- 选择2作为根节点，左子树可以插入1个元素，右子树可以插入n-2个元素。
- 选择3作为根节点，左子树可以插入2个元素，右子树可以插入n-3个元素。
...... 同理，对于第i个元素作为根节点，左子树可以插入i-1个元素，右子树可以插入n-i个元素。
这些子树本身就是BST，因此我们可以总结出公式：
f(n) = f(0)f(n-1) + f(1)f(n-2) + .......... + f(n-1)f(0)
基本情况， f(0) = 1，因为用0个节点构建一棵BST有且仅有1种方法。 f(1) = 1，因为用1个节点构建一棵BST有且仅有1种方法。
- chirag1992m
44
我推荐我的同事Nick Parlante（他之前在斯坦福大学）的这篇文章。其中，问题12中二叉树结构不同的计数有一个简单的递归解决方案（闭式形式最终会成为卡特兰公式，正如@codeka的答案中已经提到的那样）。
我不确定结构不同的二叉搜索树（BSTs缩写）的数量与“普通”二叉树有什么不同 - 除非您通过“考虑树节点值”指的是每个节点可能是任何与BST条件兼容的数字，那么不同的（但不是所有结构不同！）BSTs的数量是无限的。我认为您不是这个意思，请举一个例子澄清一下！
- Alex Martelli
3
1这里提供的解决方案 http://cslibrary.stanford.edu/110/BinaryTrees.html # 12 与由卡特兰数计算得出的解决方案不匹配。也就是说，countTrees(4) 应该是5而不是14，对吗？但它返回了14。（这是序列1、1、2、5、14、42、132） - Joyce
1countTrees(4) 是该系列的第5个元素，因为该系列从0开始，而它返回的结果是14。 - Erric
我推荐印度理工学院Ropar的这个关于Catalan数的图形教程 https://www.youtube.com/watch?v=BLG9E_PoXXc&feature=emb_logo。 - angshuk nag
15
如果给定节点数为N，则：
不同的BST数量=Catalan（N）
不同的结构不同的二叉树数量=Catalan（N）
不同的二叉树数量=N！*Catalan（N）
- Atiq
11
Eric Lippert最近在他的博客上发布了一系列非常深入的文章:"Every Binary Tree There Is"和"Every Tree There Is"(以及之后的一些文章)。
针对你特定的问题，他说：
n个节点的二叉树数量由Catalan数给出，它们有许多有趣的性质。第n个Catalan数的确定公式为(2n)! / (n+1)!n!，而这个公式是呈指数级增长的。
- Dean Harding
1
第n个卡特兰数公式
(2n)! / (n+1)!n!呈指数增长。我们如何编写一个算法来解决n > 11的情况？ - GigaWatts7
具有n个节点的不同二叉树：
(1/(n+1))*(2nCn)
其中C表示组合，例如:
n=6,
possible binary trees=(1/7)*(12C6)=132
- Sarang
5
(2n)!/n!*(n+1)!
- karthik
2
Total number of possible Binary Search Trees with n different keys =
2nCn / (n + 1)For n = 1 --> 1 Binary Search Tree is possible. For n = 2 --> 2 Binary Search Trees are possible. For n = 3 --> 5 Binary Search Trees are possible. For n = 4 --> 14 Binary Search Trees are possible. For n = 5 --> 42 Binary Search Trees are possible. For n = 6 --> 132 Binary Search Trees are possible.```And Total number of possible Binary Trees with n different keys =
(2nCn / (n + 1)) * n!For n = 4 --> 336 Binary Search Trees are possible.
- WolfBlunt
1
The number of possible binary search tree with n nodes (elements,items) is
=(2n C n) / (n+1) = ( factorial (2n) / factorial (n) * factorial (2n - n) ) / ( n + 1 )
where 'n' is number of nodes (elements,items )
Example :
for
n=1 BST=1,
n=2 BST 2,
n=3 BST=5,
n=4 BST=14 etc
- Vinayak
1
如果节点没有标签，则正确答案应为2nCn/(n+1)，如果节点有标签，则为(2nCn)*n!/(n+1)。
- Turing101
1
你能解释一下第一个公式中的2nCn和(n+1)吗？ - Bill Chen
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接