首页 > 试题广场 >

题目来源于王道论坛 先序序列为a,b,c,d

[单选题]
题目来源于王道论坛

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


  • 13
  • 14
  • 15
  • 16
查看答案及解析
添加回答
推荐
zsw3头像 zsw3

解析：

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

发表于 2018-06-16 11:22:08 回复(3)
karaysn头像 karaysn
卡特兰数吧
发表于 2018-09-04 09:46:32 回复(0)
WayhomeChen头像 WayhomeChen
根据前序序列的特点：根、左、右，得出以下递推式：

其中，n是序列的元素数，f(n)是有n个元素的前序序列的所有可能的二叉树的个数，f(0)=1，f(1)=1。
解释：一个有n个元素的前序序列，其左右子树的结点个数情况分别有：左0右n-1，左1右n-2，左2右n-3，...，左n-1右0，共n种情况；而若左子树有a个结点，右子树有b个结点，则总共有a*b种情况，即所有种情况是左右子树的所有种情况的笛卡儿积。于是，要计算f(n)，就要对所有种左右子树结点数的情况进行情况数求和，是先分类再分步的计算。
计算这个式子可以用递归（或数学归纳法）的思路求解：由f(0)和f(1)得出f(2)，再由f(0)和f(1)和f(2)得出f(3)，再由f(0)和f(1)和f(2)和f(3)得出f(4)，f(4)就是答案。
我计算出来的是：f(0)=f(1)=1，f(2)=2，f(3)=5，f(4)=14
发表于 2020-05-12 11:24:09 回复(0)
上岸upup头像 上岸upup
王道里面有公式，1/(n+1)*Cn2n
发表于 2022-03-07 20:32:47 回复(0)
tommyMusk头像 tommyMusk
卡特兰数https://www.nowcoder.com/test/question/done?tid=53331389&qid=3983#summary
发表于 2022-03-10 23:23:45 回复(0)
不做人了头像 不做人了
树是一种递归，可以使用递推公式
发表于 2020-07-01 18:47:58 回复(0)
wxl_1605头像 wxl_1605
组合（n,2n）=(2n)!/(n!*(2n-n)!)
发表于 2018-09-11 21:15:51 回复(1)
提交观点

问题信息

树
上传者：zsw3
难度：
7条回答 3525浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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