如何统计二叉树节点？并归纳定义内部节点计数函数nodecount(t)

嘿，我完全懂你的感受——明明对归纳定义和二叉树的概念都门儿清，但一要把二者结合起来定义计数函数，脑子就自动跳转到编程里的遍历逻辑，总觉得要写个“如果是叶子就停止”的流程对吧？别慌，咱们从归纳定义的核心逻辑出发，把这个事儿拆解明白，完全不用纠结编程那套过程化的思路。

要给计数函数做归纳定义，得先锚定二叉树本身的归纳定义——毕竟归纳定义都是基于结构的递归：

二叉树的归纳定义：

1. 基础情况：空树（记作$\emptyset$）是一棵二叉树；
2. 归纳步骤：如果$L$和$R$都是二叉树，$n$是一个节点，那么以$n$为根、$L$为左子树、$R$为右子树的结构$T=(n, L, R)$是一棵二叉树。

这个定义是咱们所有计数函数的基础，接下来的两个计数函数都是基于这个结构递推的。

先明确：内部节点是指有至少一个非空子树的节点（叶子节点是左右子树都为空的节点，不算内部节点）。

咱们直接对应二叉树的归纳结构来定义：

1. 基础情况：当$t$是空树$\emptyset$时，没有任何节点，自然内部节点数为0：
   $nodecount(\emptyset) = 0$
2. 归纳步骤：当$t$是一棵非空二叉树$t=(n, L, R)$时，分两种情况：
   • 如果$L$和$R$都是空树（也就是$n$是叶子节点）：这个节点不算内部节点，所以内部节点数等于左右子树的内部节点数之和，也就是$nodecount(t) = nodecount(L) + nodecount(R) = 0 + 0 = 0$；
   • 如果$L$或$R$至少有一个非空（也就是$n$是内部节点）：此时内部节点数要算上根节点$n$本身，再加上左右子树的内部节点数，即$nodecount(t) = 1 + nodecount(L) + nodecount(R)$。

你也可以把归纳步骤合并成更简洁的统一表述，不用拆分情况：
对于非空树$t=(n,L,R)$，
$$nodecount(t) = \begin{cases}
0 & \text{若 } L=\emptyset \text{ 且 } R=\emptyset \
1 + nodecount(L) + nodecount(R) & \text{否则}
\end{cases}$$

举个小例子验证：比如一棵根节点为A，左子树是叶子B，右子树为空的树。按照定义：
$nodecount(A,B,\emptyset) = 1 + nodecount(B,\emptyset,\emptyset) + nodecount(\emptyset) = 1 + 0 + 0 = 1$——正好对应内部节点只有A的情况，完全正确。

总节点数就是所有节点的数量（不管是内部节点还是叶子），这个定义更直观，直接基于二叉树的结构递推：

1. 基础情况：空树的总节点数为0：
   $totalcount(\emptyset) = 0$
2. 归纳步骤：对于非空树$t=(n,L,R)$，总节点数等于根节点的1个，加上左右子树的总节点数：
   $totalcount(t) = 1 + totalcount(L) + totalcount(R)$

还是用刚才的例子验证：$totalcount(A,B,\emptyset) = 1 + totalcount(B,\emptyset,\emptyset) + totalcount(\emptyset) = 1 + 1 + 0 = 2$——对应A和B两个节点，完全正确。

你之前总是联想到编程的遍历逻辑，其实这俩是对应的，但核心视角不一样：

• 编程里的递归遍历是过程性的，它告诉你“怎么一步步算出结果”（比如先遍历左子树，再遍历右子树，累加计数）；
• 而归纳定义是描述性的，它只定义“每个结构的树对应的函数值是什么”，不关心计算的过程——比如它只说“非叶子树的内部节点数是1加左右子树的内部节点数”，至于你是先算左还是右，甚至有没有办法算，它不关心，这是数学层面的定义。

这样是不是就把归纳定义和二叉树的结合点理清楚了？

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