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

一棵有124个结点的完全二叉树，其叶结点个数是确定的

### 回答1：
一棵有124个结点的完全二叉树，其叶结点个数是62个，因为完全二叉树的叶结点只可能在最后一层或者倒数第二层，而最后一层的结点数为2的k次方（k为层数），倒数第二层的结点数为2的k-1次方。根据这个规律，可以算出这棵完全二叉树的层数为7层，最后一层有64个结点，倒数第二层有32个结点，因此叶结点个数为64+32=96个。但是由于完全二叉树的性质，如果最后一层的结点数不足2的k次方，那么缺少的结点会从左侧开始依次填补，因此这棵完全二叉树最后一层只有62个结点，叶结点个数也就是62个。

### 回答2：
完全二叉树是指除了最后一层外所有层的节点数量都达到最大值，并且最后一层的节点都靠左排列的二叉树。因此，一棵有124个结点的完全二叉树的层数可以通过公式计算得出：

设该二叉树的深度为d，则其最后一层的节点数量为n，其它层的节点数量为2^d-1个，因此有：

2^d-1+n=124

由于叶结点没有左右子树，所以最后一层都是叶结点，即n=2^(d-1)。将n代入上式中，得：

2^d-1+2^(d-1)=124

化简得：

2^d=64

因此，d=log2 64=6，即该二叉树共有6层。

叶结点是指没有子节点的节点，因此最后一层的所有节点都是叶结点。根据完全二叉树的定义可知，除最后一层外，其它层的节点数量都达到最大值，叶结点只能在最后一层。由于该二叉树共有6层，因此最后一层有2^5=32个节点，即该完全二叉树的叶结点个数是32个，是确定的。

综上，一棵有124个结点的完全二叉树，其叶结点个数确定为32个。

### 回答3：
一棵完全二叉树是指除了最后一层之外，其它的每一层都是满的二叉树。一个完全二叉树的叶结点一定在最后一层，而且只能在最后一层，因此，叶结点的个数是可以被确定的。

首先，对于一棵二叉树来说，其叶结点的个数等于其度为2的结点数加1。因为在二叉树中，每个结点都有两个子结点，而叶结点没有子结点，因此只有度为2的结点才能够成为叶结点的父结点。而在完全二叉树中，除了最后一层之外的所有层都是满的，所以所有度为2的结点都有两个子结点，即它们不可能是叶结点。因此，在完全二叉树中，叶结点的个数等于最后一层中的结点数。

其次，根据完全二叉树的性质，最后一层的结点数是小于等于总结点数的一半的。因为一棵有124个结点的完全二叉树，如果最后一层的结点数不足62个，那么其不可能是完全二叉树，因为在完全二叉树中，最后一层缺失的结点必须全部位于右侧，否则该树将不再满足完全二叉树的定义。同时，在最坏情况下，最后一层的结点数也不会超过62个，因为如果最后一层有超过62个的结点，那么它们的父结点就不可能在倒数第二层，因此该树也不再满足完全二叉树的定义。

综上所述，一棵有124个结点的完全二叉树的叶结点个数一定在31个到62个之间。