软件设计师：具有3个节点的二叉树有5种，可推测出具有4个节点的二叉树有几种？推测方式详解

具有3个节点的二叉树有5种，可推测出具有4个节点的二叉树有几种？如果是三个以下的节点还能用画图的方式推测出来，但是一旦超过三个节点用画图的方式推测起来就比较费时费力了，下面我给宝子们总结了推测规律，根据这个规律来推测就省心多啦~

>>首先我们来推测一下具有2个节点的二叉树有几种，如下图所示

第一种：左子树为1，右子树为0，情况为1

第二种：左子树为0，右子树为1，情况为1

总结：具有2个节点的二叉树有两种

>>接下来，推测一下具有3个节点的二叉树有几种，如下图所示

总结：第一种情况，左节点为2右节点为0（左右节点数量相加等于总节点数减一）的情况为两种；右节点为2左节点为0的情况为两种；左右节点各为1的情况为一种。所以具有3个节点的二叉树有5种。我们用表格来记录一下：

计算公式为：2*1+1*2+1*1

>>根据以上规律，已知具有3个节点的二叉树有5种，可推测出具有4个节点的二叉树有几种

计算公式为：5*1+1*5+2*1+1*2

>>根据以上规律，已知具有3个节点的二叉树有5种，具有4个节点的二叉树有14种,可推测出具有5个节点的二叉树有几种

计算公式为：14*1+1*14+5*1+1*5+2*2

>>根据以上规律，已知具有3个节点的二叉树有5种，具有4个节点的二叉树有14种,具有5个节点的二叉树有42种，可推测出具有6个节点的二叉树有几种

计算公式为：42*1+1*42+14*1+1*14+5*2+2*5