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