c - 当 malloc 在递归构建过程中失败时，我们如何处理释放 BST？

Question

我环顾四周，但找不到真正能解决这个想法的好来源。

首先:众所周知，我们应该始终检查 malloc() 和 realloc() 是否返回 null。这通常以类似于以下的方式完成:

Word* temp;
if ((temp = (Word*)malloc(sizeof(Word))) == NULL) {
    fprintf(stderr, "unable to malloc for node.\n");
    exit(EXIT_FAILURE);
}

但是，我们通常也以递归方式构建二叉搜索树，如下所示:

void buildTree(Word** tree, const char* input) {
    //See if we have found the spot to insert the node.
    //Do this by checking for NULL
    if (!(*tree)) {
        *tree = createNode(input);
        return;
    }
    //else, move left or right accordingly.
    if (strcmp(input, (*tree)->data) < 0)
        buildTree(&(*tree)->left, input);
    else
        buildTree(&(*tree)->right, input);
    return;
}

那么，如果我们开始处理海量数据集并且 malloc() 无法在递归 buildTree 函数中间分配内存，我们该怎么办？我已经尝试了很多方法来跟踪“全局错误”标志和“全局头”节点指针，但我尝试得越多，它似乎就变得越来越困惑。构建 BST 的示例似乎很少考虑 malloc() 失败的情况，因此它们在这方面并没有真正的帮助。

我从逻辑上可以看出，一个答案是“不要使用递归，每次都返回树头”。虽然我明白为什么这会起作用，但我是一名本科生助教，我们使用 BST 教授的内容之一就是递归。因此，当我们教授递归时对我的学生说“不要使用递归”将是弄巧成拙的。

任何想法、建议或链接将不胜感激。

Answer 1

我们通常使用返回错误并让调用者释放它，毕竟它可以很好地释放其他非关键资源并尝试再次插入节点。

#define BUILD_OK     0
#define BUILD_FAILED 1

int buildTree(Word** tree, const char* input) {
    int res;

    //See if we have found the spot to insert the node.
    //Do this by checking for NULL
    if (!(*tree)) {
        if (!(*tree = createNode(input)))
            return BUILD_FAILED;

        //Maybe other checks

        return BUILD_OK;
    }
    //else, move left or right accordingly.
    if (strcmp(input, (*tree)->data) < 0)
       res = buildTree(&(*tree)->left, input);
    else
       res = buildTree(&(*tree)->right, input);

    return res;
}