计算具有i个节点的二叉树的数量

-3

让bi为具有i个节点的二叉树的数量。计算b10。计算具有i个节点的二叉树的数量

这是我遇到的问题。

我已经能够拿出这些至今：

B0=1 
B1=1 
B2=2 
B3=5 
B4=12

它很快变得有点太多，因为我变得更大。

任何人都可以想到一个更好的方法来计算比只是绘制出树和数它们吗？

来源

2011-12-31 spider

这功课？ – soulcheck 2011-12-31 01:36:38

提示：加泰罗尼亚号码。 – 2011-12-31 01:37:05

[有'N'个节点，可能有多少个不同的二进制和二进制搜索树？]的可能重复（http://stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many -different-binary-and-binary-search-trees-possible）和[可以用N个键创建的二元搜索树的可能数目由第N个加泰罗尼亚数给出。为什么呢？（http://stackoverflow.com/questions/1352776/the-possible-number-of-binary-search-trees-that-can-be-created-with-n-keys-is-gi） – 2011-12-31 14:18:07

我在OEIS中输入了你的答案，并得出了一些结果。

有希望的结果是A000669-具有n片叶子的系列减少的种植树的数量。提供了以下示例：a（4）= 5，其中包含以下系列减少的种植树：（oooo），（oo（oo）），（o（ooo）），（o（o（oo））），（OO）（OO））。也就是说，我们的树不一定种植。

但是，经过一些工作后，我必须通知您，您对B4的价值是不正确的 - 正确的答案是14.然后答案很清楚：the Catalan numbers。加泰罗尼亚语数字包括了一些奇怪而多样的东西，包括你在这里展示的问题（通过Wolfram）。这里值得注意的是加泰罗尼亚数字标识（8） - 定义加泰罗尼亚数字的重现。这个总和可以被认为是决定节点左边的节点数量（其余的将会在右边）。

一个更简单的概念化方法是使用Dyck单词。让X表示“左括号”，Y表示“0”。（我正在使用树的列表表示 - 左侧的节点是元素左侧的列表，反之亦然;如果一个节点没有左侧或右侧列表，它就被认为是一个叶子）。我们会在适当的地方放入正确的括号。然后是我们对B3树如下：

（（（0）0）0）=> XXXYYY

（（0）0（0））=> XXYYXY

（0（0（ 0）））=> XYXYXY

（（0（0））0）=> XXYXYY

（0（（0）0））=> XYXXYY

维基百科，5 2 N-这种形式的长度单词是XXXYYY，XYXXYY，XYXYXY，XXYYXY和XXYXYY 。最后，封闭表格

Bn = (1/(n + 1)) * (2n choose n) = (2n!)/((n+1)!(n!))

来源

2011-12-31 02:25:00 kaosjester

计算具有i个节点的二叉树的数量

回答

相关问题