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

Question

我环顾四周，但找不到一个很好的来源来解决这个问题。

首先：众所周知，我们应该始终检查 malloc() 和 realloc() return 是否为 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 函数中间分配内存，我们该怎么办？我已经尝试了很多方法来跟踪 "global error" 标志和 "global head" 节点指针，但我尝试的越多，它似乎就越乱。使用构建 BST 的示例似乎很少考虑 malloc() 失败，因此它们在这方面并没有真正的帮助。

从逻辑上讲，我可以看到一个答案是 "Don't use recursion and return the head of the tree each time."，虽然我明白为什么会这样，但我是一名本科助教，我们使用 BST 教授的其中一件事是递归。因此，在我们教授递归时对我的学生说 "don't use recursion" 会弄巧成拙。

如有任何想法、建议或链接，我们将不胜感激。

Answer 1

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

#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;
}

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

How do we handle freeing a BST when malloc fails in the middle of our recursive build?

c

malloc

free

recursion

binary-search-tree