我們如何處理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; 
}