本文共 917 字，大约阅读时间需要 3 分钟。

背景

我们从一个简单的二叉树结构开始，该树的节点分为叶子节点（n0）、度为1的节点（n1）和度为2的节点（n2）。根据提供的示例图，n0=4，表示叶子节点有D、I、J、L四个；n1=2，表示度为1的节点有C、F两个；n2=3，表示度为2的节点有A、B、E三个。

在二叉树中，特殊的关系式之一是n0 = n2 + 1，这个公式揭示了二叉树节点分布的内在规律。为了深入理解这个公式，我们需要从不同的视角去探析二叉树的结构特性。

基本概念

• n0：表示叶子节点的数量，即出度为0的节点总数。
• n1：表示度为1的节点数量。
• n2：表示度为2的节点数量。
• N：总结点数，即所有节点的总和。

在二叉树中，经典公式 n0 = n2 + 1 被广泛应用于计算结构特性。同时，总节点数 N 可以通过 n0 + n1 + n2 计算得出。

证明

为了证明 n0 = n2 + 1，我们从边的数量入手，因为每条边都从一个结点引出，除了根节点。

1.1 从下往上看

叶子节点 (n0) 是树中的末尾，除了根节点之外，每个节点都是由一条边引出的。因此，总边数 N(总) 可以表示为：

N(总) = n0 + n1 + n2 - 1

这是因为根节点没有父节点，而其他所有节点都有一个父节点被边引出。

1.2 从上往下看

从根节点向下展开，我们可以将每种节点的子节点数乘以其数量，再求和得到总边数。叶子节点 n0 没有子节点，度为1节点 n1 有一个子节点，度为2节点 n2 有两个子节点。因此：

N(总) = n0 * 0 + n1 * 1 + n2 * 2

这样，我们就得到了另一种计算总边数的表达式：

N(总) = n1 + 2 * n2

将两个公式结合起来：

n0 + n1 + n2 - 1 = n1 + 2 * n2

两边同时减去 n1，得到：

n0 + n2 - 1 = 2 * n2

简化后：

n0 = n2 + 1

这证明了二叉树中叶子节点数量等于度为2节点数量再加1的关系。

结论

通过从边的数量和各类型节点的关系入手，我们成功证明了 n0 = n2 + 1 的结论。这一关系在分析和计算二叉树的结构特性时具有重要意义。

OVER

感谢您的阅读！