均衡二叉樹

均衡二叉樹，數學公式之一，其節點數是2^（h-1）-1+m。

什麼是均衡二叉樹

深度為n的均衡二叉樹是指：如果去掉葉結點及相應的樹枝，它應該是深度為n-1的滿二叉樹。

例子

1
/ \
2 3
\ /
4 5 是均衡二叉樹，因為它去掉葉結點及相應的樹枝後，
變成了：
1
/ \
2 3 ，這是一個二叉樹。
1
/ \
2 3
而 \ / \ 則不是，因為它去掉葉結點及相應的樹枝後，
4 5 6
/
7
變成了：
1
/ \
2 3
\
4
很顯然，這並不是一個完全二叉樹。

如何計算均衡二叉樹的總結點數

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