数组实现树遍历的核心是将完全二叉树层序存储并利用索引关系（i的左子为2i+1、右子为2i+2、父为(i-1)/2）模拟节点连接，支持O(1)增删，适用于嵌入式与教学；仅对完全/满二叉树严格成立，任意树需用占位符补空。
用数组实现树遍历，核心在于把完全二叉树按层序顺序存进数组，再利用索引关系模拟父子/左右子节点的连接。不需要指针，也不需要动态分配节点，适合嵌入式、竞赛或教学场景。
数组中节点索引的父子关系要记牢
假设数组下标从 0 开始，节点在位置 i，那么：
- 左子节点在 2*i + 1（若该值
- 右子节点在 2*i + 2
- 父节点在 (i − 1) / 2（整数除法，i > 0 时有效）
这个映射是层序存储的数学基础，也是所有遍历能成立的前提。注意：只对完全二叉树或满二叉树严格成立；若想表示任意二叉树，需在空位显式填 NULL 或占位符（如 -1、INT_MAX），否则索引会错位。
四种遍历的递归写法直接套用索引公式
所有遍历都从根节点（索引 0）开始，用一个 size 参数控制边界，避免越界访问：
-
前序遍历：先访问当前节点，再递归左、右子树 → 对应
printf("%d ", arr[i]);放最前 -
中序遍历：先左、再当前、最后右 →
printf在中间 -
后序遍历：左→右→当前 →
printf在最后 -
层次遍历：不用递归，直接顺序遍历数组
for (int i = 0; i 即可 —— 这正是数组表示的最大优势
例如数组 [1,2,3,4,5,6]（6 个节点），前序结果是 1 2 4 5 3 6，中序是 4 2 5 1 6 3，后序是 4 5 2 6 3 1。
实战处理完全二叉树变量的关键细节
定义数组时建议用 vector<int> 或 int arr[N]，并始终维护 size 字段（有效节点数），而非依赖 -1 等魔数判断空节点。常见操作示例：
- 获取深度：floor(log₂(size)) + 1（因为完全二叉树高度与节点数有确定关系）
- 判断是否为叶子节点：若 2*i + 1 >= size，说明无左子 → 当前即叶子
- 插入新节点：直接 push_back 到数组末尾，新节点索引为 size，其父节点就是 (size−1)/2
- 删除最后一个节点：pop_back 即可，无需调整其他位置
这些操作时间复杂度都是 O(1)，远优于链表实现的查找父/兄弟节点（需遍历）。
注意事项：别混淆“数组索引”和“逻辑层级”
数组下标不是层数。第 k 层（k 从 0 开始）包含的索引范围是 [2ᵏ, 2ᵏ⁺¹ − 1]，但前提是数组不缺位。比如 [1,2,3,4,5] 中，索引 4（值为 5）属于第 2 层，它的父节点是索引 (4−1)/2 = 1（值为 2），不是靠数位置猜出来的。
