4个结点可构造出多少个不同的树形，二叉树计算的全部公式是什么

按照 卡特兰数 公式：f(n)= (2*n)!/ (n!* (n+1)！），为阶乘。故此， f(4) = 14。具有4个节点的普通树有14中形态。

（1) 在二叉树中，第i层的结点总数不能超出2^(i-1)；

(2) 深度为h的二叉树多有2^h-1个结点(h=1)，少有h个结点；

(3) 针对任意一棵二叉树，假设其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为int（log2n）+1；

(5)有N个结点的完全二叉树各结点假设用顺序方法存储，则结点当中有请看下方具体内容关系：

若I为结点编号则 假设I1，则其父结点的编号为I/2；

假设2*I=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*IN，则无左儿子；

假设2*I+1=N，则其右儿子的结点编号为2*I+1；若2*I+1N，则无右儿子。

(6)给定N个节点，能构成h(N)种不一样的二叉树。h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。

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

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

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

二叉排序树又叫二叉查找树或者二叉搜索树，它第一是一个二叉树，而且，一定要满足下面的条件：

1）若左子树不空，则左子树上全部结点的值均小于它的根节点的值；

2）若右子树不空，则右子树上全部结点的值均大于它的根结点的值；

3）左、右子树也分别是二叉排序树。

若一个结点有子树，既然如此那，该结点称为子树根的“双亲”，子树的根称为该结点的“孩子”。有一样双亲的结点互为“兄弟”。一个结点的全部子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的全部结点都是该结点的祖先。

结点的度：结点拥有的子树的数目。

叶子结点：度为0的结点。

分支结点：度不为0的结点。

树的度：树中结点的大的度。

层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1。

树的高度：树中结点的大层次。

森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

卡特兰数列是组合数学中一个常出现在->各自不同的计数问题中产生的数列，其前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, …

卡特兰数第一是由欧拉在计算对凸 n 边形的不一样的对角三角形剖分的个数问题时得到的，也就是在一个凸 n 边形中，通过不相交于 n 边形内部的对角线，把 n 边形拆分成若干三角形，不一样的拆成绩目用 Hn 表示，Hn 即为卡特兰数。

给定N个节点，能构成h(N)种不一样的二叉树。h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。

这个卡特兰数的量级估计方式其实是非常基础、非常简单的，看到其他回答已经有不错的方式了，再补充一个比较直接的。从卡特兰数定义

对阶乘和阶乘的商的估计大多数情况下来说就是Stirling公式（精确也实质）、均值不等式（同样可以将连乘放缩到指数，但不是很精确）、分奇偶项分别处理，这里用第三种方式：

第一n=0时目标不等式的等号成立，考虑 时，有

这里 直到1或者2为止，其实就是常说的将分子的阶乘拆成了奇数的乘积与偶数的乘积。这当中偶数的乘积比较容易想到，可以每一项提出一个2，其实就是常说的

奇数的乘积没有这么好处理，但可以比较容易将它放缩到偶数的乘积：

于是有

那左边咋办，应该如何处理呢？实际上很简单，奇数可以放大，自然也可变小，往下调整一级就行了：

因为这个原因有 时

再结合n=0的情况完全就能够清楚不等式成立了。