C语言递归函数无法将二叉搜索树数据填充至动态数组的问题

核心问题分析 #

你的代码中sorterToArray函数的索引参数i是值传递，每次递归调用时都会创建i的副本，递归内部对i的修改不会传递回上层调用。所有节点最终都会往数组的同一个索引位置写入数据，导致除最后一个写入的节点外，其他数据都被覆盖，这就是数组仅保留单个元素的根本原因。

次要问题补充 #

除核心的索引传递问题，代码还有两处需要修正：

1. 节点计数函数counter逻辑错误：原函数无法正确统计树的总节点数，会导致数组分配的空间大小错误。
2. 数组内存分配错误：writeSortedToArray中calloc(number, sizeof(int*))应该改为sizeof(int)，因为数组存储的是int类型值，而非指针。

修复方案及代码修改 #

1. 修改sorterToArray为指针传递索引

将索引i改为指针类型，让所有递归调用共享同一个索引变量：

void sorterToArray(struct treeNode* temp, int* pArray, int* i) {
    if (temp->left != NULL)
        sorterToArray(temp->left, pArray, i);

    pArray[*i] = temp->data;
    (*i)++;

    if (temp->right != NULL)
        sorterToArray(temp->right, pArray, i);
}

2. 修正writeSortedToArray调用方式

调用sorterToArray时传入索引的地址，并修正内存分配：

static int* writeSortedToArray(const BSTree tree)
{
    int number = counter(tree); // 修正后的counter直接返回节点数
    int* pArray = calloc(number, sizeof(int)); // 改为sizeof(int)
    assert(pArray != NULL);

    int i = 0;
    sorterToArray(tree, pArray, &i); // 传递i的地址

    return pArray;
}

3. 修复counter函数的节点计数逻辑

重新实现正确的节点计数：

int counter(const BSTree tree) {
    if (tree == NULL)
        return 0;
    // 递归统计左子树+右子树+当前节点
    return 1 + counter(tree->left) + counter(tree->right);
}

4. 添加测试输出（可选）

为验证修复效果，可在balanceTree中添加数组打印逻辑：

void balanceTree(BSTree* tree) {
    int* sortedArray = writeSortedToArray((*tree));
    int nodeCount = counter(*tree);
    printf("有序数组内容：");
    for (int i = 0; i < nodeCount; i++) {
        printf("%d ", sortedArray[i]);
    }
    free(sortedArray); // 释放内存避免泄漏
}

修复后效果 #

修改后，中序遍历会正确将二叉搜索树的元素按从小到大的顺序写入数组，所有节点的数据都会被保存到数组对应位置，不会出现覆盖或缺失的情况。

内容的提问来源于stack exchange，提问作者Ted Boman