由3个结点可以构造出多少种不同的二叉树

发布网友发布时间：2022-04-22 01:24

共3个回答

热心网友时间：2023-10-06 08:44

由3个结点可以构造出5种不同的二叉树

热心网友时间：2023-10-06 08:44

能组成5种形态的二叉树。
n个节点能组成多少种二叉树，百度文库里有这么一道公式
思想：递归+组合
当n=1时，只有1个根节点，则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为h(n)，
则h(1)=1;
当n=2时，1个根节点固定，还有n-1个节点，可以作为左子树，也可以作为右子树，
即：h(2)=h(0)*h(1)+h(1)*h(0)=2，则能组成2种形态的二叉树。这里h(0)表示空，所以只能算一种形态，即h(0)=1;
当n=3时，1个根节点固定，还有n-1=2个节点，可以在左子树或右子树，
即：h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5，则能组成5种形态的二叉树。
以此类推，当n>=2时，可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)种。
即符合Catalan数的定义，可直接利用通项公式得出结果。
递归式：
h(n)=h(n-1)*(4*n-2)/(n+1);
该递推关系的解为：
h(n)=C(2n,n)/(n+1)(n=1,2,3,...)

热心网友时间：2023-10-06 08:45

一共五种，如图