什么是完全二叉树？

推荐答案

完全二叉树是一种特殊的二叉树，其中除了最后一层外，每一层的节点都达到最大数量，并且最后一层的节点都尽可能地集中在左侧。换句话说，完全二叉树的节点按照从上到下、从左到右的顺序依次排列。

本题详细解读

完全二叉树的定义

完全二叉树的定义可以分解为以下几个关键点：

1. 层次性：完全二叉树的节点按照层次从上到下排列，每一层的节点从左到右依次排列。
2. 最大节点数：除了最后一层外，每一层的节点数都达到最大数量。对于深度为 d 的完全二叉树，前 d-1 层的节点数为 2^(d-1) - 1。
3. 最后一层的节点排列：最后一层的节点从左到右依次排列，且没有空缺。

完全二叉树的性质

1. 节点编号：如果对完全二叉树的节点进行编号（从1开始），那么对于任意一个节点 i，其左子节点的编号为 2i，右子节点的编号为 2i+1。
2. 高度：完全二叉树的高度为 log2(n+1)，其中 n 是节点的总数。
3. 堆结构：完全二叉树常用于实现堆（Heap）数据结构，因为它的结构可以保证堆的性质（如最大堆或最小堆）。

完全二叉树与满二叉树的区别

• 满二叉树：每一层的节点数都达到最大数量，即深度为 d 的满二叉树有 2^d - 1 个节点。
• 完全二叉树：除了最后一层外，每一层的节点数都达到最大数量，最后一层的节点从左到右依次排列。

完全二叉树的判断方法

判断一棵二叉树是否为完全二叉树，可以通过以下步骤：

1. 层次遍历：从根节点开始，按层次遍历二叉树。
2. 标记空节点：在遍历过程中，如果遇到一个空节点，则标记为 null。
3. 检查后续节点：如果在标记 null 之后，又遇到了非空节点，则该二叉树不是完全二叉树。

代码示例

以下是一个判断二叉树是否为完全二叉树的Python代码示例：

// www.javascriptcn.com code example
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_complete_tree(root):
    if not root:
        return True
    
    queue = deque([root])
    has_null = False
    
    while queue:
        node = queue.popleft()
        
        if not node:
            has_null = True
        else:
            if has_null:
                return False
            queue.append(node.left)
            queue.append(node.right)
    
    return True

总结

完全二叉树是一种结构规整的二叉树，具有层次性和节点排列的特定规则。它在数据结构中有着广泛的应用，特别是在堆的实现中。理解完全二叉树的定义和性质，对于掌握二叉树相关算法和数据结构非常重要。