单选题
以下有关平衡二叉树的说法中正确的是______。
A.平衡二叉树是高度最小的二叉排序树
B.平衡二叉树一定是丰满树
C.平衡二叉树上任一结点的平衡因子不能超过1
D.有n个结点的平衡二叉树的高度为O(log
2
n)
A
B
C
D
【正确答案】
D
【答案解析】
[解析] 有n个结点的平衡二叉树的最小高度h
min
=rlog2(n+1)l,最大高度h
max
<1.44×log
2
(n+1),因此选项D是正确的。由于平衡二叉树的中低层有可能没有填满,存在度为1的结点,只要每个结点的两棵子树的高度差的绝对值不超过1即可,所以其高度有可能不是最小,因此选项A不对。丰满树即理想平衡树,要求除最底层外其他层都是满的,平衡二叉树没有这样高的要求,因此选项B不对。对于C选项,应该是平衡二叉树上任一结点的平衡因子的绝对值不能超过1。
提交答案
关闭