含有 20 个结点的平衡二叉树的最大深度为（ ）。

A. 4 B. 5 C. 6 D. 7

平衡二叉树

[tag_link]

正确答案：C

平衡二叉树（例如 AVL 树）要求每个结点的左右子树高度差不超过 1。 对于给定的结点数，最大深度对应于结点数最少的平衡二叉树结构——为了最大化深度，树应尽可能“瘦”，但平衡条件限制了子树的深度差。

设深度为

$d$ （根结点深度为 1）的平衡二叉树的最小结点数为 $M(d)$ ，满足递归关系：

$$M(d)=M(d-1)+M(d-2)+1,$$

其中 $M(1)=1$ ， $M(2)=2$ 。

计算可得：

$$M(3)=4,M(4)=7,M(5)=12,M(6)=20,M(7)=33.$$

现有 20 个结点，因为 $M(6)=20$ ，即深度为 6 时至少需要 20 个结点，而深度为 7 至少需要 33 个结点（ 20«/span>33 ），所以 20 个结点可以构建深度为 6 的平衡二叉树，但无法构建深度为 7 的平衡二叉树。

因此，最大深度为 6。