高度为8的平衡二叉树的结点数（平衡二叉树和排序二叉树练习题）

对于平衡二叉树，任意一个结点的左右子树的高度差都不超过1。

已知高度为k的平衡二叉树，当它是棵满二叉树时结点最多，为：2^k-1，本例中为2^8-1=255。

结点最少时，除了叶子任意一个结点的左右子树的高度差都是1，设高度为k时的结点总数为S(k)，S(k)=S(k-1)+S(k-2)+1，S(k-1)、S(k-2)分别代表左右子树的结点数。那么很容易知道：S(1) = 1，S(2) = 2，可推出：

S(3) =S(1) +S(2)+1=4

S(4) = S(3) +S(2)+1=7

S(5) = S(3) +S(4)+1=12

S(6) = S(5) +S(4)+1=20

S(7) = S(5) +S(6)+1=33

S(8) =S(6) +S(7)+1= 54

综上，高度为8的平衡二叉树，结点数为54到255个。