Question

二叉树是重要的数据结构，五个点的不同的二叉树有几个？

二叉树是重要的数据结构，五个点的不同的二叉树有几个？

Answer 1

五个点的不同的二叉树有42个。含有n个节点的二叉树的不同形式共有1/(n+1) * C(2n,n)个。所以5个点有42种（左4或右4或左3右1或左1右3或左2右2， 14+14+5+5+2*2=42)。

一个有n个结点的二叉树可以看作由三个部分组成，一个根结点，一个含i个结点的左子树，一个含n-i-1个结点的右子树，其中i的取值为0到n-1。

设所求的不相似二叉树有bn种，其中n是下标为结点的个数，

则b0=1(空二叉树） ，

b1=1(一个根结点），

b2=2(一种只有左子树，另一种只有右子树） ，

更一般的表达式为 ：

bn = 1, 当n=0时 ，

= b0*bn-1 + b1*bn-2 + ... + bn-1*b0, 当n>=1时 。

扩展资料

有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量。

类型：

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

参考资料来源：百度百科-二叉树

Answer 2

2个点有2种（根有左儿子或者根有右儿子）
3个点有5种（左边2个结点或者右边2个结点或者左右各一结点, 2+2+1=5)
4个点有14种（左边3个结点或者右边3个结点或者左1右2或者左2右1 , 5+5+2+2=14)
5个点有42种（左4或右4或左3右1或左1右3或左2右2， 14+14+5+5+2*2=42)