查找n个值构造的二叉搜索树总和的Java程序

1 简介

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

此方法涉及递归选择一个节点作为根节点，并创建可能的二进制搜索树。

一种简单的计算可​​能的二叉搜索树总数的方法是通过加泰罗尼亚语数字：

Cn = (2n)! / n! *(n+1)!  

2 算法思路

• 定义具有三个属性的Node类，即：左和右数据。在此，左代表节点的左子节点，右代表节点的右子节点。
• 创建节点时，数据将被传递到该节点的data属性，并且left和right都将设置为null。
• 定义另一个具有属性根的类。
  • 根表示树的根节点，并将其初始化为null。
• 它将通过调用factorial（）来计算给定密钥的加泰罗尼亚语数字。
• 加泰罗尼亚数可以使用以下公式计算：
  Cn =（2n）！/ n！*（n + 1）！
• Factorial（）将计算给定数字的阶乘。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
public class BinarySearchTree {  
  
    //Represent the node of binary tree  
    public static class Node{  
        int data;  
        Node left;  
        Node right;  
  
        public Node(int data){  
            //Assign data to the new node, set left and right children to null  
            this.data = data;  
            this.left = null;  
            this.right = null;  
            }  
        }  
  
    //Represent the root of binary tree  
    public Node root;  
  
    public BinarySearchTree(){  
        root = null;  
    }  
  
    //factorial() will calculate the factorial of given number  
    public int factorial(int num) {  
        int fact = 1;  
        if(num == 0)  
            return 1;  
        else {  
            while(num > 1) {  
                fact = fact * num;  
                num--;  
            }  
            return fact;  
        }  
    }  
  
    //numOfBST() will calculate the total number of possible BST by calculating Catalan Number for given key  
    public int numOfBST(int key) {  
        int catalanNumber = factorial(2 * key)/(factorial(key + 1) * factorial(key));  
        return catalanNumber;  
    }  
  
    public static void main(String[] args) {  
  
        BinarySearchTree bt = new BinarySearchTree();  
  
        //Display total number of possible binary search tree with key 5  
        System.out.println("Total number of possible Binary Search Trees with given key: " + bt.numOfBST(5));  
      }  
}  

输出结果为：

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