1. 概述
在本篇文章中，我们将学习如何计算不同结构的二叉树（Binary Tree）和二叉搜索树（Binary Search Tree, BST）的数量。我们会介绍这些计算公式的直观解释，并结合组合数学中常见的卡特兰数（Catalan Number）进行分析。
我们假设读者已经具备二叉树和二叉搜索树的基本知识，因此不会对这些结构做过多解释。
2. 二叉树与二叉搜索树的区别
- 二叉搜索树（BST）是有序结构，不允许重复值，左子树所有节点值小于根节点，右子树所有节点值大于根节点。
- 二叉树没有这些限制，允许重复值，且没有顺序要求。
由于 BST 的有序性，它支持高效的查找、插入和删除操作，时间复杂度为 ✅O(log n)（在树平衡的前提下）。例如，Java 中的 TreeMap 就使用了红黑树（一种自平衡 BST）作为其底层实现。
而普通的二叉树由于缺乏有序性，通常不用于高效数据操作，因此在实际开发中使用较少。
3. 二叉搜索树的数量
假设我们有 n 个互不相同的节点，要计算这些节点能构成多少种结构不同的二叉搜索树。
3.1 直观理解
- 每棵树都有一个根节点。
- 对于 n 个不同节点，有 n 种选择作为根节点。
- 一旦选定根节点 k，那么：
- 左子树包含 k - 1 个节点
- 右子树包含 n - k 个节点
- 左右子树各自能构造的 BST 数量相乘，就是以当前 k 为根节点时的组合数
因此，总数量为所有可能根节点对应的组合数之和。
3.2 递归公式
设 F(n) 表示 n 个不同节点能构成的 BST 数量：
F(0) = 1 // 空树
F(1) = 1 // 只有一个节点的树
F(n) = Σ F(k) * F(n - k - 1) // k 从 0 到 n - 1
例如：
- F(2) = F(0)F(1) + F(1)F(0) = 11 + 11 = 2
- F(3) = F(0)*F(2) + F(1)*F(1) + F(2)*F(0) = 2 + 1 + 2 = 5
下图展示了 3 个节点可以构成的 5 种不同 BST 结构：
4. 卡特兰数（Catalan Number）
上述递归公式正是第 n 个卡特兰数的定义。卡特兰数广泛应用于组合数学问题中，例如括号匹配、凸多边形三角划分等。
其数学表达式为：
C(n) = (2n)! / ((n + 1)! * n!) = 1/(n + 1) * C(2n, n)
其中 C(2n, n) 是组合数。
✅ 也就是说：
n 个不同节点构成的 BST 数量 = 第 n 个卡特兰数
这个结论的数学证明较为复杂，超出了本文范围，但我们可以记住这个结论并在实际中使用。
5. 二叉树的数量
现在我们考虑的是二叉树（Binary Tree），它与 BST 的最大区别是：
- 二叉树不强制左右子树大小关系
- 二叉树允许节点值重复（但本文假设值是唯一的）
这意味着，相同的树结构，只要节点值不同排列，就可以视为不同的二叉树。
5.1 示例说明
考虑如下三节点结构：
这三棵树的结构完全相同，但由于节点值排列不同，它们被视为不同的二叉树。总共可以有 3! = 6 种排列方式。
5.2 公式推导
设我们有 n 个互不相同的节点：
- 结构不同的 BST 数量为 Catalan(n)
- 每种结构可以有 n! 种节点值排列方式
因此，不同结构 + 不同排列的二叉树总数为：
BinaryTree(n) = n! * Catalan(n)
⚠️ 注意：如果节点值存在重复，则需使用带重复的排列公式（见下节）来替换 n!。
5.3 带重复的排列
当节点值有重复时，排列数不再是 n!，而是：
P = n! / (k₁! * k₂! * ... * kₘ!)
其中：
- k₁, k₂, ..., kₘ 是每个不同值的出现次数
- m 是不同值的数量
- Σkᵢ = n
例如，节点值为 [1, 1, 2]，则排列数为 3! / (2! * 1!) = 3
5.4 最终公式总结
| 类型 | 数量公式 | 说明 |
|---|---|---|
| BST | Catalan(n) | 仅结构不同，值有序 |
| Binary Tree | P * Catalan(n) | 结构不同 + 值不同排列 |
| Binary Tree（结构不同） | Catalan(n) | 仅结构不同，忽略值 |
6. 总结
- ✅ BST 的数量 = 卡特兰数 Catalan(n)
- ✅ 二叉树的结构数量 = Catalan(n)
- ✅ 带不同值的二叉树数量 = 排列数 × Catalan(n)
- ⚠️ 节点值重复时，需使用带重复的排列公式
这些公式在算法设计、面试题、组合数学中经常出现。理解它们的推导过程，有助于我们更深入地掌握树结构的本质特性。