EC18-将二叉树存储到一维数组中¶

代码实现¶

C
// 函数 create：将二叉树存储到一维数组中
// 参数：
// p - 当前二叉树节点
// A[] - 存储二叉树的一维数组
// i - 当前节点在数组中的索引位置
void create(BiTree p, char A[], int i) {
    // 递归终止条件：如果当前节点为空，则返回
    if (p != NULL) {
        A[i] = p->data; // 将当前节点的数据存储到数组的第 i 个位置

        // 递归处理左子树，左子节点的索引为 2*i+1
        create(p->lchild, A, 2 * i + 1);

        // 递归处理右子树，右子节点的索引为 2*i+2
        create(p->rchild, A, 2 * i + 2);
    }
}

代码逻辑解析¶

1. 二叉树与一维数组的映射关系¶

在完全二叉树中，节点可以通过以下规则映射到一维数组：
根节点的索引为 0。
对于任意节点的索引 i：
- 左子节点的索引为 2*i + 1。
- 右子节点的索引为 2*i + 2。
- 父节点的索引为 (i-1)/2（向下取整）。

2. 算法思路¶

使用递归遍历二叉树，将每个节点的数据存储到一维数组中对应的位置。
通过上述公式计算左右子节点的索引位置。

3. 递归过程¶

递归终止条件：如果当前节点为空，则直接返回。
递归步骤：
将当前节点的数据存储到数组的相应位置。
递归处理左子树，索引为 2*i + 1。
递归处理右子树，索引为 2*i + 2。

时间复杂度分析¶

1. 遍历节点数¶

每个节点被访问 exactly 一次。
时间复杂度：O(n)，其中 n 是二叉树的节点总数。

2. 数组存储操作¶

每次存储操作的时间复杂度为 O(1)。
总时间复杂度：O(n)。

空间复杂度分析¶

1. 额外空间使用¶

只使用了常量级别的局部变量（如索引 i）。
没有使用额外的数据结构。

2. 递归调用栈空间¶

递归深度取决于树的高度 h。
最好情况（完全二叉树）：O(log n)。
最坏情况（退化为链表）：O(n)。

3. 总体空间复杂度¶

O(h)，其中 h 是树的高度。在最坏情况下为 O(n)。

较难理解部分的说明¶

1. 数组索引公式的推导¶

公式解释：¶

根节点的索引为 0。
对于任意节点的索引 i：
左子节点的索引为 2*i + 1。
右子节点的索引为 2*i + 2。

图解说明：¶

假设二叉树结构如下：

Text Only
1 2 3 4 5	`A // 根节点 / \ B C // 第 1 层 / \ / \ D E F G // 第 2 层`

对应的数组存储如下：

Text Only
1 2	`索引: 0 1 2 3 4 5 6 数据: [A, B, C, D, E, F, G]`

根节点 A 的索引为 0。
B 是 A 的左子节点，索引为 2*0 + 1 = 1。
C 是 A 的右子节点，索引为 2*0 + 2 = 2。
D 是 B 的左子节点，索引为 2*1 + 1 = 3。
E 是 B 的右子节点，索引为 2*1 + 2 = 4。
F 是 C 的左子节点，索引为 2*2 + 1 = 5。
G 是 C 的右子节点，索引为 2*2 + 2 = 6。

2. 空节点的处理¶

如果二叉树不是完全二叉树，某些节点可能为空。
在这种情况下，数组中对应的索引位置会保留未使用的状态（通常可以初始化为空值或特殊标记）。

例如：

Text Only
1 2 3 4 5	`A // 根节点 / \ B C // 第 1 层 / D // 第 2 层`

对应的数组存储如下：

Text Only
1 2	`索引: 0 1 2 3 4 5 6 数据: [A, B, C, D, -, -, -]`

延伸知识点¶

1. 从一维数组还原二叉树¶

C
// 函数 restore：从一维数组还原二叉树
BiTree restore(char A[], int i, int n) {
    // 如果索引超出数组范围或当前元素为空，则返回 NULL
    if (i >= n || A[i] == '-') {
        return NULL;
    }

    // 创建当前节点
    BiTree node = (BiTree)malloc(sizeof(BTNode));
    node->data = A[i];

    // 递归构建左子树和右子树
    node->lchild = restore(A, 2 * i + 1, n);
    node->rchild = restore(A, 2 * i + 2, n);

    return node;
}

2. 完全二叉树的性质¶

完全二叉树的特点是：
所有层（除了最后一层）都是满的。
最后一层的节点从左到右连续排列。
完全二叉树非常适合用一维数组表示，因为不会浪费空间。

3. 实际应用场景¶

堆排序：堆是一种特殊的完全二叉树，通常用一维数组实现。
线段树：用于区间查询和更新问题。
树状数组（Fenwick Tree）：一种高效的数据结构，用于动态前缀和查询。
内存优化：在嵌入式系统中，使用一维数组存储二叉树可以节省内存。

4. 性能优化建议¶

C
// 非递归版本 - 使用队列模拟层次遍历
void createIterative(BiTree root, char A[]) {
    if (root == NULL) return;

    Queue* queue = createQueue(); // 假设有队列实现
    enqueue(queue, root);
    int index = 0;

    while (!isEmpty(queue)) {
        BiTree node = dequeue(queue);
        A[index++] = node->data;

        if (node->lchild) enqueue(queue, node->lchild);
        if (node->rchild) enqueue(queue, node->rchild);
    }
}

这种方法体现了树与数组之间的映射关系的思想，是计算机科学中经典问题之一。