二叉树是一棵非线性树形结构，具有以下特点：

每个结点最多有两个子树，称为左子树和右子树

非终端结点（非叶子结点）的度为 2

叶子结点的度为 0

二叉树的叶子结点是度为 0 的结点，即没有子树的结点。计算二叉树中叶子结点的数量对于二叉树的分析和应用至关重要。接下来，我们将介绍几种计算二叉树叶子结点数量的公式。

递归公式

对于一个非空二叉树，其叶子结点的数量可以通过以下递归公式计算：

```

叶子结点数量 = 若左子树为空，则 0，否则 左子树的叶子结点数量 + 若右子树为空，则 0，否则 右子树的叶子结点数量

```

该公式基于这样一个事实：非叶子结点的叶子结点数量为其左右子树的叶子结点数量之和，而叶子结点的叶子结点数量为 1。

层次遍历算法

层次遍历算法以宽度优先的方式遍历二叉树，可以用来计算叶子结点的数量。算法如下：

1. 将根结点放入队列中

2. 遍历队列，直到队列为空

3. 对于队列中的每个结点：

若该结点是叶子结点，则叶子结点数量加 1

若该结点不是叶子结点，则将该结点的左右子树（若存在）放入队列中

先序遍历算法

先序遍历算法以深度优先的方式访问二叉树中的每个结点，也可以用来计算叶子结点的数量。算法如下：

1. 访问根结点

2. 若根结点是叶子结点，则叶子结点数量加 1

3. 若根结点不是叶子结点，则先序遍历其左子树，再先序遍历其右子树

中序遍历算法

中序遍历算法以深度优先的方式访问二叉树中的每个结点，也可以用来计算叶子结点的数量。算法如下：

1. 中序遍历左子树

2. 访问根结点

3. 若根结点是叶子结点，则叶子结点数量加 1

4. 中序遍历右子树

后序遍历算法

后序遍历算法以深度优先的方式访问二叉树中的每个结点，也可以用来计算叶子结点的数量。算法如下：

1. 后序遍历左子树

2. 后序遍历右子树

3. 访问根结点

4. 若根结点是叶子结点，则叶子结点数量加 1

其他公式

除了上述递归公式和遍历算法外，还可以使用以下公式计算二叉树的叶子结点数量：

定理 1：对于一个有 n 个结点的二叉树，其叶子结点的数量等于 n/2（向下取整）

定理 2：对于一个有 n 个结点和 m 个叶子结点的二叉树，其度为 1 的结点数量等于 m - 1

练习

计算以下二叉树的叶子结点数量：

```

1

/ \

2 3

/ \ \

4 5 6

```

解：

使用递归公式：

左子树的叶子结点数量：1

右子树的叶子结点数量：2

叶子结点数量：1 + 2 = 3

也可以使用层次遍历算法、先序遍历算法、中序遍历算法或后序遍历算法来计算叶子结点数量。

应用

计算二叉树叶子结点数量在以下应用中很有用：

树表示：用于表示大数据集时的空间优化技术

存储管理：用于计算空闲内存块的数量

文件系统：用于计算文件系统中的空闲空间量

Huffman 编码：用于压缩数据