EC21-将顺序存储的二叉树转换为二叉链表表示¶

代码实现¶

C
// 函数 create：将顺序存储的二叉树转换为二叉链表表示
// 参数：
// A[] - 存储二叉树的顺序数组
// i   - 当前处理节点在数组中的索引
// n   - 数组的长度（节点总数）
// 返回值：构建好的二叉树节点指针
BiTree create(char A[], int i, int n) {
    // 递归终止条件：索引越界或当前节点为空节点
    if (i < n && A[i] != '#') {
        // 创建新节点并分配内存
        BiTree t = (BiTree)malloc(sizeof(BTNode));

        // 将数组中当前索引位置的数据赋值给节点
        t->data = A[i];

        // 递归构建左子树
        // 左子节点在数组中的索引为：2*i + 1
        t->lchild = create(A, 2 * i + 1, n);

        // 递归构建右子树
        // 右子节点在数组中的索引为：2*i + 2
        t->rchild = create(A, 2 * i + 2, n);

        return t; // 返回构建好的节点
    }

    // 如果索引越界或节点为空（用'#'表示），返回NULL
    return NULL;
}

代码逻辑解析¶

1. 顺序存储的二叉树¶

使用一维数组存储二叉树节点
对于索引为 i 的节点：
左子节点索引：2*i + 1
右子节点索引：2*i + 2
父节点索引：(i-1)/2（向下取整）
空节点用特殊字符（如'#'）表示

2. 算法思路¶

采用递归方式遍历数组
对每个非空节点创建对应的二叉树节点
通过索引关系递归构建左右子树

关键算法理解¶

1. 数组索引映射关系¶

完全二叉树的数组表示：¶

Text Only
1 2 3 4 5 6 7 8 9	`数组索引: 0 1 2 3 4 5 6 数组元素: [A, B, C, D, E, F, G] 对应的二叉树结构： A // 索引 0 / \ B C // 索引 1,2 / \ / \ D E F G // 索引 3,4,5,6`

索引关系验证：¶

节点A(索引0)：左子B(2×0+1=1)，右子C(2×0+2=2)
节点B(索引1)：左子D(2×1+1=3)，右子E(2×1+2=4)
节点C(索引2)：左子F(2×2+1=5)，右子G(2×2+2=6)

2. 图解说明¶

假设数组存储的二叉树：

Text Only
1 2 3 4 5 6 7 8 9 10	`数组：['A', 'B', 'C', 'D', '#', 'F', 'G'] 索引： 0 1 2 3 4 5 6 对应的二叉树结构： A // 索引 0 / \ B C // 索引 1,2 / / \ D F G // 索引 3,5,6 (索引4为空)`

构建过程：

Text Only

create(A, 0, 7): A[0]='A' ≠ '#'
├─ 创建节点A
├─ create(A, 1, 7): A[1]='B' ≠ '#'
│  ├─ 创建节点B
│  ├─ create(A, 3, 7): A[3]='D' ≠ '#'
│  │  ├─ 创建节点D
│  │  ├─ create(A, 7, 7): 7≥7 → 返回NULL
│  │  └─ create(A, 8, 7): 8≥7 → 返回NULL
│  │  └─ 返回节点D
│  └─ create(A, 4, 7): A[4]='#' → 返回NULL
│  └─ 返回节点B
└─ create(A, 2, 7): A[2]='C' ≠ '#'
   ├─ 创建节点C
   ├─ create(A, 5, 7): A[5]='F' ≠ '#'
   │  └─ ... → 返回节点F
   └─ create(A, 6, 7): A[6]='G' ≠ '#'
      └─ ... → 返回节点G
   └─ 返回节点C
└─ 返回根节点A

时间复杂度分析¶

1. 访问节点数¶

每个数组元素被访问 exactly 一次
总共访问 n 个元素

2. 每次访问的操作¶

索引比较：O(1)
内存分配：O(1)
赋值操作：O(1)
递归调用：O(1)

3. 总时间复杂度¶

O(n)，其中 n 是数组长度

空间复杂度分析¶

1. 额外空间使用¶

新创建的二叉树节点：O(n)
每个节点占用常量空间

2. 递归调用栈空间¶

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

3. 总空间复杂度¶

O(n)（节点存储）+ O(h)（递归栈）最坏情况下为 O(n)

边界条件处理¶

1. 索引越界检查¶

C
if (i < n && A[i] != '#')

- i < n：防止数组越界访问 - A[i] != '#'：跳过空节点

2. 空节点处理¶

用特殊字符'#'表示空节点
遇到空节点直接返回NULL

延伸知识点¶

1. 顺序存储与链式存储的对比¶

特性	顺序存储	链式存储
内存利用率	高（完全二叉树）	低（需要指针域）
插入/删除	复杂（需要移动元素）	简单（修改指针）
随机访问	O(1)	O(h)
空间浪费	可能（非完全二叉树）	少（按需分配）

2. 反向转换：二叉链表转顺序存储¶

C
// 计算二叉树节点数
int countNodes(BiTree root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->lchild) + countNodes(root->rchild);
}

// 二叉链表转顺序存储
void treeToArray(BiTree root, char A[], int i) {
    if (root == NULL) {
        A[i] = '#'; // 空节点用'#'表示
        return;
    }

    A[i] = root->data;
    treeToArray(root->lchild, A, 2 * i + 1);
    treeToArray(root->rchild, A, 2 * i + 2);
}

// 完整转换函数
char* convertTreeToArray(BiTree root, int* size) {
    *size = countNodes(root) * 2; // 估算数组大小
    char* A = (char*)malloc(*size * sizeof(char));
    treeToArray(root, A, 0);
    return A;
}

3. 层次遍历构建¶

C
// 使用队列进行非递归构建
BiTree createIterative(char A[], int n) {
    if (n == 0 || A[0] == '#') return NULL;

    BiTree root = (BiTree)malloc(sizeof(BTNode));
    root->data = A[0];
    root->lchild = root->rchild = NULL;

    Queue* queue = createQueue();
    enqueue(queue, root);

    int i = 1;
    while (!isEmpty(queue) && i < n) {
        BiTree node = dequeue(queue);

        // 处理左子节点
        if (i < n && A[i] != '#') {
            node->lchild = (BiTree)malloc(sizeof(BTNode));
            node->lchild->data = A[i];
            node->lchild->lchild = node->lchild->rchild = NULL;
            enqueue(queue, node->lchild);
        }
        i++;

        // 处理右子节点
        if (i < n && A[i] != '#') {
            node->rchild = (BiTree)malloc(sizeof(BTNode));
            node->rchild->data = A[i];
            node->rchild->lchild = node->rchild->rchild = NULL;
            enqueue(queue, node->rchild);
        }
        i++;
    }

    return root;
}

4. 优化的递归版本¶

C
// 带错误检查的版本
BiTree createSafe(char A[], int i, int n) {
    // 输入验证
    if (A == NULL || n <= 0 || i < 0) {
        return NULL;
    }

    // 边界检查
    if (i >= n) {
        return NULL;
    }

    // 空节点检查
    if (A[i] == '#') {
        return NULL;
    }

    // 创建节点
    BiTree node = (BiTree)malloc(sizeof(BTNode));
    if (node == NULL) {
        return NULL; // 内存分配失败
    }

    node->data = A[i];
    node->lchild = createSafe(A, 2 * i + 1, n);
    node->rchild = createSafe(A, 2 * i + 2, n);

    return node;
}

5. 实际应用场景¶

堆数据结构：优先队列的实现
完全二叉树操作：如堆排序
树形数据的序列化：网络传输、文件存储
游戏开发：四叉树、八叉树的空间分割
数据库索引：B树、B+树的存储

6. 内存管理优化¶

C
// 批量内存分配版本
typedef struct {
    BiTree nodes;
    int capacity;
    int used;
} NodePool;

BiTree createWithPool(char A[], int i, int n, NodePool* pool) {
    if (i >= n || A[i] == '#') return NULL;

    // 从内存池中获取节点
    if (pool->used >= pool->capacity) return NULL;

    BiTree node = &pool->nodes[pool->used++];
    node->data = A[i];
    node->lchild = createWithPool(A, 2 * i + 1, n, pool);
    node->rchild = createWithPool(A, 2 * i + 2, n, pool);

    return node;
}

这个算法体现了树的存储结构转换思想，是数据结构中重要的基础操作，广泛应用于各种实际场景中。