二叉搜索树的数量

Question

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

解释和答案将有所帮助.

我已应用加泰罗尼亚数字公式,但结果不适合选项,所以这只是确定.

Answer 1

使用加泰罗尼亚数字,用n节点计算完整的二叉树,答案是d) 2642640= 14*132*1430.这是从我们每个未知子树中扩展(子)树的可能性.

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

更新:

正如Mark Dickinson在下面的评论中所建议的那样,澄清一下:上图和第一个语句中提到的"节点"是"内部"节点,我们正在以各种方式进行安排,而n加泰罗尼亚语数字正在计算完整的二进制数树叶与n+1节点.具有l叶节点的二叉树具有l - 1内部节点.