练习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的叶的数目恰好比内部顶点（非叶顶点）的数目多一个。

证毕。