查找具有 N 个键的可能二叉搜索树总数的 Java 程序

在此程序中，我们需要找出可以用 n 个键构建的二叉搜索树的总数。下面的图显示了具有键值为 3 的可能二叉搜索树。因此，我们可以构建总共五棵二叉搜索树。当我们选择节点 1 作为根节点时，我们得到两棵树。类似地，当我们将 2 选作根节点时得到一棵树，而当我们选择 3 作为根节点时得到两棵树。

这种方法涉及递归地选择一个节点作为根节点并创建可能的二叉搜索树。

计算可能的二叉搜索树总数的简单方法是通过卡塔兰数。

算法

• 定义 Node 类，该类包含三个属性：data、left 和 right。这里，left 表示节点的左子节点，right 表示节点的右子节点。
• 当创建一个节点时，数据将被传递到节点的 data 属性，left 和 right 都将设置为 null。
• 定义另一个类，该类有一个 root 属性。
  • Root 表示树的根节点，并将其初始化为 null。

a. numOfBST() 将找出给定键的所有可能的二叉搜索树的数量

• 它将通过调用 factorial() 来计算给定键的卡塔兰数。
• 可以使用以下公式计算卡塔兰数
  Cn = (2n)! / n! *(n+1)!
• Factorial() 将计算给定数字的阶乘。

程序

输出

Total number of possible Binary Search Trees with given key: 42