10

考虑我有一个数组[3,18,15,25,26]，可以从中形成多少个可能的二叉搜索树？

4

3 回答 3

16

看了MicSim链接的问题后，我还是不满意，所以我开始自己研究。这就是我想出的...

每棵树都可以被认为是具有父根节点的两棵树。如果您分别知道两个子分支的可能组合的数量，则具有该根节点的总组合是子组合的乘积。

我们可以通过首先解决较低计数的实例来开始构建较高计数的解决方案。

我将使用C(n)加泰罗尼亚数来表示 n 个节点的所有可能组合。

希望这两个是显而易见的：

C(0) = 1
C(1) = 1

C(2) 也相当明显，但它可以构建，所以让我们这样做。有两种方法可以选择根节点。一个留下一个孩子计数（左：右）1:0和另一个0:1。所以，第一种可能性是C(1)*C(0) = 1*1 = 1。第二个是C(0)*C(1) = 1*1 = 1。把这些加在一起给了我们

C(2) = 2

没有什么太令人兴奋的了。现在让我们做3个节点。有 3 种方法可以选择根节点，因此有 3 个子分组。您可能的组2:0是1:1和0:2。

根据我们之前的定义，C(3)可以写成C(2)*C(0) + C(1)*C(1) + C(0)*C(2) = 2*1 + 1*1 + 1*2 = 2+1+2 = 5。

C(3) = 5

4 个节点具有3:0、2:1和1:2的子组0:3。所以，C(4)可以写成C(3)*C(0) + C(2)*C(1) + C(1)*C(2) + C(0)*C(3) = 5*1 + 2*1 + 1*2 + 1*5 = 5+2+2+5 = 14。

C(4) = 14

希望有两件事开始变得明显。首先，这很快就会变得很麻烦。其次，我以相当冗长的方式描述的是 wiki 页面上的递归关系表示。

我不知道这是否有帮助，但它帮助我完成了练习，所以我想我会分享。我开始时并没有尝试重新创建递归关系，所以我的结果与现有方法之一相匹配是件好事。

于 2012-07-30T16:46:45.827 回答
7

可以使用 N 个键创建的二叉搜索树的可能数量由第 N 个加泰罗尼亚语数给出。

另请参阅此问题：可以使用 N 个键创建的二叉搜索树的可能数量由第 N 个加泰罗尼亚语数给出。为什么？

于 2012-07-30T15:15:11.073 回答
5

数组的任何节点都可以是 BST 的根，对于每个根，不同的搜索树的数量是左右子数组的组合（乘积）。所以，

BSTCount(0) = 1
BSTCount(n) = sum_{i = 1}^{n} BSTCount(i-1) * BSTCount(n-i)

您可以对前几个 n 评估此函数，然后在On-Line Encyclopedia of Integer Sequences™ (OEIS)中查找序列以找到闭合形式。

于 2012-07-30T15:16:47.093 回答