給定一個完全二叉樹，公有840個節(jié)點(diǎn)，求葉子節(jié)點(diǎn)的個數(shù)。對于這樣一個題目，我們要推導(dǎo)一個推論來計(jì)算。
基本概念
首先，我們需要掌握基本概念，掌握二叉樹、完全二叉樹的概念，否則無法區(qū)分，這里不再贅述。
接著，需要引入一個在圖中常用，在樹中不常用的概念：度。可以仿借圖的出度來定義理解，二叉樹的度指該節(jié)點(diǎn)引出的邊數(shù)(節(jié)點(diǎn)下面的邊)，也即節(jié)點(diǎn)的子節(jié)點(diǎn)樹。那么二叉樹有3種度：
- n0: 度為0，即為葉子節(jié)點(diǎn)數(shù)量。
- n1: 度為1，即為只有左子樹或者右子樹的節(jié)點(diǎn)數(shù)量，對于完全二叉樹，只可能存在一種情況，節(jié)點(diǎn)數(shù)為奇數(shù)時有一個節(jié)點(diǎn)只有一個左子樹，所以n1 = 0 or 1。
- n2:度為2，即有左右節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)量。
引理 n0 = n2 + 1
證明：
- 假設(shè)樹的節(jié)點(diǎn)數(shù)是n，那么n = n0 + n1 + n2。
- 按照入度考慮一下(節(jié)點(diǎn)上面的邊)，除了根節(jié)點(diǎn)，每個節(jié)點(diǎn)都有一條入邊，所以邊數(shù)為n-1；而邊的數(shù)量為2*n2 + n1
- 結(jié)合上面兩個推導(dǎo): 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為偶數(shù)，說明不存在只有子節(jié)點(diǎn)的節(jié)點(diǎn)，n1 = 0, n0 = (n+1)/2；如果n為奇數(shù)，說明存在1個只有左子節(jié)點(diǎn)的節(jié)點(diǎn)，那么n1 = 1, n0 = n/2?？梢院喜閚0 = (n+1)/2。
小結(jié)
根據(jù)結(jié)論n0 = (n+1)/2， 所以結(jié)果為420。在整個過程中，我們不需要去記憶結(jié)論，而是記住推理的過程，這樣就是利用第一性原理在學(xué)習(xí)。
