完全二叉樹

完全二叉樹(Complete Binary Tree)

若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1~h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。

完全二叉樹是由滿二叉樹而引出來的。對(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í)稱之為完全二叉樹。

一棵二叉樹至多只有最下面的一層上的結(jié)點(diǎn)的度數(shù)可以小于2，并且最下層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹成為完全二叉樹。

如果一棵具有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ù)，則 ①n= 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)，所以②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。

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

完全二叉樹:葉節(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置的二叉樹

葉子結(jié)點(diǎn)只可能在最大的兩層上出現(xiàn),對(duì)任意結(jié)點(diǎn)，若其右分支下的子孫最大層次為L，則其左分支下的子孫的最大層次必為L 或 L+1;

出于簡便起見,完全二叉樹通常采用數(shù)組而不是鏈表存儲(chǔ),其存儲(chǔ)結(jié)構(gòu)如下:

var tree:array[1..n]of longint;{n:integer;n>=1}

對(duì)于tree[i]，有如下特點(diǎn):

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

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

(3)若i>1，tree的父親節(jié)點(diǎn)為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é)點(diǎn)(對(duì)應(yīng)于(3));

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

(7)滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。

完全二叉樹第i層至多有2^(i-1)個(gè)節(jié)點(diǎn)，共i層的完全二叉樹最多有2^i-1個(gè)節(jié)點(diǎn)。

完全二叉樹的特點(diǎn)是:

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

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

大家都知道完全二叉樹的總結(jié)點(diǎn)數(shù)是： 2^h-1，而均衡二叉樹是完全二叉樹再加上幾個(gè)葉結(jié)點(diǎn)，所以它的總結(jié)點(diǎn)數(shù)就是：2^（h-1）-1+m，其中h是樹的深度，m是第h層葉結(jié)點(diǎn)個(gè)數(shù)。

下面我們來討論左偏樹的距離和節(jié)點(diǎn)數(shù)的關(guān)系。

[引理1] 若左偏樹的距離為一定值，則節(jié)點(diǎn)數(shù)最少的左偏樹是完全二叉樹。

證明:由性質(zhì)2可知，當(dāng)且僅當(dāng)對(duì)于一棵左偏樹中的每個(gè)節(jié)點(diǎn)i，都有dist(left(i)) =dist(right(i)) 時(shí)，該左偏樹的節(jié)點(diǎn)數(shù)最少。顯然具有這樣性質(zhì)的二叉樹是完全二叉樹。

[定理1] 若一棵左偏樹的距離為k，則這棵左偏樹至少有2^(k+1)-1個(gè)節(jié)點(diǎn)。

證明:由引理1可知，當(dāng)這樣的左偏樹節(jié)點(diǎn)數(shù)最少的時(shí)候，是一棵完全二叉樹。距離為k的完全二叉樹高度也為k，節(jié)點(diǎn)數(shù)為2^(k+1)-1，所以距離為k的左偏樹至少有2^(k+1)-1個(gè)節(jié)點(diǎn)。

作為定理1的推論，我們有:

[性質(zhì)4] 一棵N個(gè)節(jié)點(diǎn)的左偏樹距離最多為?log(N+1)?-1。

證明:設(shè)一棵N個(gè)節(jié)點(diǎn)的左偏樹距離為k，由定理1可知，N ≥ 2^(k+1)-1，因此k ≤ ?log(N+1)?-1。

標(biāo)程

《數(shù)字序列》程序

1

/ \

2 3

\ /

4 5 是均衡二叉樹，因?yàn)樗サ羧~結(jié)點(diǎn)及相應(yīng)的樹枝后，

變成了：

1

/ \

2 3 ，這是一個(gè)二叉樹。

1

/ \

2 3

而 \ / \ 則不是，因?yàn)樗サ羧~結(jié)點(diǎn)及相應(yīng)的樹枝后，

4 5 6

/

7

變成了：

1

/ \

2 3

\

4

很顯然，這并不是一個(gè)完全二叉樹。