用N个键找到可能的二叉搜索树的总数的程序

下一个→ ←上一页

Q.编写程序，找出有n个键的可能二叉搜索树的总数。

解释

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

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

一个简单的方法来计算可能的二叉搜索树的总数是通过加泰罗尼亚数:

算法

定义Node类，它有三个属性，即data left和data right。这里，left表示节点的左子节点，right表示节点的右子节点。
当创建节点时，数据将传递给节点的data属性，并且left和right都将被设置为null。
定义另一个具有属性根的类。
1. 根表示树的根节点并将其初始化为null。
numOfBST()将找出给定键的所有可能的二叉搜索树:
1. 它将通过调用factorial()来计算给定键的加泰罗尼亚数字。
2. 加泰罗尼亚数可以用公式计算:
  Cn = (2n)!/ n !* (n + 1) !
3. Factorial()将计算给定数字的阶乘。

解决方案

Python

            #表示二叉树类的节点node: def __init__(self,data): #为新节点分配数据，设置左、右子节点为None self。Data =数据;自我。left = None;自我。right =无;类BinarySearchTree: def __init__(self): #表示二叉树self的根。root =无;#factorial()将计算给定数字的阶乘def factorial(self, num): fact = 1;If (num == 0):返回1;其他: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)));
           

输出:

给定键的可能二叉搜索树的总数:42

C

            #include <stdio.h> #include <stdlib.h> //表示二叉树结构节点{int data;Struct node *left;Struct node *right;};//表示二叉树结构的根节点*root = NULL;//createNode()将创建一个新的节点结构节点* createNode(int data){//创建一个新的节点结构节点*newNode = (struct节点*)malloc(sizeof(struct节点));//为newNode分配数据，将左子和右子设置为NULL;newNode->left = NULL;newNode->right = NULL;返回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; }
           

输出:

给定键的可能二叉搜索树的总数:42

JAVA

            公共类BinarySearchTree{//表示二叉树的节点公共静态类node {int data;节点离开;节点对的;public Node(int data){//将数据分配给新节点，将左子节点和右子节点设置为null。Data =数据;这一点。Left = null;这一点。Right = null;}} //表示二叉树公共节点根;public BinarySearchTree(){根= 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)); } }
           

输出:

给定键的可能二叉搜索树的总数:42

c#

            使用系统;命名空间Tree{公共类Program{//表示二叉树公共类node <T>{公共T data;public Node<T> left;public Node<T> right;public Node(T data){//将数据分配给新节点，将左子节点和右子节点设置为null。Data =数据;这一点。Left = null;这一点。Right = null;}}公共类BinarySearchTree<T>{//表示二叉树的根公共节点<T>根; 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)); } }
           

输出:

给定键的可能二叉搜索树的总数:42

PHP

            < !DOCTYPE html> <html> <body> <?php //表示二叉树类node {public $data;公共美元离开;公众对美元;函数__construct($data){//将数据分配给新节点，将左右子节点设置为NULL $this->data = $data;$this->left = NULL;$this->right = NULL;}}类BinarySearchTree{//表示二叉树的根公共$root;函数__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); ?> <div style="text-align:center;margin-bottom:5px;"><form action="http://www.baidu.com/baidu" target="_blank"><div bgcolor="#FFFFFF" style="text-align:center;"><input name="tn" type="hidden" value="baidu"><a href="http://www.baidu.com/"><img src="http://img.baidu.com/img/logo-80px.gif" width="80px" height="29px" alt="Baidu" align="bottom" border="0"></a><input type="text" name="word" size="30" placeholder="" value=""><input type="submit" value="baidu"></div></form></div><div id="so360" style="text-align:center;margin-bottom:5px;"><form action="https://www.so.com/" target="_blank" id="so360form"><img src="http://p1.qhimg.com/d/_onebox/search.png" width="100px" height="25px"> <input type="text" autocomplete="off" name="q" id="so360_keyword" placeholder="" value="">  <input type="submit" id="so360_submit" value="360"> <input type="hidden" name="ie" value="gbk"><input type="hidden" name="src" value="zz"> <input type="hidden" name="site" value="so.com"> <input type="hidden" name="rg" value="1"></form></div><div id="sogou" style="text-align:center;margin-bottom:5px;"><form action="https://www.sogou.com/" target="_blank" id="so360form"><img src="https://www.sogou.com/web/index/images/logo_440x140.v.4.png" width="100px" height="25px"> <input type="text" autocomplete="off" name="q" id="sogou.com_keyword" placeholder="" value="">  <input type="submit" id="sogou_submit" value="sougou"> <input type="hidden" name="ie" value="gbk"><input type="hidden" name="src" value="zz"> <input type="hidden" name="site" value="so.com"> <input type="hidden" name="rg" value="1"></form></div><div align="center"><a target="_blank" href="/sitemap.xml">map</a></div></body> </html>
           

输出:

给定键的可能二叉搜索树的总数:42

下一个话题项目列表

←上一页下一个→

视频加入我们的Youtube频道:现在加入

反馈

将你的意见发送至(电子邮件保护)

帮助别人，请分享

学习最新教程

Splunk

SPSS

2022世界杯赛程安排

transact - sql

Tumblr

ReactJS

正则表达式

强化学习

世界杯2022赛程时间表最新

RxJS

反应本地

Python设计模式

Python的枕头

Python的乌龟

Keras

准备

资质

世界杯2022赛程时间表

语言能力

面试问题

公司的问题

b .技术/马华

2022世界杯预选赛

数据结构

DAA

操作系统

计算机网络

编译器设计

计算机组织

离散数学

道德黑客

计算机图形学

软件工程

网络技术

网络安全

自动机

C编程

c++

Java

net

Python

项目

控制系统

数据挖掘

数据仓库

2022世+D11837:D11850界杯八强让球

JavaTpoint提供了太多高质量的服务。邮件地址:(电子邮件保护)，以获取有关特定服务的更多信息。

网站设计
网站开发
世界杯欧洲杯小组赛
PHP开发
WordPress
平面设计
标志
2022卡塔尔世界杯赛程图
页面上和页面外的SEO
PPC
内容开发
企业培训
课堂和在线培训
数据输入

大学校园培训

JavaTpoint提供核心Java、高级Java、。net、Android、Hadoop、PHP、Web技术和Python的大学校园培训。请将您的要求寄至(电子邮件保护)
持续时间:1 - 2周

^{喜欢/订阅我们以获取最新更新或通讯}

项目

Q.编写程序，找出有n个键的可能二叉搜索树的总数。

解释

算法

解决方案

Python

C

JAVA

c#

PHP

反馈

帮助别人，请分享

学习最新教程

准备

热门的技术

b .技术/马华

2022世+D11837:D11850界杯八强让球

大学校园培训