试题详情
简答题设计算法，判断一棵二叉树是否为完全二叉树。
  • 根据完全二叉树的定义可知，对完全二叉树按照从上到下、从左到右的次序（即层序）遍历应该满足：
    ⑴若某结点没有左孩子，则其一定没有右孩子；
    ⑵若某结点无右孩子，则其所有后继结点一定无孩子。若有一结点不满足其中任意一条，则该二叉树就一定不是完全二叉树。因此可采用按层次遍历二叉树的方法依次对每个结点进行判断是否满足上述两个条件。为此，需设两个标志变量BJ和CM，其中BJ表示已扫描过的结点是否均有左右孩子，CM存放局部判断结果及最后的结果。
    具体算法如下：

  • 关注下方微信公众号，在线模考后查看

热门试题