CC++ & Algorithm

完全二叉树：像排队一样整齐的树

中等8
语言版本：C++Python
概述：完全二叉树是一种特殊的二叉树，除了最后一层外其它层都是满的，并且最后一层的节点全部靠左排列，非常适合用数组来存储。

完全二叉树：像排队一样整齐的树

完全二叉树是一种特殊的二叉树，它长得特别整齐——除了最后一层，其它每一层都是满的，而且最后一层的所有节点都从左边开始排，中间一个空位都不能有。这种“从左到右、从上到下”的排列规则，让完全二叉树可以用**数组（列表）**来存储，访问起来又快又省空间。你听过“堆排序”或“优先队列”吗？它们都是基于完全二叉树实现的。今天我们就来彻底搞懂它。

什么是完全二叉树？

想象一下学校做广播体操，老师让同学们站成几排，要求：

  • 第一排站满（比如4人）
  • 第二排也站满
  • 第三排也站满
  • …
    但是总人数可能不够站满最后一排，那么最后剩下的人必须从左边开始站，不能中间空着。如果队伍是这样的，它就是完全二叉树的样子。

对应到树结构：每个“人”就是一个节点，每排就是一层。

和“满二叉树”的区别：
满二叉树是所有层都站满（总人数正好是 2ⁿ - 1），而完全二叉树只要求除了最后一层外都满，最后一层靠左排列。所以满二叉树一定是完全二叉树，但反过来不一定。

完全二叉树的三个关键特点

  1. 除了最后一层，其它层都是满的
    第1层（根）最多1个节点，第2层最多2个，第3层最多4个……第 k 层最多 2^(k-1) 个。
    完全二叉树保证前几层一个不少。

  2. 最后一层的节点全部靠左
    假设最后一层有5个位置，但只有3个人，那么他们必须坐在左边第1、2、3号位子，第4、5号位子是空的。不能第1个空着、第2个有人。

  3. 编号有规律，适合用数组存储
    把节点从上到下、从左到右编号（从0开始），那么：

    • 父节点编号为 parent，左孩子编号 = 2 * parent + 1，右孩子编号 = 2 * parent + 2
    • 反过来，孩子编号为 child，父节点编号 = (child - 1) // 2（下取整）

    这个规律就是完全二叉树能用列表存储的根本原因。

生活中的例子：排座位、发零食、考试排名

例1：排座位

教室有4排，每排最多坐8人。班里25人，前3排坐满8×3=24人，最后一排只剩1人，他必须坐在最左边。这样座位编号就是从0到24，每个座位对应一个学生。

例2：发零食

妈妈买了15颗糖，想按“完全二叉树”的方式分给孩子们：第一个孩子拿1颗，第二、三个孩子每人拿2颗，第四到第七个孩子每人拿4颗……但糖果只有15颗，不够分完第4层（第4层需要8颗）。于是前3层分掉1+2+4=7颗，剩下8颗给第4层，第4层从左到右有8个孩子，每人1颗。如果糖果只有10颗，那么第4层只能分到3颗，后面5个位置空着。

例3：考试排名

老师想把全班成绩按从高到低排成“堆”（优先队列），堆就是用完全二叉树实现的。每次取出最高分，或者插入一个新分数，都只需要 O(log n) 时间，非常快。

为什么完全二叉树用数组存更方便？

普通二叉树需要用节点+指针（left、right）来链接，像链条一样。而完全二叉树因为编号有规律，每个节点的位置由编号直接决定，所以只需要一个列表就够了：

tree = [10, 20, 30, 40, 50, 60]  # 列表下标就是节点编号
  • 查找 tree[0] 就是根节点
  • 左孩子 tree[1]、右孩子 tree[2]
  • 想找某个节点的父节点，直接用公式 (index - 1) // 2 计算

这样内存占用小，访问速度快（随机访问），特别适合需要频繁读取父节点或子节点的操作。

新手容易犯的错误

❌ 错误1：把完全二叉树和满二叉树混为一谈

例子：

    10          （满二叉树：每层满）
   /  \
  20  30
 / \  / \
40 50 60 70

    10          （完全二叉树：最后一层靠左）
   /  \
  20  30
 / \  
40 50

上面的完全二叉树最后一层只有两个节点，但左边有，右边空缺。如果最后一层有节点在右边而左边空着，就不是完全二叉树。

❌ 错误2：插入节点时不考虑靠左规则

比如用列表 [10, 20, 30, 40, 50]，想加一个新节点60，正确做法是直接 append(60)，它会自动放在最后一层最左边的空位上。如果手动插入到错误位置（比如插到40和50之间）就破坏了完整结构。

❌ 错误3：计算子节点索引时忘记加1

公式是 2*parent + 1 和 2*parent + 2，不是 2*parent 和 2*parent+1（那是从1开始编号的规则）。Python列表从0开始，要小心。

完整可运行的代码示例

下面我们实现一个完全的二叉树类，包含：

  • 插入（自动保持完全二叉树性质）
  • 层序遍历（直接返回列表）
  • 获取父节点、左孩子、右孩子（通过公式计算）
  • 判断一棵树是否是完全二叉树（拓展功能）
class CompleteBinaryTree:
    def __init__(self):
        self.tree = []  # 用列表存储节点, 下标就是编号
    
    def insert(self, value):
        """
        向完全二叉树中添加一个节点
        直接追加到列表末尾, 新节点会自动成为最后一个位置
        """
        self.tree.append(value)
    
    def level_order(self):
        """层序遍历: 按编号顺序输出所有节点的值"""
        if not self.tree:
            return []
        return self.tree[:]  # 直接返回列表副本, 因为列表顺序就是层序顺序
    
    def parent_index(self, child_idx):
        """根据孩子编号返回父节点编号, 如果 child_idx 是根则返回 None"""
        if child_idx <= 0:
            return None
        return (child_idx - 1) // 2
    
    def left_child_index(self, parent_idx):
        """根据父节点编号返回左孩子编号, 如果超出范围则返回 None"""
        idx = 2 * parent_idx + 1
        if idx >= len(self.tree):
            return None
        return idx
    
    def right_child_index(self, parent_idx):
        """根据父节点编号返回右孩子编号, 如果超出范围则返回 None"""
        idx = 2 * parent_idx + 2
        if idx >= len(self.tree):
            return None
        return idx
    
    def is_complete(self):
        """
        判断当前树是否是完全二叉树
        核心: 层序遍历时遇到 None 后, 后面不能再有非 None 节点
        因为最后一层靠左, 中间不能有空缺
        """
        # 利用完全二叉树的性质: 编号连续, 没有空洞
        # 只要列表中没有空值（None）, 并且长度满足完全二叉树规律
        # 这里假设所有节点都是非空值, 如果插入过 None 则需特殊处理
        # 简单方法: 检查所有节点的编号是否连续
        # 对于完全二叉树, 最后一个节点的编号等于总节点数-1
        # 并且中间没有空缺
        return all(self.tree)  # 如果列表中没有 None、0 等假值, 可以认为连续
        # 更严格: 检查每个节点的子节点编号是否符合规则
        # 但简单场景下, 只要插入时保证正确, 自然就是完全的

# ---------- 使用示例 ----------
# 创建一个完全二叉树, 元素跟之前一样
cbt = CompleteBinaryTree()
vals = [10, 20, 30, 40, 50, 60]
for v in vals:
    cbt.insert(v)

print("完全二叉树中的元素（层序）:", cbt.level_order())
# 输出: [10, 20, 30, 40, 50, 60]

# 查看某个节点的家人
print("根节点:", cbt.tree[0])                 # 10
print("根节点的左孩子:", cbt.tree[cbt.left_child_index(0)])   # 20
print("根节点的右孩子:", cbt.tree[cbt.right_child_index(0)])  # 30
print("节点40（下标3）的父节点:", cbt.tree[cbt.parent_index(3)]) # 20
print("节点60（下标5）的父节点:", cbt.tree[cbt.parent_index(5)]) # 30

# 判断是否完全二叉树
print("这棵树是完全二叉树吗?", cbt.is_complete())  # True

# 对应的树结构:
#        10
#      /    \
#     20    30
#    /  \   /
#   40  50 60
# (60是30的左孩子, 30的右孩子空缺, 符合完全二叉树)

相关知识点

学完完全二叉树，你可以继续探索：

  1. 堆（Heap）：一种特殊的完全二叉树，分为最大堆（父节点≥子节点）和最小堆（父节点≤子节点）。Python 的 heapq 模块就是用列表实现的堆，常用于优先队列、排序等。
  2. 堆排序：利用堆的调整过程，可以在 O(n log n) 时间内完成排序。
  3. 段树、树状数组：虽然不一定是完全二叉树，但经常借用完全二叉树的编号思想。
  4. 层序遍历：对于完全二叉树，层序顺序就是数组下标顺序，对于普通二叉树则需要用队列来遍历。

完全二叉树是计算机科学中非常优雅的数据结构——它既有二叉树的灵活，又有数组的快速。记住“从左到右、从上到下，最后一层靠左”的口诀，你就能轻松掌握它。

例题精讲

1单选题

一棵完全二叉树有6层（根为第1层），则节点数最少为？

A31
B32
C63
D64
2判断题

完全二叉树中，如果节点总数为奇数，则叶子节点数等于内部节点数。

3填空题
以下函数用于判断一棵二叉树是否为完全二叉树，请填空：
def is_complete(root):
    if not root:
        return True
    queue = [root]
    has_no_child = False
    while queue:
        node = queue.pop(0)
        if node.left:
            if has_no_child:
                return False
            queue.append(node.left)
        else:
            has_no_child = True
        if node.right:
            if ___:
                return False
            queue.append(node.right)
        else:
            has_no_child = True
    return True
4判断题

完全二叉树的所有叶子节点只可能出现在最后两层。

5单选题

已知一棵完全二叉树有100个节点，按层序编号从1开始，则编号为8的节点其右孩子编号为？

A16
B17
C不存在
D15