前置知识：完全二叉树

⚡ 30 秒速记

• 完全二叉树除最后一层外都填满，最后一层从左到右连续填充，因此适合用数组紧凑存储
• 零基数组中父结点是 Math.floor((i - 1) / 2)，左右孩子是 2i + 1、2i + 2
• 完全性是形状约束，不规定父子值大小；堆还要额外满足堆序性质

完全二叉树除最后一层外都必须填满，最后一层的结点还要从左到右连续排列。 正因为形状紧凑，它可以按从上到下、从左到右的顺序存进数组，不需要额外保存连接关系。零基数组中，索引 i 的父结点是 Math.floor((i - 1) / 2)，左右孩子分别是 2 * i + 1 和 2 * i + 2。这里约束的是树的形状，并没有规定父子结点值的大小。

完全二叉树是指同时满足下面两个条件的二叉树：

• 从第一层到倒数第二层，每一层都是满的，也就是说每一层的结点数都达到了当前层所能达到的最大值
• 最后一层的结点是从左到右连续排列的，不存在跳跃排列的情况（也就是说这一层的所有结点都集中排列在最左边）。

完全二叉树可以是这样的：

也可以是这样的：

但不能是这样的：

更不能是这样的：

注意，完全二叉树中有着这样的索引规律：假如我们从左到右、从上到下依次对完全二叉树中的结点从0开始进行编码：

那么对于索引为 n 的结点来说：

• 索引为 (n-1)/2 的结点是它的父结点
• 索引 2*n+1 的结点是它的左孩子结点
• 索为引 2*n+2 的结点是它的右孩子结点

💬 面试官追问

• 可视化页面中一棵树除最后一层外都满，但最后一层节点出现在最右侧、左侧留空，设计师称它仍是完全二叉树，你怎么反驳？

  它不是完全二叉树，因为最后一层必须从左到右连续占位，不能在左侧留下空洞后又出现节点。仅满足前面各层为满层还不够；这个反例会破坏按层连续存入数组时的紧凑索引关系。

• 堆组件用零基数组保存节点，代码评审要求你写出索引 i 的父节点和两个孩子位置，并说明边界怎么处理？

  左孩子是 2*i+1，右孩子是 2*i+2，非根节点的父节点是 Math.floor((i-1)/2)。计算出的孩子下标必须小于数组长度才真实存在，根节点没有父节点；公式成立依赖节点按层且从左到右连续存放。

• 批量建堆时同事从数组末尾每个节点都执行下沉，你会把起点改到哪里，依据是什么？

  应从最后一个非叶节点 Math.floor(n/2)-1 开始向前下沉，因为零基数组中其后的节点都没有孩子。叶节点天然满足局部堆约束，无需处理；空数组或单元素数组得到负起点时应直接结束。

• 序列化模块收到普通二叉树，需要判断它能否紧凑编码为完全二叉树；日志显示某层出现空位后，后续又读到非空节点，你如何判定？

  应立即判为非完全二叉树，因为层序扫描一旦遇到首个空孩子，后续位置只能继续为空。实现时可设置“已进入空缺区”标记，之后发现非空节点即失败；若随意跳过空位，就会掩盖中间空洞。

• 存储组选型时，一方要用数组保存任意稀疏二叉树，另一方只接受完全二叉树，你会怎样解释空间取舍？

  完全二叉树按层连续排列，数组下标即可定位父子，不需要额外指针，也不会因结构产生大量空槽。任意稀疏树若强行沿用同样的位置编码，深层少量节点可能对应很大的下标；此时显式节点引用通常更合适。