题13

题13

题目

Q:高度为 3 的平衡二叉排序树的形态共有 ( ) 种.
A. 13
B. 14
C. 16
D. 15

分析

A:平衡二叉树的形态数量通过卡特兰树来进行计算：

注意把平衡二叉树的形态和题9中二叉查找树的形态数的计算区分开来，上面这么算是错的

解

D
高度为 3 的平衡二叉树的左右子树的高度共有三种情况:
①左右子树都是高度为 2 的平衡二叉树;
②左子树是高度为 1 的平衡二叉树, 右子树是高度为 2 的平衡二叉树;
③左子树是高度为 2 的平衡二叉树, 右子树是高度为 1 的平衡二叉树。
高度为 1 的平衡二叉树只有 1 种形态, 即单个结点, 如图 1 所示;
高度为 2 的平衡二叉树有 3 种形态, 如图 2 所示。

因此,对于情况①,共有 种树形态;
对于情况②,共有 种树形态;
情况③和情况②类似,也有 3 种树形态,所以共有 种树形态。