滿二叉樹和完全二叉樹的區(qū)別

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

　　性質(zhì)

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

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

　　①n= n0+n1+n2 （其中n為完全二叉樹的結(jié)點總數(shù)）；又因為一個度為2的結(jié)點會有2個子結(jié)點，一個度為1的結(jié)點會有1個子結(jié)點，除根結(jié)點外其他結(jié)點都有父結(jié)點，

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