如何将使用vector的C++ BST节点存储代码改为C语言数组实现？

核心修改说明 #

• 修正函数参数：原代码的int arr[]类型错误，我们需要存储Node*类型的节点指针，因此要改为Node** arr；同时新增int* cur_idx参数，全局跟踪数组当前写入位置，替代C++ vector自动维护的尾部索引。
• nodes.push_back(root)的对应实现：将当前root指针写入数组的*cur_idx位置，再对*cur_idx执行自增操作即可，注意要加括号避免运算符优先级错误。

完整实现代码 #

// 提前定义Node结构体示例
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

void storeBSTNodes(Node* root, Node** arr, int* cur_idx)
{
    if (root == NULL)
        return;

    storeBSTNodes(root->left, arr, cur_idx);
    // 对应C++版本的nodes.push_back(root)
    arr[*cur_idx] = root;
    (*cur_idx)++; // 括号不可省略，避免运算符优先级错误
    storeBSTNodes(root->right, arr, cur_idx);
}

调用示例 #

使用前需要先统计BST总节点数，申请对应大小的数组空间：

// 统计BST节点总数的辅助函数
int countNodes(Node* root) {
    if (root == NULL) return 0;
    return countNodes(root->left) + countNodes(root->right) + 1;
}

// 业务调用逻辑
int main() {
    Node* root = /* 你的BST根节点 */;
    int nodeTotal = countNodes(root);
    // 申请存储节点指针的数组
    Node** nodeArr = (Node**)malloc(sizeof(Node*) * nodeTotal);
    int curIdx = 0;
    // 调用存储函数，传入索引的地址保证所有递归层级共享同一个索引
    storeBSTNodes(root, nodeArr, &curIdx);

    // 后续可使用nodeArr的中序序列完成平衡BST重构等操作
    // ... 你的业务代码

    // 释放申请的数组空间
    free(nodeArr);
    return 0;
}

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