对于二叉树:无需考虑树节点值,我只对具有“N”个节点的不同树拓扑感兴趣。
对于二叉搜索树:我们必须考虑树节点值。
二叉树的总数为 =
对 i 求和得出具有 n 个节点的二叉搜索树的总数。
基本情况是 t(0) = 1 和 t(1) = 1,即有一个空的 BST,并且有一个带有一个节点的 BST。
因此,通常您可以使用上述公式计算二叉搜索树的总数。我在谷歌面试中被问到一个关于这个公式的问题。问题是有多少个二叉搜索树可能有 6 个顶点。所以答案是 t(6) = 132
我想我给了你一些想法……
二叉树的数量可以使用加泰罗尼亚数来计算。
二叉搜索树的数量可以看作是一种递归解决方案。即二叉搜索树的数量=(左二叉搜索子树的数量)*(右二叉搜索子树的数量)*(选择根的方式)
在 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 种方法可以制作具有 1 个节点的 BST。
我推荐我的同事尼克·帕兰特(Nick Parlante)写的这篇文章(从他还在斯坦福大学的时候开始)。结构不同的二叉树的计数(问题 12)有一个简单的递归解决方案(封闭形式最终是 @codeka 的答案已经提到的加泰罗尼亚公式)。
我不确定结构不同的二叉搜索树(简称 BST)的数量与“普通”二叉树的数量有何不同——除了,如果“考虑树节点值”是指每个节点可能是例如任何与 BST 条件兼容的数字,则不同(但并非所有结构上不同!-)BST 的数量是无限的。我怀疑你的意思,所以,请用一个例子澄清你的意思!
如果没有。节点数为 N 则。
BST 的不同数量=Catalan(N)
结构不同的二叉树的不同数量是 = Catalan(N)
不同的二叉树数为=N!*Catalan(N)
具有 n 个节点的不同二叉树:
(1/(n+1))*(2nCn)
其中C =组合例如。
n=6,
possible binary trees=(1/7)*(12C6)=132
(2n)!/n!*(n+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
对于未标记的节点,正确答案应该是2nCn/(n+1),如果节点已标记,则为 (2nCn)*n!/(n+1)。
二叉树:
不需要考虑值,我们需要看结构。
由 (2 power n) - n 给出
例如:对于三个节点,它是 (2 power 3) -3 = 8-3 = 5 个不同的结构
二叉搜索树:
我们甚至需要考虑节点值。我们称之为加泰罗尼亚数
由 2n C n / n+1 给出
具有 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.