滿二叉樹 (Full binary tree)

除最后一層無任何子節點外，每一層上的所有結點都有兩個子結點二叉樹。

國內教程定義：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二叉樹。

國外(國際)定義:a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.

大意為：如果一棵二叉樹的結點要么是葉子結點，要么它有兩個子結點，這樣的樹就是滿二叉樹。(一棵滿二叉樹的每一個結點要么是葉子結點，要么它有兩個子結點，但是反過來不成立，因為完全二叉樹也滿足這個要求，但不是滿二叉樹)

從圖形形態上看，滿二叉樹外觀上是一個三角形。

從數學上看，滿二叉樹的各個層的結點數形成一個首項為1，公比為2的等比數列。

因此由等比數列的公式，滿二叉樹滿足如下性質。

1、一個層數為k 的滿二叉樹總結點數為：

??。因此滿二叉樹的結點樹一定是奇數個。

2、第i層上的結點數為：?

3、一個層數為k的滿二叉樹的葉子結點個數（也就是最后一層）：?

?

完全二叉樹

?

完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。

可以根據公式進行推導，假設n0是度為0的結點總數（即葉子結點數），n1是度為1的結點總數，n2是度為2的結點總數，則 ：

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

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

簡便來算，就是 n0=n/2，其中n為奇數時（n1=0）向上取整；n為偶數時（n1=1）。可根據完全二叉樹的結點總數計算出葉子結點數。

?

重點：出于簡便起見,完全二叉樹通常采用數組而不是鏈表存儲

?

對于tree[i]，有如下特點：

（1）若i為奇數且i>1，那么tree的左兄弟為tree[i-1]；

（2）若i為偶數且i<n，那么tree的右兄弟為tree[i+1]；

（3）若i>1，tree的父親節點為tree[i?div?2]；

（4）若2*i<=n，那么tree的左孩子為tree[2*i]；若2*i+1<=n，那么tree的右孩子為tree[2*i+1]；

（5）若i>n div 2,那么tree[i]為葉子結點（對應于（3））；

（6）若i<(n-1) div 2.那么tree[i]必有兩個孩子（對應于（4））。

（7）滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。

完全二叉樹第i層至多有2^（i-1）個節點，共i層的完全二叉樹最多有2^i-1個節點。

特點：

1）只允許最后一層有空缺結點且空缺在右邊，即葉子結點只能在層次最大的兩層上出現；

2）對任一結點，如果其右子樹的深度為j，則其左子樹的深度必為j或j+1。 即度為1的點只有1個或0個