CC++ & Algorithm

完全二叉树

较难0
语言版本：C++
概述：完全二叉树是除最后一层外，每一层都满，且最后一层的节点全部靠左排列。

完全二叉树：一种整齐有规律的树形结构

想象一下，你正在班级里排座位，老师要求大家按顺序坐好：第一排坐满4个同学，第二排坐满4个，第三排坐满4个……到了最后一排，人数不够也没关系，但必须从最左边的座位开始坐，中间不能有空位。这种“先上后下、先左后右，绝不留空”的坐法，就和完全二叉树一模一样。

完全二叉树是除了最后一层外，上面每一层的节点数都达到最大值（即该层所有位置都填满），并且最后一层的节点全部靠左连续排列的二叉树。这种结构在计算机科学中有很多好处，比如可以用数组来高效存储，实现堆排序、优先队列等经典算法。

一、完全二叉树的两条核心规则

  1. 上一层必须全满
    假设树有 h 层，那么第 1 层到第 h-1 层都必须是满的（每个节点都有左右孩子）。例如一个高度为 3 的完全二叉树，前两层（第1层1个节点，第2层2个节点）必须全部存在。

  2. 最后一层必须靠左连续
    最后一层的节点必须从最左边开始依次排列，中间不能有空缺。也就是说，从左到右数节点时，不会出现“右边有节点、左边却空着”的情况。

为什么叫“完全”？
因为它“几近完整”，除了最后一层可能有缺失，其他部分都完整。它比一般二叉树更规整，比满二叉树（每一层都满）更灵活。

二、生活中的完全二叉树

  • 学校运动会淘汰赛
    把8支球队的赛程画成一棵二叉树，第1轮是4场比赛，第2轮是2场，第3轮是1场。如果只有6支球队，那么最后两场比赛的队伍需要“轮空”，但如果第1轮先安排6队中的4队比赛，另外2队轮空，这种安排就不符合完全二叉树——因为轮空的队伍在树中相当于某些节点缺失且不连续。而真正完全二叉树的淘汰赛会先让所有球队依次配对，实在不够的才轮空，并且轮空位置也靠左。

  • 电影院座位编号
    假设电影院有若干排，每排座位数相同，但今天观众人数少，大家从每排最左边开始坐，不允许隔空坐人。这种“靠左连续”的坐法就是完全二叉树的思想。

三、完全二叉树的性质（数学规律）

  1. 节点数与高度的关系
    设树的高度为 h（根节点高度为1），则最少有 2^(h-1) 个节点（最后一层只有1个），最多有 2^h - 1 个节点（满二叉树）。

  2. 用数组存储时的索引规律
    这是完全二叉树最大优势：

    • 从数组索引 1 开始存储根节点（索引0留空或放总数）。
    • 对于任意节点在数组中的位置 i：
      • 它的左孩子位置为 2 * i
      • 它的右孩子位置为 2 * i + 1
      • 它的父节点位置为 i // 2
    • 数组的最后一个非叶子节点下标为 总节点数 // 2。

    这个规律省去了用指针（或 left/right 属性）连接节点的麻烦，只需简单的下标运算就能找到子节点或父节点。

  3. 为什么可以用数组？
    因为完全二叉树是“连续”的，从左到右、从上到下编号正好与数组的下标一一对应。如果树中间有空洞，这种对应关系就会被打乱，必须用指针结构。

四、Python 实现：用列表模拟完全二叉树

1. 从层序遍历序列构建完全二叉树

假设我们已经按层序遍历得到了节点的值序列（例如 [1,2,3,4,5,6]），由于完全二叉树连续无空洞，我们可以直接把它存入数组，并在索引0处放一个占位符（比如 None），让真正的数据从索引1开始。

def build_complete_tree(values):
    # values: 按层序顺序给出的节点值列表，完全二叉树连续，无None
    # 返回一个列表，索引0占位None，索引1起存储节点值
    return [None] + values   # 前面加一个占位符

2. 辅助函数：拿到孩子和父节点的索引

def left_child(index):
    # 返回左孩子的位置（下标）
    return index * 2

def right_child(index):
    # 返回右孩子的位置（下标）
    return index * 2 + 1

def parent(index):
    # 返回父节点的位置
    return index // 2

3. 遍历完全二叉树

因为数组已经天然记录了节点的顺序，我们可以用递归或栈来遍历。下面给出前序、中序、后序和层序遍历的代码。

def preorder_tree(tree, index, result):
    # 前序遍历：根 -> 左 -> 右
    if index < len(tree) and tree[index] is not None:
        result.append(tree[index])               # 访问根
        preorder_tree(tree, left_child(index), result)   # 递归左子树
        preorder_tree(tree, right_child(index), result)  # 递归右子树

def inorder_tree(tree, index, result):
    # 中序遍历：左 -> 根 -> 右
    if index < len(tree) and tree[index] is not None:
        inorder_tree(tree, left_child(index), result)
        result.append(tree[index])
        inorder_tree(tree, right_child(index), result)

def postorder_tree(tree, index, result):
    # 后序遍历：左 -> 右 -> 根
    if index < len(tree) and tree[index] is not None:
        postorder_tree(tree, left_child(index), result)
        postorder_tree(tree, right_child(index), result)
        result.append(tree[index])

def level_order_tree(tree):
    # 层序遍历：直接按数组顺序输出（跳过索引0）
    # 注意：完全二叉树数组本身已经是层序顺序，但需去掉None（本例中不会出现None）
    return [tree[i] for i in range(1, len(tree)) if tree[i] is not None]

4. 完整示例

现在我们来创建一个有6个节点的完全二叉树，并打印所有遍历结果。

# 创建一个完全二叉树，按层序输入：1为根，2左，3右，4、5、6为下一层（2的孩子）
tree = build_complete_tree([1, 2, 3, 4, 5, 6])

res_pre = []
preorder_tree(tree, 1, res_pre)
print("前序遍历结果:", res_pre)   # 输出: [1, 2, 4, 5, 3, 6]

res_in = []
inorder_tree(tree, 1, res_in)
print("中序遍历结果:", res_in)    # 输出: [4, 2, 5, 1, 3, 6]

res_post = []
postorder_tree(tree, 1, res_post)
print("后序遍历结果:", res_post)  # 输出: [4, 5, 2, 6, 3, 1]

print("层序遍历结果:", level_order_tree(tree))  # 输出: [1, 2, 3, 4, 5, 6]

注意：中序和后序遍历结果与普通二叉树一样，完全二叉树并没有特殊的遍历规则，只是存储方式不同。

五、新手最容易犯的错

  1. 数组索引从 0 还是 1 开始？

    • 如果索引从 0 开始，那么左孩子是 2*i+1，右孩子是 2*i+2，父节点是 (i-1)//2。
    • 如果索引从 1 开始，公式更简洁。建议统一用一种，并在写代码时明确注释。
    • 常见错误：混用两种公式，或者忘记留出索引 0 的占位符，导致越界。

  2. 判断孩子是否存在的条件
    用数组存储时，节点不一定都存在（虽然完全二叉树是连续的，但用 None 占位时也可能有空洞）。一定要检查下标是否超出数组长度，以及该位置的值是否为 None。否则递归时会访问到空值或越界。

    # 错误写法：直接访问可能会下标越界
res.append(tree[left_child(index)])  # 如果 left_child(index) 超出 len(tree)-1，会报错

# 正确写法：
if left_child(index) < len(tree):
    ...

  3. 认为完全二叉树一定是满二叉树

    • 满二叉树：所有层都是满的。
    • 完全二叉树：除了最后一层，上面全满，最后一层靠左连续。
      完全二叉树不一定是满二叉树，但满二叉树一定是完全二叉树。

  4. 层序遍历结果不等价于数组顺序
    对于完全二叉树，数组的顺序（从索引1开始）就是层序遍历的顺序，但遇到 None 占位的情况（比如不是完全二叉树时），层序遍历需要跳过 None。不过在我们讨论的“连续完全二叉树”中不会出现 None。

六、相关知识点指引

  • 堆（Heap）：堆是一种完全二叉树，通常用数组实现，分为最大堆和最小堆。堆排序、优先队列的底层都是堆。
  • 优先队列（Priority Queue）：用堆实现，支持快速取出最大/最小元素。
  • 线段树（Segment Tree）：虽然不一定是完全二叉树，但也常用数组存储，其父子索引关系与完全二叉树一样（2i, 2i+1）。
  • 二叉堆的插入与删除：完全二叉树的性质保证了堆的平衡，插入时在数组末尾添加节点，然后“上浮”；删除根时，把最后一个节点移到根，然后“下沉”。
  • 树的遍历：前序、中序、后序、层序遍历，是二叉树的基本操作，掌握它们后可以应对很多树的问题。

如果你已经掌握了完全二叉树的数组存储，接下来可以尝试用 Python 实现一个最小堆，或者用堆解决“合并K个有序链表”这样有趣的问题。

例题精讲

1单选题

一棵完全二叉树共有100个节点，则其叶子节点个数为多少？

A50
B51
C49
D48
2判断题

一棵完全二叉树一定是满二叉树。

3填空题
以下函数用于判断一棵二叉树是否为完全二叉树。请补充代码。

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

def is_complete(root):
    if not root:
        return True
    from collections import deque
    queue = deque([root])
    flag = False  # 标记是否遇到空节点
    while queue:
        node = queue.popleft()
        if not node:
            flag = True
        else:
            if flag:
                return False
            queue.append(node.left)
            queue.append(___)
    return True
4单选题

将一棵完全二叉树按层序编号（根节点编号为1），则编号为10的节点的父节点编号是？

A4
B5
C6
D3
5判断题

一棵完全二叉树有2^k个节点，则其深度为k+1。