算法学习011-不同的二叉查找树/搜索树 c++动态规划算法实现中小学算法思维学习信奥算法解析

C++不同的二叉查找树

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、运行结果

五、考点分析

六、推荐资料

C++不同的二叉查找树

一、题目要求

1、编程实现

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

现给定一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

注：节点个数数n在1到19之间

2、输入输出

输入描述：输入一个正整数n（1<=n<=40）

输出描述：只有一行，一个整数，即多少种不同的二叉搜索树

输入样例：

输出样例：

二、算法分析

从给定题目的初步分析可以看出，这是算法中比较典型的不同二叉搜索树
根据二叉搜索的定义可以得出，左子树一定比节点小，右子树比节点大
接下来具体分析：
当节点为0的时候，也就是节点为空，这个是空二叉树也是一棵二叉树
当节点为1的时候，就是只有一个节点1，为一棵二叉树
当节点为2的时候，根据定义可以有：节点为1右子树为2的二叉树和节点为2左子树为1的二叉树，共2棵二叉树
当节点为3的时候，根据上图可以看到由：节点为1的两棵和节点为2的一棵和节点为3的两棵相加而来，共有5棵
而通过观察节点为3的二叉树，当节点为1的时候，发现左子树是为0（一棵），右子树为2和3（两棵）即：1*2=2
再次分析节点为3的二叉树，当节点为2的时候，左右子树都是为1（一棵），即：1*1=1
继续分析节点为3的二叉树，当节点为3的时候，发现左子树是为1和2（两棵），右子树为0（一棵）即：2*1=2
所以可以采用动态规划的方式来进行实现
设置动态数组dp[i]，i表示爬上第几个节点；所以对应的dp[i]就是爬上第i个节点对应的不同的二叉搜索树
而要求第i个节点对应的不同二叉搜索树需要从1遍历到第i个节点，将每个节点对应的左子树对应的不同二叉树乘以右子树对应的不同二叉树然后累加的来
所以可以得出对应的动态数组dp[i]的状态转移方为：dp[i]+=dp[j-1]*dp[i-j]
同时遍历顺序为从小到大，外层从0到n，内层从1到i
而根据题目分析可以得到dp[0]=dp[1]=1

三、程序编写

//程序中的dp可以使用动态数组vector进行实现更好
#include<bits/stdc++.h>
using namespace std;
int dp[20];
int getTrees(int n)
{
	dp[0] = dp[1] = 1;
	for(int i=2;i<=n;i++)
		for(int j=1;j<=i;j++)
			//第i个节点对应的不同二叉搜索由对应不同左子树乘以不同右子树而来
			dp[i] += dp[j-1] * dp[i-j];
	return dp[n];
}
int main()
{
	int n;
	cin >> n;
	cout << getTrees(n);
	return 0;
}

本文作者：小兔子编程作者首页：小兔子编程-CSDN博客