【ROSALIND】【练Python，学生信】67 无根二叉树的数目

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面  谢谢配合~

题目：

无根二叉树的数目（Counting Unrooted Binary Trees）

Given: A positive integer n (n≤1000).

所给：一个不大于1000的整数n。

Return: The value of b(n) modulo 1,000,000.

需得：b(n)的值，对1,000,000取模。

测试数据

5

测试输出

15

背景

        在55 创建字符表中我们知道，从一棵树上删除一条边，就会产生两棵独立的树，每棵树都是原始树的子集，可以用S∣Sc表示这种树的分裂。我们也可以用这种分裂集合来唯一的表示一棵无根二叉树。

        在本题中，我们想要知道在有n个叶子结点的情况下，一共有多少课不同的无根二叉树。为了解决这个问题，我们首先要定义何为“相同”的无根二叉树，具有相同分裂的两棵树即为“相同的无根二叉树”，反之，如果两棵树的分裂是不同的，则被认为是“不同的无根二叉树”。

        在本题中，我们定义b(n)表示具有n个叶子结点的的不同无根二叉树的总数。

思路

        对于生物专业的同学，本题题目可能相当难懂。总结来说，题目会给我们叶子结点的数量，我们来回答具有这些叶子的无根二叉树一共有多少棵。接下来我们会将解题步骤分解，并绘图来帮助理解。

（1）理解一棵有n个叶子结点的无根二叉树肯定有2n-3条边；

        由无根二叉树的特点可知，一个结点要么度为3（内结点），要么度为1（叶子节点）。

有3个叶子结点的树：

        有4个叶子结点的树，其中一种情况为：

        有5个叶子结点的树，其中一种情况为：

        叶子结点更多的情况也可以以此类推，边满足2n-3。

（2） 把一个新结点通过一条边连在现有的边上，我们就可以得到一棵新的无根二叉树；除了这种办法以外，没有其他连接新结点的方法。

        举个例子，我们向有3个叶子结点的那棵树添加一个新结点，操作过程如下：

        画图可知，这是唯一的添加新结点方法，其他方法无法满足无根二叉树的定义。

（3）可能具有n片叶子的树的数量是具有n-1片叶子的树的数量的2(n-1)-3倍；

        在进化树中，每一片叶子结点都代表一个不同的种属，因此在每个边上添加新结点都会产生一个不同的进化树。由于有n-1个叶子结点的树有2(n-1)-3条边，因此每棵树添加一个结点都可以产生2(n-1)-3个新的树，再乘上n-1个叶子结点的树的数目，就得到了有n片叶子的树的数量。

        经过以上三步可以看到我们得到了一个递归，有n片叶子的树的数量由有n-1个叶子结点的树的数目决定，即b(n)=[2(n-1)-3]*b(n-1)。

        因为只有一棵有3片叶子的树，所以最终的公式为T(n)=1⋅3⋅…(2n−5)=(2n−5)!!

        想明白这个过程，代码就非常简单啦，甚至都不需要有注释~

代码