首页 > 试题广场 >

一个具有3个节点的二叉树可以有()种形态。

[填空题]
一个具有3个节点的二叉树可以有1种形态。
推荐
答案:5
这里将三个节点分别表示为A,B,C。(ABC等价,不做区分),假设A为 root
第一种情况:B是A的左孩子,C是A的右孩子
第二种情况:B是A的左孩子,C是B的左孩子
第三种情况:B是A的左孩子,C是B的右孩子
第四种情况:B是A的右孩子,C是B的右孩子
第五种情况:B是A的右孩子,C是B的左孩子
编辑于 2015-02-02 11:24:18 回复(0)
答案:5
求卡特兰数:h(n)=C(n, 2n)/(n+1),代入3解得h(3)=5
发表于 2015-08-03 16:32:21 回复(0)
Catalan数

发表于 2016-08-17 22:35:05 回复(0)
可以把非线性的树问题看成栈的问题,3个数进入栈,出来的结果又五种情况,所以5.
发表于 2015-10-13 15:47:32 回复(1)

发表于 2015-11-15 22:42:18 回复(0)

又学到一些知识
发表于 2017-03-16 15:07:19 回复(0)
学习新公式,m=C(n,2n) /(n+1)
发表于 2017-03-02 09:27:04 回复(0)
记n个节点的二叉树形态个数为A[n]

1)0个节点的二叉树只有1种形态,A[0]=0;1个节点的二叉树只有1种形态,A[1]=1
2)n个节点(n>=2)的二叉树有 A[n] = ∑ [m=0到n-1] ( A[m]*A[n-m-1] ) ,求和的每一项,分别表示根的左子树为m个节点、右子树为 n-m-1个节点的情况

刚好就是catalan数,直接用catalan数的公式:h(n)=C(2n,n)/(n+1)
发表于 2016-10-24 15:01:30 回复(0)
5种
发表于 2015-09-11 15:56:35 回复(0)
设具有N个节点的二叉树的形态有f(N)种,则f(0)=0,f(1)=1
具有3个节点的二叉树,包含一个根节点与2个子节点,可以分以下几类:
左子树0个节点,右子树2个节点,此时二叉树的形态有f(0)+f(2)
左子树1个节点,右子树1个节点,此时二叉树的形态有f(1)
左子树2个节点,右子树0个节点,此时二叉树的形态有f(2)+f(0)
故f(4)=2f(0)+f(1)+2f(2)
f(2)=2f(0)+2f(1)=2
所以f(4)=5,即具有3个节点的二叉树有5种.
发表于 2015-08-11 10:23:13 回复(0)
4
发表于 2015-05-24 00:27:12 回复(1)