81

对于二叉树:无需考虑树节点值,我只对具有“N”个节点的不同树拓扑感兴趣。

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

4

11 回答 11

86
  1. 二叉树的总数为 =输入图片描述![在此处输入图片描述

  2. 对 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. 选择 1 作为根,左子树不能插入任何元素。n-1 个元素将被插入到右子树上。
  2. 选择 2 作为根,可以在左侧子树中插入1 个元素。n-2 个元素可以插入到右子树上。
  3. 选择 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 回答
10

Eric Lippert 最近有一个非常深入的系列博客文章:“每棵二叉树”和“每棵树”(之后还有一些)。

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

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

于 2010-06-15T03:56:47.800 回答
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 回答