对于二叉树：无需考虑树节点值，我只对具有“N”个节点的不同树拓扑感兴趣。
对于二叉搜索树：我们必须考虑树节点值。
问问题
178053 次
11 回答
86
二叉树的总数为 =
对 i 求和得出具有 n 个节点的二叉搜索树的总数。
基本情况是 t(0) = 1 和 t(1) = 1，即有一个空的 BST，并且有一个带有一个节点的 BST。
因此，通常您可以使用上述公式计算二叉搜索树的总数。我在谷歌面试中被问到一个关于这个公式的问题。问题是有多少个二叉搜索树可能有 6 个顶点。所以答案是 t(6) = 132
我想我给了你一些想法……
于 2012-09-21T13:57:23.847 回答
46
二叉树的数量可以使用加泰罗尼亚数来计算。
二叉搜索树的数量可以看作是一种递归解决方案。即二叉搜索树的数量=（左二叉搜索子树的数量）*（右二叉搜索子树的数量）*（选择根的方式）
在 BST 中，只有元素之间的相对顺序很重要。因此，在不失一般性的情况下，我们可以假设树中的不同元素是1, 2, 3, 4, ...., n。此外，对于 n 个元素，让 BST 的数量由f(n) 表示。
现在我们有多种选择根的情况。
- 选择 1 作为根，左子树不能插入任何元素。n-1 个元素将被插入到右子树上。
- 选择 2 作为根，可以在左侧子树中插入1 个元素。n-2 个元素可以插入到右子树上。
- 选择 3 作为根，可以在左侧子树中插入2 个元素。n-3 个元素可以插入到右子树上。
...... 同理，以第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 种方法可以制作具有 1 个节点的 BST。
于 2013-09-30T21:42:21.817 回答
42
我推荐我的同事尼克·帕兰特（Nick Parlante）写的这篇文章（从他还在斯坦福大学的时候开始）。结构不同的二叉树的计数（问题 12）有一个简单的递归解决方案（封闭形式最终是 @codeka 的答案已经提到的加泰罗尼亚公式）。
我不确定结构不同的二叉搜索树（简称 BST）的数量与“普通”二叉树的数量有何不同——除了，如果“考虑树节点值”是指每个节点可能是例如任何与 BST 条件兼容的数字，则不同（但并非所有结构上不同！-）BST 的数量是无限的。我怀疑你的意思，所以，请用一个例子澄清你的意思！
于 2010-06-15T04:02:45.317 回答
14
如果没有。节点数为 N 则。
BST 的不同数量=Catalan(N)
结构不同的二叉树的不同数量是 = Catalan(N)
不同的二叉树数为=N!*Catalan(N)
于 2013-10-20T11:55:14.933 回答
6
具有 n 个节点的不同二叉树：
(1/(n+1))*(2nCn)
其中C =组合例如。
n=6,
possible binary trees=(1/7)*(12C6)=132
于 2011-10-13T12:28:04.257 回答
5
(2n)!/n!*(n+1)!
于 2010-11-24T15:49:43.937 回答
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
于 2012-07-07T13:44:46.570 回答
1
对于未标记的节点，正确答案应该是2nCn/(n+1)，如果节点已标记，则为 (2nCn)*n!/(n+1)。
于 2018-08-22T13:02:09.640 回答
0
二叉树：
不需要考虑值，我们需要看结构。
由 (2 power n) - n 给出
例如：对于三个节点，它是 (2 power 3) -3 = 8-3 = 5 个不同的结构
二叉搜索树：
我们甚至需要考虑节点值。我们称之为加泰罗尼亚数
由 2n C n / n+1 给出
于 2014-08-18T17:45:56.347 回答
0
具有 n 个不同键的可能二叉搜索树的总数 =
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.```并且具有 n 个不同键的可能二叉树的总数 =
(2nCn / (n + 1)) * n!For n = 4 --> 336 Binary Search Trees are possible.
于 2021-04-28T10:01:03.570 回答