用'N'节点，可以有多less个不同的二进制和二进制search树？

对于二叉树：没有必要考虑树节点的值，我只对有'N'个节点的不同树拓扑感兴趣。

二叉search树：我们必须考虑树节点值。

我推荐这篇由我的同事Nick Parlante撰写的文章 （当时他还在斯坦福大学）。 在结构上不同的二叉树（问题12）的计数有一个简单的recursion解决scheme（封闭的forms最终是@ codeka的答案已经提到的加泰罗尼亚公式）。

我不确定结构上不同的二叉search树（简称BST）与“普通”二叉树的数目是不同的，除非如果通过“考虑树节点值”来表示每个节点可能是例如任何与BST条件相容的数字，那么不同的（但不是所有的结构上不同的）BST的数量是无限的。 我怀疑你的意思，所以请用一个例子来澄清你的意思！

  1. 二叉树的总数是= 输入图片说明！

  2. 总结i给出了具有n个节点的二叉search树的总数。 在这里输入图像描述

基本情况是t（0）= 1和t（1）= 1，即有一个空的BST和一个BST有一个节点。 在这里输入图像描述

所以，一般来说，你可以使用上面的公式计算二叉search树的总数。 我在Google面试中被问到一个关于这个公式的问题。 问题是有六个顶点可能有多less个二叉search树的总数。 所以答案是t（6）= 132

我想我给你一些想法…

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

二叉search树的数量可以看作是一个recursion的解决scheme。 即二进制search树的数量=（ 左二叉search子树的数量）*（ 右二叉search子树的数量）*（select根的方式）

在BST中，只有元素之间的相对顺序很重要。 因此，在不失一般性的情况下，我们可以假设树中的不同元素是1,2,3,4，…，n 。 而且，让n个元素的BST的数目由f（n）表示 。

现在我们有了多个select根的例子。

  1. select1作为根，在左边的子树上不能插入元素。 n-1个元素将被插入到右边的子树上。
  2. select2作为根，左边的子树上可以插入1个元素。 可以在右边的子树上插入n-2个元素。
  3. select3作为根，在左边的子树上可以插入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，因为确实有一种方法可以使0节点的BST。 f（1）= 1，因为有一个方法可以构成一个节点的BST。

最终公式

Eric Lippert最近有一个非常深入的系列博客文章：“ 每棵二叉树 ”和“ 每棵树都有 ”（此后再加上一些）。

在回答你的具体问题时，他说：

具有n个节点的二叉树的数量由加泰罗尼亚数字给出，其具有许多有趣的特性。 第n个加泰罗尼亚语数字由公式（2n）决定！ /（n + 1）！n！，其指数增长。

如果没有给出。 节点是N然后。

BST的不同数量=加泰罗尼亚语（N）
不同结构上不同的二元树的数目=加泰罗尼亚语（N）

不同数量的二叉树是= N！*加泰罗尼亚语（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

二叉树：

没有必要考虑价值观，我们需要看结构。

由（2幂n） – n给出

例如：对于三个节点，（2个功率3）-3 = 8-3 = 5个不同的结构

二叉search树：

我们甚至需要考虑节点值。 我们称之为加泰罗尼亚号

由2n C n / n + 1给出

Interesting Posts