n个结点最多可以构成的不同形态的树的个数¶

下面要讨论的是当给定 \(n（n>=0）\)个结点时，可以构建多少种形态不同的树。

如果两棵树中各个结点的位置都一一对应，可以说这两棵树相似。如果两棵树不仅相似，而且对应结点上的数据也相同，就可以说这两棵树等价。接下来我们讨论的，形态不同的树指的是互不相似的树。

对于任意一棵普通树，通过孩子兄弟表示法的转化，都可以找到唯一的一棵二叉树与之对应。所以我们研究的题目也可以转化成：\(n\)个结点可以构建多少种形态不同的二叉树。

每一棵普通树对应的都是一棵没有右子树的二叉树，所以对于\(n\) 个结点的树来说，树的形态改变是因为除了根结点之外的其它结点改变形态得到的，所以，\(n\) 个结点构建的形态不同的树与之对应的是 \(n-1\) 个结点构建的形态不同的二叉树。

如果 \(t_n\) 表示 \(n\) 个结点构建的形态不同的树的数量，\(b_n\) 表示 \(n\) 个结点构建的形态不同的二叉树的数量，则两者之间有这样的关系：\(t_n=b_{n-1}\)。

统计 n-1 个结点可以构建出多少形态不同的二叉树，有两种计算方案。

1.【方案1】：最直接的一种方法就是推理。当 \(n=0\) 时，只能构建一棵空树；当 \(n=2\) 时，可以构建 2 棵形态不同的二叉树，如图 1(A)；当 \(n=3\) 时，可以构建\(5\)棵形态互不相同的二叉树，如图 1(B)

对于具有\(n( n>1 )\)个结点的二叉树来说，都可以看成是一个根结点、由\(i\)个结点组成的左子树和由\(n-i-1\)个结点组成的右子树。

当 \(n=1\) 时，也适用，只不过只有一个根结点，没有左右孩子（\(i=0\)）。

可以得出一个递推公式:

\( \left\{\begin{matrix}b_0=1 & \\b_n=\sum_{i=0}^{n-1} b_ib_{n-i-1} & \end{matrix}\right. \)

例如，通过公式可以得出：

\(b_0 = 1\)

\(b1 = b_0b_0 = 1\)

\(b2 = b_0b_1+b_1b_0 = 2\)

\(b3 = b_0b_2+b_1b_1+b_2b_0 = 5\)

该递推公式就是卡特兰数，该公式的最终解为：\(b_n=\frac{C_{2n}^n}{n+1}\)

2.【方案2】：对于\(n\)个结点构建的二叉树，如果我们知道二叉树的前序序列和中序序列，就能唯一确定一棵二叉树。如下图所示为前序序列（1，2，3）构建的不同形态的二叉树，他们的中序序列各不相同。因此，不同形态二叉树的数目恰好就是前序序列一定的情况下，所能得到的不同中序序列的个数。

中序序列是对二叉树进行中序遍历得到的，遍历的过程本质就是对各个结点做进栈和出栈操作。因此计算中序序列的个数，就等价于将各个元素逐个入栈，然后在不同的时机出栈，统计各种情况的数量。

以 (1, 2, 3) 为例，各个元素进栈和出栈的情况如下图所示：

对于包含 \(n\) 个元素的数列，各个元素依次入栈，然后在不同时机出栈，各种情况的数量可以利用卡特兰数公式解决.

【结论】：通过以上两种方式。我们可以知道\(n\)个结点能构成的不同形态的二叉树的数量，再结合\(t_n=b_{n-1}\),我们就可以知道\(n\)个不同结点能构建的不同形态的树的个数。