设T是至少有两个顶点的树，证明如果T是一个完整的二叉树，那么T的叶子数正好比内部顶点数（非叶子顶点）多一个

我们可以使用数学归纳法来证明这个结论。

当T只有两个顶点时，结论显然成立。

假设当T有n个顶点时结论成立，现在考虑T有n+1个顶点的情况。

由于T是一棵完整的二叉树，所以T的根节点有两个子节点。我们可以将这两个子节点看成两棵子树，分别记作T1和T2。由于T是一棵树，且T1和T2的顶点之间没有交集，所以T1和T2的并集加上根节点构成了T。

根据归纳假设，T1和T2的叶子数分别为i和j，其中i和j分别比T1和T2的内部顶点数（非叶子顶点）多一个。因此，T1和T2的内部顶点数之和为i+j-2。

T的内部顶点数为T1和T2的内部顶点数之和再加1（根节点）。因此，T的内部顶点数为i+j-1。

T的叶子数为T1和T2的叶子数之和。因此，T的叶子数为i+j。

将T的内部顶点数和叶子数代入结论中，得到：

T的叶子数正好比内部顶点数（非叶子顶点）多一个。

因此，当T有n+1个顶点时，结论也成立。根据数学归纳法原理，结论对于所有至少有两个顶点的完整二叉树都成立。

相关问题

练习3。二叉树是一种有根的树状结构，其中每个顶点最多有两个子节点，并且顶点的每个子节点都被指定为其左子节点或右子节点。未展开树的叶子是顶点阶为1的节点。注意，对于有根树，根顶点通常不被视为叶，而所有阶为1的其他节点都被视为。全二叉树是指每个节点都有零个子节点或两个子节点的二叉树。 1） 画一个有七个顶点、只有一片叶子的二叉树。 2） 绘制一个有七个顶点和尽可能多的叶子的二叉树。 3） 设T是一个至少有两个顶点的树，证明如果T是全二叉树，则 T的叶的数目恰好比内部顶点（非叶顶点）的数目多一个。

1） 以下是一个有七个顶点、只有一片叶子的二叉树：

          o
         / \
        o   o
       / \
      o   o
     / \
    o   o
   /
  o

2） 以下是一个有七个顶点和尽可能多的叶子的二叉树：

          o
         / \
        o   o
       / \   \
      o   o   o
     / \   \
    o   o   o

3） 设T是一个至少有两个顶点的树，证明如果T是全二叉树，则 T的叶的数目恰好比内部顶点（非叶顶点）的数目多一个。

证明：

对于一个全二叉树T，设其叶子节点数为L，内部节点数为I。

我们可以通过数学归纳法来证明：T的叶的数目恰好比内部顶点（非叶顶点）的数目多一个。

当T只有两个顶点时，显然成立。

假设对于任意一个全二叉树，当其顶点数小于n时，该结论均成立。

现在考虑一个顶点数为n的全二叉树T。设其左子树有L1个叶子，右子树有L2个叶子，左子树和右子树的内部节点数分别为I1和I2。

则有：

- L = L1 + L2 （全二叉树的叶子节点数等于左子树和右子树叶子节点数之和）
- I = I1 + I2 + 1 （全二叉树的内部节点数等于左子树和右子树内部节点数之和再加上根节点）

由于T是全二叉树，左子树和右子树都是满二叉树（所有节点都有两个子节点），因此有：

- L1 = I1 + 1 （左子树的叶子节点数等于内部节点数加一）
- L2 = I2 + 1 （右子树的叶子节点数等于内部节点数加一）

将上述三个式子代入第一个式子得：

L = L1 + L2 = (I1 + 1) + (I2 + 1) = I + 2

将上述三个式子代入第二个式子得：

I = I1 + I2 + 1 = (L1 - 1) + (L2 - 1) + 1 = L - 1

因此，T的叶的数目恰好比内部顶点（非叶顶点）的数目多一个。

证毕。

证明每个包含k次顶点的树至少包含k个叶子

首先，我们定义一个叶子节点为一个度数为1的节点。因为树是一个连通的无向图，所以每个树至少有两个叶子节点。我们需要证明每个包含$k$次顶点的树至少包含$k$个叶子。

我们使用归纳法来证明这个结论。对于$k=2$的情况，显然成立，因为包含2个顶点的树只有1条边，两个顶点都是叶子节点。

现在假设对于$k=m$的情况，每个包含$m$次顶点的树至少包含$m$个叶子节点，现在我们证明对于$k=m+1$的情况也成立。

考虑一个包含$m+1$个顶点的树$T$，我们选择一条最长的路径$P$，它连接了两个叶子节点。因为$P$是最长的路径，所以它的端点不可能是叶子节点，即$P$的两个端点至少有一个度数大于1。我们选择其中一个度数大于1的端点$v$，它肯定有一个子节点$u$。我们将$v$和$u$之间的边删除，得到两个子树$T_1$和$T_2$，它们的顶点数分别为$k_1$和$k_2$，满足$k_1+k_2=m+1$。

因为$v$的度数大于1，所以$v$不是叶子节点，因此$T_1$和$T_2$中至少有一个包含$v$。不失一般性，我们假设$T_1$包含$v$。因为$v$的度数为$d_v>1$，所以$T_1$至少包含$d_v$个顶点，而$v$和$u$是被删除的两个顶点，因此$T_1$包含$k_1-d_v+1$个顶点。根据归纳假设，$T_1$至少包含$k_1-d_v+1$个叶子节点。同时，$T_2$中至少包含$k_2$个叶子节点。因此，$T$中至少包含$k_1-d_v+1+k_2=m+1$个叶子节点。

因此，我们证明了对于任何$k\geq2$，每个包含$k$次顶点的树至少包含$k$个叶子节点。