二叉树问题

二叉树是数据结构中的一个重要概念，如果二叉树非空的话，那么每一棵二叉树必有一特定的结点，称作根结点（root）。根结点及之下的每个结点均可以有不超过两个的子结点（也可以没有）。图4.13所示的4棵树中，每个结点的子结点都不超过2个，所以它们均为二叉树。69J100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

图4.1369J100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

试求N（1≤N≤25）个结点（每一个结点都是等价的）可组成多少个不同二叉树？69J100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入

输入有多组数据，每组输入一个整数N，表示有N个结点。69J100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出

每组数据输出一行，即输出一个整数，表示组成的不同二叉树个数。69J100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

样例

输入

3

输出

5

提示

3个结点组成的5个不同的二叉树如图4.14所示。69J100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库