【证明题】5.2 定义满二叉树的每一个结点或者是一个分支结点，并恰好有两个非空子结点；或者是叶结点。 定义一个结点的度为其非空子结点的数目。作为满二叉树定理的推论，证明任何一棵二叉树中度为2的结点的数目为叶结点数目减1。

证明：

设二叉树中度为2的结点数目为n，叶结点数目为m。

首先，根据满二叉树的定义可知，满二叉树中的所有结点的度均为2。因此，对于任意一棵满二叉树，其度为2的结点数目为叶结点数目减1，即n=m-1。

接下来，我们考虑一般的二叉树。对于任意一棵二叉树，可以通过添加虚拟结点使其成为满二叉树。具体来说，对于任意一个度为1的结点，我们可以在其下面添加一个空结点作为其第二个子结点，使其成为度为2的结点。这个过程可以一直进行下去，直到最后得到一棵满二叉树。

我们假设在添加虚拟结点的过程中，度为2的结点数目增加了k个。由于每次添加虚拟结点都是在度为1的结点下方添加的，因此每次添加之后叶结点数目增加1，即m'=m+k。同时，由于每次添加虚拟结点都将一个度为1的结点变成了度为2的结点，因此度为2的结点数目也增加了k，即n'=n+k。

根据上面的推理，我们可以将原二叉树分解为两部分：一部分是满二叉树，其度为2的结点数目为m-1；另一部分是添加了虚拟结点的部分，其度为2的结点数目为n'。因此，原二叉树的度为2的结点数目为n=n'-k，叶结点数目为m=m'-k。将其代入n=m-1，得到n'=(m-1)+k，即原二叉树中度为2的结点数目为叶结点数目减1。证毕。

相关问题

5.2 定义满二叉树的每一个结点或者是一个分支结点，并恰好有两个非空子结点；或者是叶结点。 定义一个结点的度为其非空子结点的数目。作为满二叉树定理的推论，证明任何一棵二叉树中度为2的结点的数目为叶结点数目减1。

证明：

设一棵二叉树的叶结点数目为n，度为2的结点数目为m，则该树共有n+m个结点。

由于满二叉树的每个结点要么有两个非空子结点，要么是叶结点，因此一棵满二叉树的度为2的结点数目为n-1。

考虑将一棵任意的二叉树转化为一棵满二叉树，可以发现每次添加一个新的结点，都会增加一个度为1的结点和一个度为0的结点（即叶结点）。因此，将n个叶结点连成一条链，再在链上添加m个度为1的结点，即可得到一棵满二叉树。

由于每次添加一个度为1的结点，都会增加一个度为2的结点，因此度为2的结点数目为m=n-1。

综上所述，任何一棵二叉树中度为2的结点的数目为叶结点数目减1。