什么是均衡二叉树

例子

如何计算均衡二叉树的总结点数

什么是均衡二叉树

深度为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层叶结点个数。