algorithm - 二叉搜索树的数量

Question

具有 20 个节点且元素为 1,2,3,...,20 的二叉搜索树的数量是多少，使得树的根为 12，左子树的根为 7？一)2634240b) 1243561c) 350016d) 2642640

解释和答案会很有帮助。

我已经应用了加泰罗尼亚数字公式，但选项的结果不合适，所以这只是为了确定。

Answer 1

使用 Catalan numbers ，计算具有 n 节点的完整二叉树，答案将是 d) 2642640 = 14 * 132 * 1430。这就是从我们的每个未知数扩展(子)树的可能性子树。

           12
          /  \
         7    (8 nodes)
        / \
(6 nodes) (4 nodes)

更新:

正如 Mark Dickinson 在下面的评论中所建议的那样，澄清一下:上图中和第一个语句中提到的“节点”是“内部”节点，我们正在以各种方式安排这些节点，而 n 第一个 Catalan 数正在计算 具有 n+1 个叶节点 的完整二叉树。 Binary trees with l leaf nodes have l - 1 internal nodes .