均衡二叉樹

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

1

/ \

2 3

\ /

4 5 是均衡二叉樹，因為它去掉葉結(jié)點及相應(yīng)的樹枝后，

變成了：

1

/ \

2 3 ，這是一個二叉樹。

1

/ \

2 3

而 \ / \ 則不是，因為它去掉葉結(jié)點及相應(yīng)的樹枝后，

4 5 6

/

7

變成了：

1

/ \

2 3

\

4

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

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

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

完全二叉樹(Complete Binary Tree)

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

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

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