2、對(duì)于滿二叉樹，除最后一層無任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)二叉樹。而完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹。

　　性質(zhì)

　　如果一棵具有n個(gè)結(jié)點(diǎn)的深度為k的二叉樹，它的每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)為1~n的結(jié)點(diǎn)一一對(duì)應(yīng)，這棵二叉樹稱為完全二叉樹。

　　可以根據(jù)公式進(jìn)行推導(dǎo)，假設(shè)n0是度為0的結(jié)點(diǎn)總數(shù)（即葉子結(jié)點(diǎn)數(shù)），n1是度為1的結(jié)點(diǎn)總數(shù)，n2是度為2的結(jié)點(diǎn)總數(shù)，則 ：

　�、賜= n0+n1+n2 （其中n為完全二叉樹的結(jié)點(diǎn)總數(shù)）；又因?yàn)橐粋�(gè)度為2的結(jié)點(diǎn)會(huì)有2個(gè)子結(jié)點(diǎn)，一個(gè)度為1的結(jié)點(diǎn)會(huì)有1個(gè)子結(jié)點(diǎn)，除根結(jié)點(diǎn)外其他結(jié)點(diǎn)都有父結(jié)點(diǎn)，

　�、趎= 1+n1+2*n2 ；由①、②兩式把n2消去得：n= 2*n0+n1-1，由于完全二叉樹中度為1的結(jié)點(diǎn)數(shù)只有兩種可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。