问：计算具有 n 个键的可能二叉搜索树总数的程序。

17 Mar 2025 | 5 分钟阅读

说明

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

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

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

Program to find the total number of possible Binary Search Trees with n keys

算法

定义 Node 类，该类包含三个属性：data、left 和 right。这里，left 表示节点的左子节点，right 表示节点的右子节点。
当创建一个节点时，数据将传递到节点的 data 属性，并且 left 和 right 都将被设置为 null。
定义另一个类，该类有一个 root 属性。
1. 根表示树的根节点，并将其初始化为 null。
numOfBST() 将找出给定键的总共可能的二叉搜索树。
1. 它将通过调用 factorial() 来计算给定键的卡特兰数。
2. 卡特兰数可以使用以下公式计算：
  Cn = (2n)! / n! *(n+1)!
3. Factorial() 将计算给定数字的阶乘。

解决方案

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class BinarySearchTree:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
        
    #factorial() will calculate the factorial of given number
    def factorial(self, num):
        fact = 1;
        if(num == 0):
            return 1;
        else:
            while(num > 1):
                fact = fact * num;
                num = num - 1;
            return fact;
    
    #numOfBST() will calculate the total number of possible BST by calculating Catalan Number for given key
    def numOfBST(self, key):
        catalanNumber = self.factorial(2 * key)/(self.factorial(key + 1) * self.factorial(key));
        return int(catalanNumber);
 
bt = BinarySearchTree();
 
#Display the total number of possible binary search tree with key 5
print("Total number of possible Binary Search Trees with given key: " + str(bt.numOfBST(5)));

输出

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

C

#include <stdio.h>
#include <stdlib.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root of binary tree
struct node *root = NULL;
 
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right child to NULL
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
 
//factorial() will calculate the factorial of given number
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
int numOfBST(int key) {
    int catalanNumber = factorial(2 * key)/(factorial(key + 1) * factorial(key));
    return catalanNumber;
}
    
int main(){
    
    //Display total number of possible binary search tree with key 5
    printf("Total number of possible Binary Search Trees with given key: %d", numOfBST(5));
    
    return 0;
}

输出

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

JAVA

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

C#

using System;
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to null
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class BinarySearchTree<T>{
            //Represent the root of binary tree
            public Node<T> 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()
        {
            BinarySearchTree<int> bt = new BinarySearchTree<int>();
        
            //Display total number of possible binary search tree with key 5
            Console.WriteLine("Total number of possible Binary Search Trees with given key: " + bt.numOfBST(5));                
        }    
    }

输出

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

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class BinarySearchTree{
    //Represent the root of binary tree
    public $root;
    function __construct(){
        $this->root = NULL;
    }
    
    //factorial() will calculate the factorial of given number
    function factorial($num) {
        $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
    function numOfBST($key) {
        $catalanNumber = $this->factorial(2 * $key)/($this->factorial($key + 1) * $this->factorial($key));
        return $catalanNumber;
    }
}
 
$bt = new BinarySearchTree();
        
//Display total number of possible binary search tree with key 5
print "Total number of possible Binary Search Trees with given key: " . $bt->numOfBST(5);      
?>
</body>
</html>

输出

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

下一个主题程序列表

问：计算具有 n 个键的可能二叉搜索树总数的程序。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

程序

问：计算具有 n 个键的可能二叉搜索树总数的程序。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

计算圆柱体体积的程序

计算等边三角形面积的程序

检查迪沙里数（Disarium number）的程序

计算圆锥体积的程序

反向打印数组元素的程序

打印数组中最大元素的程序

华氏度转摄氏度的程序

计算正方形面积的程序

打印 n 个数的平均值的程序

在单向链表末尾插入新节点的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器