バイナリツリーのリーフノードを削除します

Question

バイナリ検索ツリーからleaf nodeを削除しようとしていますが、それは私にとってはうまくいかず、コードをデバッグしても問題が見つかりません。私は流れが正確であることを見ることができます、呼び出しはleaf nodeアドレスに達し、freeを呼び出します。しかしその後、私がpre-orderを実行したとき、私は値がまだそこにあるのを見ます。

私が作成したバイナリツリー（そのシンプルな1） - ：= 14削除する

      10 
         / \ 
         6  14 

Leaf Node値。

削除前Pre - orderトラバーサル結果= 10->6->14。これは私のコンソールに表示されます。 leaf node削除する

コード - ：

// Delete a leaf node 

void deleteNode(struct Nodes * root,int value){ 

    // Check if root is null 

    if (root == NULL) { 
     return; 
    } 

    // If no left and right node present, it's a leaf node. Perform delete. 

    while (root->left == NULL && root->right == NULL) { 

     // Check if value at leaf node is same as value to be deleted. If yes, go inside (if). 

     if (root->info == value) { 
      printf("Delete the leaf node \n"); 

      printf("delete node address is \n %p",root); 

      // free the root (which is currently a leaf node) 
      free(root); 
      return; 
     } 
    } 

    // keep checking if value to be deleted is on right or left, till a value is found. 

    if (root->info < value) { 
     // Ccheck on right 
     deleteNode(root->right,value); 
    }else{ 
     // check on left 
     deleteNode(root->left,value); 
    } 

} 

を私はerrorsを得ることはありませんので、私は根本原因を推測することはできませんよ。

削除後Pre - orderトラバーサル結果= 10->6->14。誰か助けてくれますか？私は非常にばかげたミスをしていることを知っている、または私のコンセプトはまだ透明ではありません。

その他の情報が必要な場合は教えてください。

画像の出力 - ：私は正しい値と同じアドレスを参照してください。

Answer 1

freeは、「私は、それがfree'dまたは任意に再割り当てすることができる任意のより多くのメモリを使用することはありません誓う」かなり多くを意味します。

あなたはその約束に違反しています。メモリを解放した後、そのアドレス上のすべての参照を忘れる必要があります。親ノードは、ノードが以前に使用されたアドレスを覚えており、偶然メモリがまだリサイクルされていない。

典型的な「フリー後に使用」エラーがあります。その間に別のノードを割り当てていた場合は、もう一度トラバースする前に、メモリが破損していることに気がつきました。

親オブジェクトのポインタを指し示すパラメータを関数にもう1つ追加できます。そうすれば、親を変更することができます。

ノード内の親に参照を戻す。

どちらかが動作します。

Answer 2

1つのアプローチは、再帰呼び出しでポインタを親に渡すことです。

void deleteNode(struct Nodes *root, struct Nodes *parent, int value){ 

    // Check if root is null 

    if (root == NULL) { 
     return; 
    } 

    if ((root->info == value) && (root->left == NULL) && (root->right == NULL)) { 
     if (parent->left->info == value) {free(parent->left); parent->left = NULL;} 
     else {free(parent->right); parent->right = NULL;} 
    } 
    else if (root->info < value) { 
     // check on right 
     deleteNode(root->right,root, value); 
    }else{ 
     // check on left 
     deleteNode(root->left,root, value); 
    } 
}