完全二叉树的叶子节点数

给定一个完全二叉树，公有840个节点，求叶子节点的个数。对于这样一个题目，我们要推导一个推论来计算。

基本概念

首先，我们需要掌握基本概念，掌握二叉树、完全二叉树的概念，否则无法区分，这里不再赘述。

接着，需要引入一个在图中常用，在树中不常用的概念：度。可以仿借图的出度来定义理解，二叉树的度指该节点引出的边数(节点下面的边)，也即节点的子节点树。那么二叉树有3种度：

• n0: 度为0，即为叶子节点数量。
• n1: 度为1，即为只有左子树或者右子树的节点数量，对于完全二叉树，只可能存在一种情况，节点数为奇数时有一个节点只有一个左子树，所以n1 = 0 or 1。
• n2:度为2，即有左右节点的节点数量。

引理 n0 = n2 + 1

证明：

• 假设树的节点数是n，那么n = n0 + n1 + n2。
• 按照入度考虑一下(节点上面的边)，除了根节点，每个节点都有一条入边，所以边数为n-1；而边的数量为2*n2 + n1
• 结合上面两个推导: n = n0 + n1 + n2 = 2*n2 + n1 + 1，化简得到n0 = n2 + 1

推理 n0 = n/2 or (n-1)/2

证明：

• 由于n = n0 + n1 + n2，而n0 = n2 + 1，所以n = 2n0 + n1 - 1
• 对于完全二叉树，如果n为偶数，说明不存在只有子节点的节点，n1 = 0, n0 = (n+1)/2；如果n为奇数，说明存在1个只有左子节点的节点，那么n1 = 1, n0 = n/2。可以合并为n0 = (n+1)/2。

小结

根据结论n0 = (n+1)/2， 所以结果为420。在整个过程中，我们不需要去记忆结论，而是记住推理的过程，这样就是利用第一性原理在学习。