如何用归纳法证明非空二叉树节点数与链接数的关系？

别慌！好久没碰归纳法确实容易卡壳，我帮你把这道题的证明拆解清楚，包括你纠结的“链接”怎么定义，一步步来～

先明确术语：什么是“链接”？ #

咱们先把概念统一，避免歧义：这里的链接就是二叉树中父节点指向子节点的边——简单说，每一个非叶子节点如果有左孩子，就对应1条左链接；有右孩子就对应1条右链接；叶子节点（没有孩子）的链接数是0。整个树的总链接数就是所有节点的链接数之和（或者说所有边的总数）。

步骤1：基础情况验证 #

从最简单的非空二叉树开始：只有1个根节点，没有任何子节点。

• 节点数 ( n = 1 )
• 总链接数 ( e = 0 )
  代入公式：( 1 = 0 + 1 )，完全成立。

步骤2：归纳假设 #

假设所有节点数为k的非空二叉树都满足公式：( 节点数 = 链接数 + 1 )，也就是 ( k = e_k + 1 )（其中 ( e_k ) 表示节点数为k的树的总链接数）。

步骤3：归纳步骤（核心证明） #

现在要证明：当二叉树的节点数为 ( k+1 ) 时，公式依然成立。

我们可以换个思路：任意一个有 ( k+1 ) 个节点的非空二叉树，一定存在至少一个叶子节点（没有孩子的节点）。我们把这个叶子节点连同它和父节点之间的那条链接一起去掉，就得到了一个有k个节点的二叉树。

根据归纳假设，这个k节点的树满足 ( k = e_k + 1 )。那我们再看原来的 ( k+1 ) 节点树：

• 节点数：( k + 1 )（比k节点树多了1个叶子节点）
• 总链接数：( e_k + 1 )（比k节点树多了1条刚才去掉的链接）

把链接数代入公式右边：( (e_k + 1) + 1 = e_k + 2 )
而根据归纳假设 ( k = e_k + 1 )，所以 ( e_k = k - 1 )，代入上式得：( (k - 1) + 2 = k + 1 )，刚好等于原来树的节点数。

这就证明了：如果节点数为k的树满足公式，那么节点数为 ( k+1 ) 的树也满足公式。

额外补充：换一种构建视角理解 #

如果从“从小到大构建树”的角度看：给任意一个k节点的树的某个叶子节点添加左/右孩子，会新增1个节点和1条链接。

• 新节点数：( k + 1 )
• 新链接数：( e_k + 1 )
  根据归纳假设 ( k = e_k + 1 )，新节点数 ( k+1 = (e_k +1) +1 = (e_k +1) +1 )，而新链接数+1也是 ( (e_k+1)+1 = e_k+2 )，两者完全相等，等式依然成立。两种视角都能验证结论。

内容的提问来源于stack exchange，提问作者Evan