滿二叉樹 (Full binary tree)

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

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

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

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

從圖形形態(tài)上看，滿二叉樹外觀上是一個三角形。

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

因此由等比數(shù)列的公式，滿二叉樹滿足如下性質(zhì)。

1、一個層數(shù)為k 的滿二叉樹總結(jié)點數(shù)為：

??。因此滿二叉樹的結(jié)點樹一定是奇數(shù)個。

2、第i層上的結(jié)點數(shù)為：?

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

?

完全二叉樹

?

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

可以根據(jù)公式進行推導(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。

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

?

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

?

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

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

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

（3）若i>1，tree的父親節(jié)點為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]為葉子結(jié)點（對應(yīng)于（3））；

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

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

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

特點：

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

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

總結(jié)

以上是生活随笔為你收集整理的数据结构课上笔记11的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。