我们如何处理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（）失败，所以它们在这方面并没有真正的帮助。

我可以合乎逻辑地看到一个答案是“不要每次都使用递归并返回树的头部”。虽然我明白了为什么会这样，但我是一名本科TA，我们使用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; 
}