查找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

 

热门文章

优秀文章