用数组可以实现二叉树吗？

可以。用数组实现二叉树常见有两种思路： # 1) 隐式二叉树（最常用：完全二叉树/堆/段树） 把树当成“按层从左到右”的顺序放进一个数组，靠索引推算父子关系，无需指针。 * 0 基下标：`left(i)=2*i+1`，`right(i)=2*i+2`，`parent(i)=(i-1)/2` * 适用：**完全或近似完全**的二叉树（如最大/最小堆、段树、优先队列） * 优点：内存连续、局部性好、无需额外指针 * 缺点：稀疏/不平衡时会浪费空间 极简 Java 示例（最大堆）： ```java public class IntMaxHeap { private int[] a = new int[16]; private int size = 0; public void add(int x) { ensure(size + 1); a[size] = x; siftUp(size++); } public int peek() { if (size == 0) throw new IllegalStateException(); return a[0]; } public int poll() { if (size == 0) throw new IllegalStateException(); int top = a[0]; a[0] = a[--size]; siftDown(0); return top; } private void siftUp(int i) { while (i > 0) { int p = (i - 1) / 2; if (a[p] >= a[i]) break; swap(p, i); i = p; } } private void siftDown(int i) { while (true) { int l = 2 * i + 1, r = l + 1, best = i; if (l < size && a[l] > a[best]) best = l; if (r < size && a[r] > a[best]) best = r; if (best == i) break; swap(i, best); i = best; } } private void ensure(int n) { if (n > a.length) a = java.util.Arrays.copyOf(a, a.length * 2); } private void swap(int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } } ``` # 2) 显式二叉树（任意形状，用“并行数组”存孩子下标） 用几组数组保存**节点值**与**左右孩子的索引**，用 `-1` 表示空指针： ```java public class IntArrayBinaryTree { private int[] val = new int[16]; private int[] left = new int[16]; private int[] right = new int[16]; private int root = -1, size = 0; public int insertBST(int x) { // 例：按二叉搜索树规则插入 int node = newNode(x); if (root == -1) return root = node; int cur = root; while (true) { if (x < val[cur]) { if (left[cur] == -1) { left[cur] = node; break; } cur = left[cur]; } else { if (right[cur] == -1) { right[cur] = node; break; } cur = right[cur]; } } return node; } private int newNode(int x) { ensure(size + 1); val[size] = x; left[size] = right[size] = -1; return size++; } private void ensure(int n) { if (n > val.length) { int cap = val.length * 2; val = java.util.Arrays.copyOf(val, cap); left = java.util.Arrays.copyOf(left, cap); right = java.util.Arrays.copyOf(right, cap); } } } ``` * 适用：**任意形状**（BST、AVL、红黑树等）的教学或实验实现 * 优点：仍是连续内存（多组数组），cache 友好 * 缺点：代码管理相对繁琐（需要维护“空位/回收”等）；做旋转/删除时下标操作比指针版本更啰嗦 # 何时用数组？ * 完全/近完全树：**强烈推荐**（堆、段树、索引堆等），简单且高效 * 形态不规则的搜索树：可以用并行数组做，但工业界通常直接用“节点对象+引用”的实现，可读性更好、实现维护简单 如果你要在项目里做优先队列/排名，直接用数组堆（或 `PriorityQueue`）是最省心的；要做段树/区间统计，数组实现也是标准做法。