【ROSALIND】【练Python，学生信】35 二叉树的内结点数量

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

题目：

计算系统发生祖先数（Counting Phylogenetic Ancestors）

Given: A positive integer n (3≤n≤10000).

所给：一个正整数n，大小在3到10000之间。

Return: The number of internal nodes of any unrooted binary tree having n leaves.

需得：有n个叶子结点的二叉树包含的内节点的数量。

测试数据

4

测试输出

2

生物学背景

        在之前的问题中，我们考虑用树来描述生物进化，但具体使用哪种树并未确定。根据达尔文的进化学说，新物种通常是在旧有物种的一部分与原物种隔离一段时间后，变化积累产生的。在这种理论下产生的进化树中，内节点代表着进化的分枝点，在这里旧物种演变成一个新物种或进化为两个新物种。这种进化方式很适合用二叉树来表示。

数学背景

        二叉树是每个结点最多有两个子树的树结构，即每个节点的度都不能超过3。有根数是有根节点的数，而无根树没有根结点。有根数根结点的度为2，其他内结点的度为3，而无根树所有内结点的度都为3。

思路

        这道题我是用画图解决的。

        有4个叶子结点时：

        显然有两个内节点。

        再加入一个结点，叶子结点数量仍然为4，内结点数量也仍为2：

        再添加一个结点，使叶子结点的数量达到5，此时有3个内结点：

        再加一个结点，叶子结点的数量为5，有3个内结点：

        再加一个结点，有6个叶子结点，4个内结点：

        ……

        以此类推，可以看到内结点总比叶子结点少两个，所以只要用给的叶子结点数减去2即为内结点数。

        当然，只用画图的方法近于作弊，怎么推导呢？有人给出了如下证明：

        假设一个无根二叉树有N个结点，则必有N-1个边，且1个边对应2个度。假设k是内结点的数目，n是叶子结点的数目，内结点度为3，叶子结点度为1。又因为无根二叉树只有内结点和叶子结点，则可以写出等式：3k+n = 2((k+n)-1)，整理的k=n-2。

代码

        这是一道难得的不需要编程的题，解完题后我浏览了一下讨论区，发现一片欢乐。其中有一评论放在这里非常合适：“No computer program involved unless you can't subtract two in your head.”