数据结构学习中ing~~, 分享来自青空の霞光大佬的笔记
二叉树练习题:
由三个结点可以构造出多少种不同的二叉树?
这个问题我们可以直接手画得到结果,一共是五种,当然,如果要求N个结点的话,可以利用动态规划求解,如果这道题是求N个结点可以构造多少二叉树,我们可以分析一下:
- 假设现在只有一个结点或者没有结点,那么只有一种,$h(0) = h(1) = 1$
- 假设现在有两个结点,那么其中一个拿来做根结点,剩下这一个可以左边可以右边,要么左边零个结点右边一个结点,要么左边一个结点右边零个结点,所以说 $h(2) = h(1) × h(0) + h(0) × h(1) = 2$
- 假设现在有三个结点,那么依然是其中一个拿来做根节点,剩下的两个结点情况就多了,要么两个都在左边,两个都在右边,或者一边一个,所以说 $h(3) = h(2) × h(0) + h(1) × h(1) + h(0) × h(2)$
我们发现,它是非常有规律的,N每+1,项数多一项,所以我们只需要按照规律把所有情况的结果相加就行了,我们按照上面推导的结果,编写代码:
int main(){
int size;
scanf("%d", &size); //读取需要求的N
int dp[size + 1];
dp[0] = dp[1] = 1; //没有结点或是只有一个结点直接得到1
for (int i = 2; i <= size; ++i) {
dp[i] = 0; //一开始先等于0再说
for (int j = 0; j < i; ++j) { //内层循环是为了计算所有情况,比如i等于3,那么就从j = 0开始,计算dp[0]和dp[2]的结果,再计算dp[1]和dp[1]...
dp[i] += dp[j] * dp[i - j - 1];
}
}
printf("%d", dp[size]); //最后计算的结果就是N个结点构造的二叉树数量了
}
成功得到结果,当然,实际上我们根据这个规律,还可以将其进一步简化,求出的结果序列为:1, 1, 2, 5, 14, 42, 132…,这种类型的数列我们称为卡特兰数,以中国蒙古族数学家明安图 (1692-1763)和比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名,它的通项公式为:
所以也可以不需要动态规划了,可以直接运用函数直接解决
int factorial(int n){
int res = 1;
for (int i = 2; i <= n; ++i) res *= i;
return res;
}
int main(){
int n;
scanf("%d", &n);
printf("%d", factorial(2*n) / (factorial(n) * factorial(n + 1)));
}
一棵完全二叉树有1001个结点,其中叶子结点的个数为?
既然是完全二叉树,那么最下面这一排肯定是按顺序排的,并且上面各层应该是排满了的,那么我们先求出层数,根据性质四: $k = \lfloor log_2n \rfloor + 1 = 9 + 1 = 10$
所以此二叉树的层数为10,也就是说上面9层都是满满当当的,最后一层不满,那么根据性质二,我们求出前9层的结点数: $n = 2^k - 1 = 511$
那么剩下的结点就都是第十层的了,得到第十层所有叶子结点数量 $ = 1001 - 511 = 490$,因为第十层并不满,剩下的叶子第九层也有,所以最后我们还需要求出第九层的叶子结点数量,先计算第九层的所有结点数量: $n = 2^{i - 1}=256$
接着我们需要去掉那些第九层度为一和度为二的结点,其实只需要让第十层都叶子结点除以2就行了: $n = (490 + 1) / 2 = 245$
注意在除的时候+1,因为有可能会出现一个度为1的结点,此时也需要剔除,所以说+1变成偶数这样才可以正确得到结果。最后剔除这些结点,得到最终结果: $n_0 = 256 - 245 + 490 = 501$
所以这道题的答案为501。
深度为h的满m叉树的第k层有多少个结点?
这道题只是看着复杂,但是实际上我们把之前推导都公式带进来就行了。但是注意,难点在于,这道题给的是满m叉树,而不是满二叉树,满二叉树根据性质一我们已经知道: $n = 2^{i-1}$
那m叉树呢?实际上也是同理的,我们以三叉树为例,每向下一层,就划分三个孩子结点出来:
每一层的最大结点数依次为:1、3、9、27....
我们发现,实际上每一层的最大结点数,正好是3的次方,所以说无论多少叉树,实际上变化的就是底数而已,所以说深度为h(h在这里没卵用,障眼法罢了)的满m叉树第k层的结点数: $n = m^{k-1}$
一棵有1025个结点的二叉树的层数k的取值范围是?
这个问题比较简单,层数的最小值实际上就是为完全二叉树的情况,层数的最大值实际上就是连成一根线的情况,结点数就是层数,所以说根据性质四得到最小深度为11,最大深度就直接1025了,k的范围是11 - 1025
将一棵树转换为二叉树时,根节点的右边连接的是?
根据我们前面总结得到的性质,树转换为二叉树之后,根节点一定没有右子树,所以为空
我直接膜