使用"N"个节点,可以使用多少个不同的二进制和二进制搜索树？

Question

对于二叉树:没有必要考虑树节点值,我只对具有'N'节点的不同树拓扑感兴趣.

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

Answer 1

基本情况是t(0)= 1且t(1)= 1,即有一个空BST并且有一个BST具有一个节点. 在此输入图像描述

因此,通常您可以使用上面的公式计算二进制搜索树的总数.我在Google采访中被问到有关此公式的问题.问题是6个顶点可能有多少二元搜索树.所以答案是t(6)= 132

我想我给了你一些想法......

注意,1和2实际上是表达相同公式的不同方式,而不是不同数量的公式,如果不清楚的话. (6认同)
@Black_Rider - 我尝试了上面的公式来计算数量。100 个唯一节点的可能树。但它正在失败。我用DP来解决这个问题。您可以在[此处](https://github.com/dineshappavoo/ctgi/blob/master/src/com/ctgi/google/problems/MaximumPossibleWaysOfBST.java)找到代码。答案是错误的。预期答案是 25666077，但实际输出是 7159379471982673992。你能帮我解决这个问题吗？ (2认同)

Answer 2

我推荐这位同事Nick Parlante的文章(当时他还在斯坦福大学时).结构上不同的二叉树的数量(问题12)有一个简单的递归解决方案(以封闭的形式最终成为加泰罗尼亚公式,@ codeka的答案已经提到过).

我不确定结构上不同的二叉搜索树(简称BST)的数量与"普通"二叉树的数量有何不同- 除非通过"考虑树节点值"表示每个节点可能是例如任何与BST条件兼容的数字,那么不同(但不是所有结构上不同的! - )BST的数量是无限的.我怀疑你的意思是,所以,请澄清一下,你就用一个例子的意思!

Answer 3

可以使用加泰罗尼亚数来计算二叉树的数量.

二叉搜索树的数量可以看作是递归解决方案.即,二进制搜索树的数量=(左二叉搜索子树的数量)*(右二叉搜索子树的数量)*(选择根的方式)

在BST中,只有元素之间的相对排序很重要.因此,在没有任何一般性损失的情况下,我们可以假设树中的不同元素是1,2,3,4,....,n.另外,对于n个元素,将bST的数量表示为f(n).

现在我们有多种情况来选择根.

......同样,对于第i个元素作为根,i-1元素可以在左边,ni在右边.

这些子树本身就是BST,因此,我们可以将公式概括为:

f(n)= f(0)f(n-1)+ f(1)f(n-2)+ .......... + f(n-1)f(0)

基本情况,f(0)= 1,因为正好有1种方法可以生成具有0个节点的BST.f(1)= 1,因为有一种方法可以生成一个带有1个节点的BST.

最终公式

Answer 4

如果没有.节点是N然后.

不同数量的BST =加泰罗尼亚语(N)
不同数量的结构不同的二元树是=加泰罗尼亚语(N)

不同数量的二叉树是= N!*加泰罗尼亚语(N)

Answer 5

埃里克·利珀特(Eric Lippert)最近有一篇关于此事的非常深入的博客文章系列:" 每个二进制树都有 "和" 每棵树都有 "(之后还有更多).

在回答你的具体问题时,他说:

具有n个节点的二叉树的数量由加泰罗尼亚数给出,其具有许多有趣的属性.第n个加泰罗尼亚数由公式(2n)确定!/(n + 1)!n !,它呈指数增长.

Answer 6

(2n)!/n!*(n+1)!

Answer 7

具有n个节点的不同二叉树:

(1/(n+1))*(2nCn)

其中C =组合例如.

n=6,
possible binary trees=(1/7)*(12C6)=132