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