首页 > 试题广场 >

有3个节点的二叉树可能有多少种？

[单选题]
有3个节点的二叉树可能有（）种 
  • 5
  • 13
  • 12
  • 15
查看答案及解析
添加回答
StrongYoung头像 StrongYoung
卡特兰数C(n,2n)/(n+1)

发表于 2015-08-22 22:00:08 回复(0)
shuo~头像 shuo~
根左（第二层）左（第三层）
根左（第二层）右（第三层）
根右（第二层）左（第三层）
根右（第二层）右（第三层）
根左（第二层）右（第二层）
发表于 2019-09-03 18:59:00 回复(0)
yayamma头像 yayamma
发表于 2015-09-10 10:40:50 回复(0)
whoway头像 whoway

这是一个求n个无差别的节点构成的二叉树有多少种不同的结构的问题。
我们假设n个无差别的节点构成不同的结构数为f(n)，f(0)表示空树,所以种数为1种。
计数原理进行分类：

  • 以第1个节点为头时,结构数为f(0)*f(n-1)//左子树是空树，右子树是n-1个点组成的子树
  • 以第2个节点为头时,结构数为f(1)*f(n-2)//左子树是1个点组成的子树，右子树是n-1个点组成的子树
  • 以3节点为头时,结构数为f(2)*f(n-3)
    etc.

显然，我们知道
f(0)=1,f(1)=1,f(2)=2,f(3)=5
然后我们可以由计数原理知道

卡特兰数的1个格式：

发表于 2020-07-05 22:50:39 回复(0)
royad头像 royad
A
发表于 2015-04-02 16:42:39 回复(1)
SadOnMyOwn头像 SadOnMyOwn
个人感觉30种更合适些。
发表于 2017-07-26 15:52:53 回复(2)
云云云一飞冲天头像 云云云一飞冲天
发表于 2022-08-22 13:20:13 回复(0)
wayToMaster头像 wayToMaster
我有一个问题哈，5的话是不是没有考虑到三个节点的不同顺序造成的二叉树不同。。。比如设三个节点分别是1，2，3； 则1->2->3 和 2->1->3 肯定不是一颗二叉树啊。。。没明白，求教
发表于 2021-01-31 10:16:37 回复(0)
葬爱家族小鑫鑫头像 葬爱家族小鑫鑫
单纯地考虑卡特兰数我觉得并不完全，和大家想法相似，唯一的前序可以确定五种二叉树，但是3个节点可以组合出6种前序，总是觉得不完全，更倾向于30种。
发表于 2019-04-14 17:02:48 回复(0)
IM_Rocket头像 IM_Rocket

我考虑的有点多了 我觉得三个节点确实是有五种形状的二叉树 但是每一种二叉树中节点的排列万一不同呢？ 那不是就更多种了吗？

发表于 2017-04-19 15:26:30 回复(0)
Useless Programmer头像 Useless Programmer
个人感觉应该是 五种形状的二叉树,对于这个问题,感觉最好的答案应该是 30. 三个节点列组合*五种不同的树形
发表于 2016-09-21 09:47:28 回复(0)
陌上花开头像 陌上花开
A
发表于 2014-10-15 14:34:40 回复(0)
提交观点

问题信息

阿里巴巴 树
上传者：二天
难度：
12条回答 10302浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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