如何在 Java 中利用数组实现简单的完全二叉树判定逻辑（基于下标连续性分析）

如何在 Ja va 中利用数组实现简单的完全二叉树判定逻辑（基于下标连续性分析）

用数组来存储二叉树，是一种非常直观且高效的方式，尤其是在处理完全二叉树时。其存储规则大家都很熟悉：根节点放在索引0，对于任意节点i，其左孩子索引是2*i+1，右孩子是2*i+2。那么，如何快速判断一个给定的数组是否对应一棵完全二叉树呢？答案就藏在“下标连续性”这个特性里。

简单来说，完全二叉树的数组表示有一个核心特征：所有非空节点必须紧密地排列在数组的前部，形成一个连续的块。一旦出现空位（null），那么这个空位之后的所有位置都必须为空，绝不允许“断档”后再出现有效节点。

完全二叉树的数组表示中，所有非空节点下标必须连续：若 tree[i] != null，则对任意 j < i，tree[j] 不能为空；且最后一个非空节点后不能有非空节点。

关键判定依据：有效节点下标必须连续

假设我们有一个数组Object[] tree，长度为n，其中null代表一个空节点。要判定它是否为完全二叉树，只需验证以下两点：

• 从数组头部开始，所有非空节点必须连续出现。换句话说，如果你在索引i找到了一个有效节点，那么所有比i小的索引位置j，都必须是有效节点。
• 一旦在某个位置遇到了第一个null，那么这个null之后的所有元素，都必须且只能是null。那种“空-非空”交替出现的情况，是完全二叉树所不允许的。

实现步骤：一次遍历识别中断点

基于上述逻辑，实现起来异常简洁。整个过程无需真正构建树结构，也无需递归或额外的存储空间，一次线性扫描足矣：

• 从索引0开始，顺序遍历数组。
• 找到第一个值为null的元素，记录下它的位置。
• 从这个位置之后继续检查，只要发现任何一个元素不是null，就可以立即断定：这棵树不是完全二叉树。
• 如果第一个null之后全是null，或者整个数组都没有null，那么它就是一棵完全二叉树。

Ja va 示例代码（简洁可运行）

下面这段代码，正是上述思路的直接体现：

public static boolean isCompleteBinaryTree(Object[] tree) {
  if (tree == null || tree.length == 0) return true;
  int n = tree.length;
  int firstNull = -1;

  // 第一步：定位第一个 null 出现的位置
  for (int i = 0; i < n; i++) {
    if (tree[i] == null) {
      firstNull = i;
      break;
    }
  }

  // 如果整个数组都没有 null，说明节点连续填满，自然是完全二叉树
  if (firstNull == -1) return true;

  // 第二步：检查第一个 null 之后是否还存在非 null 元素
  for (int i = firstNull + 1; i < n; i++) {
    if (tree[i] != null) return false;
  }

  return true;
}

立即学习“Ja va免费学习笔记（深入）”；

注意事项与边界情况

使用这个方法时，有几个细节需要留意：

• 该方法最适合“紧凑数组表示”，即数组长度对应着二叉树按层序展开到最深一层时的最大可能节点数。不过，我们实际只关心已存储节点的连续性，数组末尾多出来的空位（null）不影响判定。
• 举个例子，数组[1,2,3,null,null,null,null]是合法的，因为所有有效节点（1,2,3）连续，之后的null都是填充。但数组[1,2,null,4]就是非法的，因为在索引2出现null之后，索引3又出现了有效节点4，连续性被破坏了。
• 最后必须强调一点：这个方法只验证存储结构的下标连续性，它不检查数组中节点数值是否满足二叉树的父子关系逻辑。也就是说，它只保证“形状”上是完全二叉树，不保证“内容”上符合二叉搜索树等特定数据结构的约束。