首页 > 试题广场 > 判断下列说法是否正确:一棵深度为k的平衡二叉树,其每个非终端
[单选题]
判断下列说法是否正确:一棵深度为k的平衡二叉树,其每个非终端结点的平衡因子均为0,则该树共有2k-1个结点。()
  • 正确
  • 错误
推荐
答案:A
解答:某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子,因为每个非终端节点的平衡因子均为0,所以这颗二叉树为满树,其次对于第i层来说,该层一共有2i-1个节点,因此所有节点数为等比数列求和:1+2+22+23+...+2(k-1)=2k-1
编辑于 2019-10-09 14:22:03 回复(0)
A
题干两点条件:
  1. 平衡二叉树
  2. 非终端结点平衡因子为0  (左右子树高度相等
一棵深度为k的平衡二叉树。因此,这样的平衡二叉树即为满二叉树,而高度为k的满二叉树的结点数是2k-1。
发表于 2019-10-08 18:52:17 回复(0)
所有非叶子节点平衡因子为0,是满二叉树,节点最多。为1,节点最少。
发表于 2019-10-14 19:59:33 回复(0)