首页 > 试题广场 >

先序序列为a,b,c,d 的不同二叉树的个数是 （） 。

[单选题]

先序序列为a,b,c,d 的不同二叉树的个数是 （） 。 

  • 13
  • 14
  • 15
  • 16
添加回答
推荐
艾晓米Amyfairy头像 艾晓米Amyfairy

根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列 a,b,c,d 为入栈次序，则出栈序列的个数为？”，对于 n 个不同元素进栈，出栈序列的个数为 =14 。（来自王道论坛）

编辑于 2016-12-01 18:29:31 回复(7)
笑以头像 笑以
这是在考Catalan数。先序序列为a,b,c,d 的不同二叉树的个数是 、对于 n 个不同元素进栈，出栈序列的个数、以及n个节点的二叉树有多少种形态等问题都是考Catalan数，具体可以百度一下。
发表于 2018-06-19 01:00:12 回复(0)
紫夜丶听雨头像 紫夜丶听雨

卡特兰数的应用：

  • 出栈次序
  • n个节点的二叉树构成
  • 凸多边形的三角形划分
  • 括号匹配，网格两点之间抵达方案等

套公式：
C(2n,n)/(n+1)即可

发表于 2018-09-04 09:30:17 回复(0)
Azoth头像 Azoth

(1/(n+1))*Cn2n

发表于 2018-09-02 20:29:35 回复(0)
Dream_forever头像 Dream_forever

只给出了前序序列，则二叉树未确定，相当于求n个节点的二叉树可能的个数有多少个，直接套用公式C 2 n n /(n+1)

编辑于 2018-04-02 14:09:43 回复(0)
josan头像 josan
我就提一个名词

卡特兰数  Catalan Number
发表于 2017-07-09 13:07:56 回复(0)
我是俊生啊头像 我是俊生啊
通项公式为 1/(n+1) * C(n, 2n)
发表于 2017-05-25 09:38:50 回复(0)
rulingfong头像 rulingfong
卡特兰数
发表于 2017-09-14 10:30:05 回复(0)
八部龙波头像 八部龙波
1/(n+1) * C(2n,n)=1/5*(8,4)=(1/5)*((8*7*6*5)/(4*3*2*1))=(1/5)*70=14
发表于 2017-07-31 12:21:34 回复(0)
Tom_jerry头像 Tom_jerry
根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列 a,b,c,d 为入栈次序，则出栈序列的个数为？”，对于 n 个不同元素进栈，出栈序列的个数为 =14 。（来自王道论坛）

2.直接利用卡特兰数，h(n)=C(2n,n)/(n+1)。求得是14
发表于 2018-03-30 11:18:22 回复(0)
美团到店招聘头像 美团到店招聘
n个结点构成的不同二叉树个数为：C 2 n n /(n+1)
n = 4带入得：C8 4/5 = 14
发表于 2017-03-05 09:30:00 回复(2)
沙月ちゃん头像 沙月ちゃん

由于先序排列的顶点个数不多，因此可以直接枚举。
枚举时，为了防止重复或者漏掉，我们可以按照每层的顶点数进行分类讨论。
注意：接下来枚举的是二叉树的形状，因此不要在意顶点的标记。

第一类：“1-1-1-1”型

图片说明
共种。

第二类：“1-1-2”型

图片说明
共种。

第三类：“1-2-1”型

图片说明
共种。
显然，对于任意一种形状，它的满足题意的顶点标记的填法有且仅有一种。
综上所述，一共有14种。选B。

发表于 2020-08-06 17:46:40 回复(1)
书丛头像 书丛
以序列   a,b,c,d   为入栈次序，则出栈序列的个数 穷举出14种：
ABCD ABDC ACBD ACDB ADCB
BACD BADC BCAD BCDA BDCA
CBAD CBDA CDBA  DCBA

发表于 2017-02-15 10:31:18 回复(1)
苏亦云凡头像 苏亦云凡
卡特兰数 1,2,5,14,42,132.......
发表于 2019-07-22 15:53:02 回复(0)
vector<>头像 vector<>
遍历的时候，先序遍历是先访问节点，随后节点入栈，中序遍历是，出栈的时候，访问这个节点。
所以无论怎么出栈入栈，先序遍历就是取栈顺序，中序遍历就是出现顺序
发表于 2020-06-15 15:31:10 回复(0)
褪涩头像 褪涩
Catalan Number计算方法：
c[n]=c(2n,n)-c(2n,n-1)
c[4] =c(8,4),c(8,3)=14
发表于 2019-09-14 18:07:28 回复(0)
快说我这信号好头像 快说我这信号好
卡特兰数 按ABCD的序列进栈，求出栈序列有多少个？
编辑于 2018-05-08 18:41:27 回复(0)
空空以空空头像 空空以空空
哎，其实这个跟先序遍历无关吧。就是告诉你有四个结点，可以组成多少种不同形态的二叉树(这个有公式可以求)要真的想先序遍历成a b c d,就把他们套进去那14种状态里不就得了。遍历的结果也只是取决于他们所在的顺序而已，并不是取决于二叉树的形态。
发表于 2017-08-28 01:47:21 回复(1)
sunlight_run头像 sunlight_run
公式C（2n,n）/(n+1)
发表于 2017-06-26 09:24:47 回复(0)
黏黏糖头像 黏黏糖
个数满足卡特兰数列：Cn=(1/(n+1))((2n!)/(n!*n!))代入即可
编辑于 2017-05-26 08:52:26 回复(0)
陈玉龙头像 陈玉龙
14
发表于 2017-02-12 15:24:48 回复(0)
提交观点

问题信息

树
上传者：城市里的养猫者
难度：
24条回答 24764浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号