嚴(yán)格二叉樹(shù)

是程序算法中的一種算法模式。

在二叉樹(shù)中出現(xiàn)空的子樹(shù)（包括樹(shù)葉）上增加空的樹(shù)葉，使其成為滿二叉樹(shù)的二叉樹(shù)稱之為擴(kuò)充二叉樹(shù)。

1

/ \

2 3

\ /

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

變成了：

1

/ \

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

1

/ \

2 3

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

4 5 6

/

7

變成了：

1

/ \

2 3

\

4

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

完全二叉樹(shù)(Complete Binary Tree)

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

完全二叉樹(shù)是由滿二叉樹(shù)而引出來(lái)的。對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹(shù)。

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