バイナリ検索ツリーの削除機能に問題がある

Question

バイナリ検索ツリーから特定の値を削除しようとしています。この関数は、指定された値が存在する場合は1を返し、存在しない場合は0を返します。私は値を適切に返すとは思わない。適切な値は削除されているようですが、削除してはいけないときに削除メッセージを表示して、関数が0でないはずであることを示しています。誰かが私の誤りを見つけるのを助けることができますか？ありがとう。

/*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

自分自身を再帰的に呼び出すときは、再帰呼び出しの値を返す必要があります。だから、変更：

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

に：

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

と同様に右のケースのために。これがなければ、これらのケースでは0を返すだけです。

Answer 2

関数を呼び出すとき、あなたは戻り値を使用していませんでした

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

で

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

を交換してください。