-
2018-11-02 21:05:37
【n个节点的二叉树有多少种形态(Catalan数)】
分析过程:
(1)先考虑只有一个节点的情形,设此时的形态有f(1)种,那么很明显f(1)=1(2)如果有两个节点呢?我们很自然想到,应该在f(1)的基础上考虑递推关系。那么,如果固定一个节点后,左右子树的分布情况为1=1+0=0+1,故有f(2) = f(1) + f(1)
(3)如果有三个节点,(我们需要考虑固定两个节点的情况么?当然不,因为当节点数量大于等于2时,无论你如何固定,其形态必然有多种)我们考虑固定一个节点,即根节点。好的,按照这个思路,还剩2个节点,那么左右子树的分布情况为2=2+0=1+1=0+2。
所以有3个节点时,递归形式为f(3)=f(2) + f(1)*f(1) + f(2)。(注意这里的乘法,因为左右子树一起组成整棵树,根据排列组合里面的乘法原理即可得出)(4)那么有n个节点呢?我们固定一个节点,那么左右子树的分布情况为n-1=n-1 + 0 = n-2 + 1 = … = 1 + n-2 = 0 + n-1。此时递归表达式为f(n) = f(n-1) + f(n-2)f(1) + f(n-3)f(2) + … + f(1)f(n-2) + f(n-1)
接下来我们定义没有节点的情况,此时也只有一种情况,即f(0)=1
那么则有:
f(0)=1,f(1)=1
f(2)=f(1)f(0)+f(0)f(1)
f(3)=f(2)f(0)+f(1)f(1)+f(0)f(2)
.
.
.
.
f(n)=f(n-1)f(0)+f(n-2)f(1)+……….+f(1)f(n-2)+f(0)f(n-1)
该数列称为卡特兰数(Catalan数),该递推关系的解为:
这里写图片描述
即含n个节点的二叉树有f(n)种形态。【其他使用Catalan数解决的问题】
(1)矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?
(2)一个栈(无穷大)的进栈序列为1,2,3,…n,有多少个不同的出栈序列?
(3)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)
(4)将一个凸多边形区域分成三角形区域的方法数?
(5)在圆上选择2n个点,将这些点成对连接起来,使得所得到的n条线段不相交的方法数。
(6)一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?更多相关内容 -
Python算法之求n个节点不同二叉树个数
2020-09-21 02:21:53本文先向大家分享了建立二叉树的简单代码,其次介绍了Python计算n个节点不同二叉树个数的问题及实现代码示例,具有一定参考价值,需要的朋友可以了解下。 -
求证:具有 n 个结点的完全二叉树的深度为......
2021-10-13 23:55:29求证:具有 n 个结点的完全二叉树的深度为⌊log2n⌋+1 或⌈log2(n+1)⌉ 。 证明:设完全二叉树的深度为h,则依据“深度为h的二叉树至多有2h-1个结点(h≥1)”的性质,可得:2^(h-1)-1<n ≤ 2^h-1 其等价于 2^(h-1)...求证:具有 n 个结点的完全二叉树的深度为⌈log2(n+1)⌉或⌊log2n⌋+1
证明:设完全二叉树的深度为h,则依据“深度为h的二叉树至多有2h-1个结点(h≥1)”的性质,
可得:2h-1-1<n ≤ 2h-1
其等价于 2h-1<n+1 ≤ 2h,也即 2h-1≤ n<2h● 对式子 2h-1<n+1 ≤ 2h 求对数,可得 h-1<log2(n+1) ≤ h
显然,此时完全二叉树的深度h=⌈log2(n+1)⌉● 对式子 2h-1≤ n<2h 求对数,可得 h-1 ≤log2n<h
显然,此时完全二叉树的深度h=⌊log2n⌋+1
-
输出具有n个结点的所有不同的二叉树-增强前序遍历形式输出-C++
2020-09-19 23:42:10我们知道具有n个结点的不同的二叉树的数量是个(这是一个卡塔兰数),那么如何确定这些二叉树是什么样子的呢?下面是博主的思路: 我们还知道一个入栈序列的不同出栈序列的数量也是个,于是博主就想:这不是巧了么,...我们知道具有n个结点的不同的二叉树的数量是
个(这是一个卡塔兰数),那么如何确定这些二叉树是什么样子的呢?下面是博主的思路:
我们还知道一个入栈序列的不同出栈序列的数量也是
个,于是博主就想:这不是巧了么,既然他们的数量是一样的,而且均不相同,那么是不是可以构建一个映射,使得不同的出栈序列和不同的二叉树进行一一对应呢。
于是,在博主的做了深入的观察和思考后,发现对于其中一个出栈序列,其实和某个二叉树的中序遍历结果是相对应的,而经过进一步探索,发现入栈序列是所有二叉树的前序遍历结果。
众所周知,一个二叉树的前序和中序遍历结果是可以唯一确定一棵二叉树的。
然而在写代码的过程中博主又遇到了一个难题:就是如何输出一个入栈序列的全部出栈序列呢?为了解决这个问题,博主上某搜索网站参考了各位大神的代码,发现他们基本都是用回溯法解决的。于是在一番研究之下。我成功地写出了输出一个入栈序列的全部出栈序列的函数。
这样一来,所有问题都解决了。然后经过了20分钟的编码。博主成功地写出了求解具有n个结点的不同的二叉树的所有前序增强序列的C++代码:
另外如果大家有什么疑问或者见解可以在评论下方讨论,如果发现确实有什么错误的话,还请指正。
如下所示:
#include <iostream> using namespace std; static const int M = 100; //依次代表的意思是结点数、栈、出栈序列、栈指针、出栈序列大小、输入顺序、二叉树中序序列,二叉树中序序列索引 static int n,stk[M],seq[M],stk_top=-1,seq_size=0,input[M],in[M],idx; //根据二叉树的前序和中序遍历获取增强前序序列 static void getEnhencedPreorder(int root, int begin, int end) { if (begin > end) { cout << "#" << " "; return; } int i = begin; while (input[root] != in[i]) { i++; } cout << input[root] << " "; getEnhencedPreorder(root + 1, begin, i - 1); getEnhencedPreorder(root + (i - begin) + 1, i + 1, end); } //获取所有出栈序列 static void getSequence(int i) { if (i == n) { //收集结果 idx = 0; for (int i = 0; i < seq_size; i++) { in[idx++]=seq[i]; } for (int i = stk_top; i >= 0; i--) { in[idx++] = stk[i]; } //根据前序和中序遍历获取其增强前序遍历序列 getEnhencedPreorder(0,0,n-1); cout << endl; } else { //对于一个入栈的元素,可以入栈,也可以不入栈 //但是每种情况都要检验 //一、首先是元素入栈了 stk[++stk_top]= input[i]; getSequence(i + 1); stk_top--; //二、然后元素没有入栈,并且栈顶元素出栈了 if (stk_top!=-1) { int top= stk[stk_top--]; seq[seq_size++]=top; getSequence(i); seq_size--; stk[++stk_top] = top; } } } //相当于main函数 void stack_pop_sequence_re2_main() { cin >> n; for (int i = 0; i < n;i++) { input[i] = i + 1; } getSequence(0); }
下面是一个示例(当n取3时):
其入栈序列为1 2 3,输出结果为所有组成的二叉树的前序增强序列('#'号标识空)。
-
n个结点的二叉树一共有多少种形态
2021-07-13 14:34:13记n个节点的二叉树形态个数为A[n] 1)0个节点的二叉树只有1种形态,A[0]=0;1个节点的二叉树只有1种形态,A[1]=1 2)n个节点(n>=2)的二叉树有,求和的每一项,分别表示根的左子树为m个节点、右子树为 n-1-m个...记n个节点的二叉树形态个数为A[n]
1)0个节点的二叉树只有1种形态,A[0]=0;1个节点的二叉树只有1种形态,A[1]=12)n个节点(n>=2)的二叉树有
,求和的每一项,分别表示根的左子树为m个节点、右子树为 n-1-m个节点的情况。(总共n个节点,左子树m个节点,根节点有1个,那么右子树的节点数为n-1-m个)
刚好就是catalan数,直接用catalan数的公式:h(n)==
-
n个节点二叉树有几个指针域_java在二叉树的每个节点中填充下一个右指针
2020-09-01 20:15:07n个节点二叉树有几个指针域Problem Statement: You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. Populate each next pointer to point to its ... -
n个节点的二叉树,最多可以有多少层? D
2021-01-25 23:24:201.n个节点的二叉树,最多可以有多少层? A.n/2 B.log(n) C.n-1 D.n 答案解析: D 假设从根节点开始,根节点的层数为1,每一层一个节点,则有n层。 -
二叉树n个结点的深度求法
2022-04-08 21:12:51一棵二叉树有n个结点。 该树满足任意结点的左子树结点个数和右子树的结点个数之差最多为1。 因为 2^n-1是表示n层满二叉树的结点总数 所以 2^n-1>=二叉树的结点总数 若结点为2022,则树的最大深度是? 2^10=... -
一种构建n个结点的二叉树所有形态的算法 (2012年)
2021-04-24 02:46:45给出了一种基于二叉排序树构建具有n个结点的二叉树所有不同形态的算法,该算法简单明了,易于理解和实现。 -
n个节点的二叉树有多少种形态(Catalan数)
2019-01-24 06:30:56【n个节点的二叉树有多少种形态(Catalan数)】 分析过程: (1)先考虑只有一个节点的情形,设此时的形态有f(1)种,那么很明显f(1)=1 (2)如果有两个节点呢?我们很自然想到,应该在f(1)的基础上考虑递推关系... -
【数据结构】线索二叉树中为什么n个结点的二叉树中,有n+1和空指针
2020-12-13 21:23:46线索二叉树中为什么n个结点的二叉树中,有n+1和空指针: 因为每个叶结点有2个空指针,而每个度为1的结点有1个空指针, 则总的空指针数为 2 * n0 + n1 而 n0 = n2 + 1 (二叉树的特性) 所以对上式化简,德总的空... -
n个节点的二叉树有多少种形态
2019-07-29 11:59:19(1)先考虑只有一个节点的情形,设此时的形态有f(1)种,那么很明显f(1)=1 (2)如果有两个节点呢?我们很自然想到,应该在f(1)的基础上考虑递推关系。那么,如果固定一个节点后,左右子树的分布情况为1=1+0=0+1,... -
[算法][Python]随机生成一棵具有N个节点的二叉树
2020-08-31 23:18:41思路很简单: 初始化N个树节点,每次随机从中选出一个父节点和子节点,随机决定子节点作为父节点的左叶或右叶; 特别的,使用并查集来避免出现构建回环的情况;(并查集的相关知识请参考《算法4》) 考虑到每个节点... -
递归算法计算n个结点的二叉树的形态数
2021-11-16 21:35:47递归算法计算n个结点的二叉树的形态数 本题来自苏州大学872考研2016年真题。 设计递归算法,求出包涵n个结点的不同形态的二叉树的数目k。如:3个结点的二叉树共有五种不同形态,即n=3时,k=5。 算法思想:本题与求... -
N个节点的二叉树有多少种形态
2019-08-05 21:59:07转载自N个节点的二叉树有多少种形态 这是一道阿里的面试题。其实算不上新鲜,但是我之前没关注过,如今碰到了,就顺便探讨下这个问题吧:) 拿到这个题,首先想到的是直接写出表达式肯定不行,所以有必要从递推入手... -
具有N个节点的二叉树有多少种形态,居然有计算公式
2017-09-07 10:34:11具有3个结点的二叉树有几种形态? 正确答案: B 你的答案: B (正确) 4 5 6 7 解析 这是一道牛客网上的测试题,因为题目是求3个节点的二叉树的形态,所以直接手画了。... -
N个节点的二叉树的形态数详细推导
2020-03-20 22:49:39N个节点的二叉树的形态数 卡特兰数 -
具有n个结点且深度也为n的二叉树有多少种?
2015-11-30 09:37:04如题,考研数据结构问题,具有n个结点且深度也为n的二叉树有多少种? -
n个结点的完全二叉树的深度公式推导
2021-05-03 18:19:03考虑1个叶子节点和0个叶子节点的极端情况: 故: -
n个结点的二叉树的形状数目(动态规划)
2020-11-27 19:15:44一、题目描述 给定nnn个结点,求二叉树的形状数目。 二、想法 对于一颗有nnn个结点的二叉树。 保持其右子树不变,改变左子树形态,此时有kkk种...根据排列组合,当前n个结点的二叉树有f(n−k−1)∗f(k)∗2f(n-k-1)*f(k -
求N个结点能够组成的二叉树的个数
2022-05-04 20:51:35求N个结点能够组成的二叉树的个数 -
c语言, 一棵具有n个结点的完全二叉树以数组存储,试写一个非递归 算法实现对 该树的前序遍历。
2021-05-21 17:51:05满意答案398ibxhsf2014.06.26采纳率:48%等级:9已帮助:566人以向量为存储结构的完全二叉树,其存储在向量中的结点其实是按层次遍历的次序存放的,可以根据课本第74页的内容设计出算法:typedef char DataType;... -
教你一秒钟得出 N个节点的完全二叉树有多少个叶子节点 / 度为1或2的节点个数
2020-02-29 19:46:00没耐心的同学们可以直接拉到最底下看结论,有兴趣的话可以浏览全篇文章 ...一棵完全二叉树具有1000个结点,则此完全二叉树有多少个度为2的结点? 完全二叉树699个节点,则叶子节点有多少个? 已知完全二叉树... -
n个结点下,可构成多少种不同形态的二叉树
2020-05-10 11:41:29n个结点下,可构成多少种不同形态的二叉树 先来回顾下“树的定义”中的部分描述: 树是由唯一的根和若干棵互不相交的子树组成的。其中,每一棵子树又是一棵树,也是由唯一的根结点和若干颗互不相交的子树组成的。... -
关于完全二叉树高度h与结点个数n的推导
2021-09-20 09:10:21推导1:具有n个(n>0)结点的完全二叉树的高度h为:⌈log2(n+1)⌉ 由于高度h的满二叉树共有2h-1个结点 高度为h-1的满二叉树有2h-1-1个结点 可得2h-1-1 < n <=2h-1 不等式同时+1:2h-1 < n+1 <=2h ... -
具有1102个结点的完全二叉树一定有__个叶子结点。
2020-06-28 09:57:16具有1102个结点的完全二叉树一定有__个叶子结点。 79 551 √ 1063 不确定 设n2为度为bai2的节点,n1为度为1的节点,dun0为度为0的节点; 边数n=节点zhi数-1,即n=1101; n=2n2+n1; 完全二dao叉树度为1的节点只能...