叶节点的数量比度为2的节点数量多一个

叶节点的数量比度为2的节点数量多一个

Content #

对任何一棵二叉树,如果其叶节点数量为n0​,度为 2 的节点数量为n2​,即:n0​=n2​+1。

除了叶节点(度为 0),其他的节点度数要么为 1 要么为 2,如果假设度为 1 的节点数量是 n1​,那么该二叉树的节点总数量 n = n0​ + n1​ + n2​。

再算一算节点的总度数,节点的总度数应该等于 2*n2​ + n1​。

由于,节点的总数量 = 节点的总度数 + 1,就有:

节点总数量 n = 2*n2​ + n1​+ 1。

结合刚才的节点总数量式子,可以得到:n0​ + n1​ + n2​ = 2n2​ + n1​+ 1。

两边同时减少一个 n1​ 和一个 n2​,不难得到:n0​ = n2​ + 1。

Viewpoints #

From #

10|二叉树:二叉树到底长什么样子?