Python实现：层次遍历判断完全二叉树

在Python中，判断一个二叉树是否为完全二叉树是通过层次遍历的方式实现的。完全二叉树是一种特殊的二叉树，它除了最后一层外，每一层都是满的，且所有叶子节点都集中在最右边。以下是一个使用队列实现的判断完全二叉树的代码示例： ```python class TreeNode: def __init__(self, value): self.val = value self.left = None self.right = None def is_complete_binary_tree(root): if not root: return False queue = [root] flag = False # 标记是否遇到空节点后有非叶子节点 while queue: node = queue.pop(0) # 检查左子节点 if node.left: queue.append(node.left) else: # 如果之前有空节点，当前节点无左子节点，更新flag if flag: return False flag = True # 检查右子节点 if node.right: queue.append(node.right) else: # 如果之前有空节点，当前节点无右子节点，保持flag为True if flag: continue else: # 遇到空节点后没有非叶子节点，恢复flag为True flag = True # 如果整个遍历过程中未发现不符合完全二叉树条件的情况，返回True return True ``` 这个`is_complete_binary_tree`函数首先检查根节点是否存在，若不存在则直接返回False。接着，使用队列执行层次遍历。对于当前节点，如果其左子节点存在，则将左子节点加入队列；若不存在且之前已遇到空节点，则说明后续可能有非叶子节点，更新标志`flag`为False。如果左子节点不存在但右子节点存在，继续处理右子节点。如果遍历过程中始终未发现不符合条件的情况（即遇到空节点后没有非叶子节点），最后返回True，表示该二叉树是完全二叉树。反之，如果遍历结束时`flag`仍为False，说明存在空节点之后有非叶子节点，返回False。通过这种方法，我们可以有效地判断一个给定的二叉树是否满足完全二叉树的定义。