【证明题】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。

一棵有n(n>0）个结点的满二叉树共有多少个非终端结点

在一颗满二叉树中，所有节点都被完全填充，并且除了最后一层外，每一层都尽可能地填满了节点。对于满二叉树，如果有 n 个节点，我们可以这样计算非终端节点的数量：

- 当 n = 1 时，这是一棵只有一个根节点的树，所以没有子节点，即没有非终端节点。
- 对于 n > 1 的情况，由于它是满二叉树，第 i 层（从 1 开始计数）将有 2^(i-1) 个节点。满二叉树的最后一层（即第 k 层，使得 2^(k-1) <= n < 2^k）的所有节点都是终端节点，因为没有更多的空间放子节点了。那么前 k-1 层的节点都是非终端节点。

非终端节点总数等于所有非最后层节点数之和，即：

非终端节点数 = Σ(2^(i-1)) for i from 1 to k-1
              = 2^0 + 2^1 + ... + 2^(k-2)
              = 2^(0+1+...+(k-2)) (因为这是一个等比数列求和公式)
              = 2^(k-1) - 1

因此，对于任意给定的 n，非终端节点的数量就是 2^(k-1) - 1，其中 k 满足 2^(k-1) <= n < 2^k。