从 n 个不同的元素可以构造多少个二叉搜索树？我们怎样才能找到一个经过数学证明的公式呢？
示例： 如果我们有 3 个不同的元素，例如 1、2、3，则有 5 个二叉搜索树。
问问题
24580 次
3 回答
41
给定 n 个元素，可以从这些元素组成的二叉搜索树的数量由第 n 个加泰罗尼亚数（表示为 C n）给出。这等于
直观地说，加泰罗尼亚数字表示您可以通过以下方式创建由 n 个元素组成的结构的方式数量：
- 将元素排序为 1、2、3、...、n。
- 选择其中一个元素用作枢轴元素。这会将剩余的元素分成两组——元素之前的元素和元素之后的元素。
- 从这两个组中递归地构建结构。
- 将这两个结构与您删除的一个元素组合在一起以获得最终结构。
这种模式与您从一组 n 个元素构建 BST 的方式完美匹配。选择一个元素作为树的根。所有较小的元素必须向左，所有较大的元素必须向右。从那里，您可以从左侧和右侧的元素构建更小的 BST，然后将它们与根节点融合在一起以形成整体 BST。使用 n 个元素执行此操作的方法数由 C n给出，因此可能的 BST 数由第 n 个加泰罗尼亚数给出。
希望这可以帮助！
于 2013-04-14T21:56:33.757 回答
9
我确信这个问题不仅仅是使用数学公式来计算。我花了一些时间编写程序以及计算背后的解释或想法。
我尝试用递归和动态编程来解决它。希望这可以帮助。
该公式已经存在于上一个答案中：
因此，如果您有兴趣学习解决方案并了解方法，您可以随时查看我的文章Count Binary Search Trees created from N unique elements
于 2013-08-25T11:00:17.897 回答
3
令 T(n) 为 n 个元素的 bst 数。
给定 n 个不同的有序元素，编号为 1 到 n，我们选择 i 作为根。
这将 (1..i-1) 留在左子树中用于 T(i-1) 组合，将 (i+1..n) 留在右子树中用于 T(ni) 组合。
所以：
T(n) = sum_i=1^n(T(i-1) * T(n-i))
当然 T(1) = 1
于 2013-04-14T21:57:46.137 回答