Probleme mit einem binären Suchbaum entfernen Funktion

Question

Ich versuche, einen bestimmten Wert aus einem binären Suchbaum zu entfernen. Die Funktion gibt 1 zurück, wenn der angegebene Wert vorhanden war, und 0, wenn dies nicht der Fall war. Ich glaube nicht, dass ich Werte richtig zurückgebe. Die richtigen Werte scheinen entfernt zu sein, aber ich drucke eine Entfernungsnachricht, wenn ich nicht sollte, was anzeigt, dass die Funktion 0 zurückgibt, wenn es nicht sein sollte. Kann mir jemand helfen, meinen Fehler zu erkennen? Vielen Dank. Ersetzen

/*Remove data from BST pointed to by rootRef, changing root if necessary. 
* For simplicity's sake, always choose node's in-order 
* successor in the two-child case. 
* Memory for removed node should be freed. 
* Return 1 if data was present, 0 if not found. */ 

int removeBST(struct TreeNode** rootRef, int data) 
{ 
    struct TreeNode* heir; 
    struct TreeNode* prev; 

    if(*rootRef == NULL) 
    { 
    return 0; 
    } 

    if(data < (*rootRef)->data) 
    { 
    removeBST(&(*rootRef)->left, data); 
    } 
    else if(data > (*rootRef)->data) 
    { 
    removeBST(&(*rootRef)->right, data); 
    } 
    else 
    { 
    struct TreeNode* temp; 

    if((*rootRef)->right == NULL) 
    { 
     temp = *rootRef; 
     *rootRef = (*rootRef)->left; 
     free(temp); 
    } 
    else if((*rootRef)->left == NULL) 
    { 
     temp = *rootRef; 
     *rootRef = (*rootRef)->right; 
     free(temp); 
    } 
    else 
    { 
     heir = (*rootRef)->left; 
     prev = *rootRef; 

     while(heir->right != NULL) 
     { 
     prev = heir; 
     heir = heir->right; 
     } 

     (*rootRef)->data = heir->data; 

     if(prev != *rootRef) 
     { 
     prev->right = heir->left; 
     } 
     else 
     { 
     prev->left = heir->left; 
     } 
     free(heir); 
    } 
    return 1; 
    } 
    return 0; 
} 

Answer 1

Wenn es sich selbst rekursiv aufruft, muss es den Wert aus dem rekursiven Aufruf zurückgeben. So ändern:

removeBST(&(*rootRef)->left, data); 

zu:

return removeBST(&(*rootRef)->left, data); 

und in ähnlicher Weise für den rechten Fall. Ohne dies fällt es einfach durch und gibt 0 für diese Fälle zurück.

Answer 2

if(data < (*rootRef)->data) 
{ 
    removeBST(&(*rootRef)->left, data); 
} 
else if(data > (*rootRef)->data) 
{ 
    removeBST(&(*rootRef)->right, data); 
} 

mit

if(data < (*rootRef)->data) 
{ 
    return removeBST(&(*rootRef)->left, data); 
} 
else if(data > (*rootRef)->data) 
{ 
    return removeBST(&(*rootRef)->right, data); 
} 

Wenn Sie die Funktion aufrufen, haben Sie nicht den Rückgabewert verwenden.