バイナリ検索ツリーからノードを削除するには

Question

バイナリ検索ツリーからノードを削除する関数を実装するにはどうすればよいですか？以下は私の現在の関数である：それは私は非常に近いが、ときだように私は感じて立ったよう

void remove(TreeNode *&tree, ANY num) {//Removed Need for ">" 
    if (tree == NULL){ 
     return; 
    } 

    if (tree->value == num) { 
     makeDeletion(tree); 
    } else if (num < tree->value) { 
     remove(tree->left, num); 
    } else { 
     remove(tree->right, num); 
    } 
};//Remove 

：

void makeDeletion(TreeNode *&tree) { 
    TreeNode *NodeToDelete; 
    NodeToDelete = tree; 
    TreeNode *InOrder; 

    if (tree->right == NULL && tree->left == NULL) { 
     delete NodeToDelete; 
    } 
    if (tree->right == NULL) { 
     tree = tree->left; 
     delete NodeToDelete; 
    } 
    else if (tree->left == NULL) { 
     tree = tree->right; 
     delete NodeToDelete; 
    } 
    else { 
     InOrder = tree->right; 
     while (InOrder->left != NULL) { 
      InOrder = InOrder->left; 
     } 

     NodeToDelete->value = InOrder->value; 
     remove(InOrder, InOrder->value); 
    } 
} 

そして、ここでは、私はそれを削除する値を見つけていremove機能ですプログラムがクラッシュするバイナリツリーの内容を出力します。私は、ノードが2人の子供を持っている場合、次の順番でノードの値をスワップし、そのノードの後継者とノードを「削除」し、その後継者を削除するアプローチを使用しようとしています。 。 remove機能を調整しないと、makeDeletion機能を説明どおりに動作させるために、どのような情報が欠けていますか？

編集：makeDeletion機能私は誤って2つの文を連続して書きました。 2番目のifステートメントはelse ifステートメントでなければなりません。 makeDeletionで

Answer 1

treeは（leftとright両方がNULLある）の葉であれば、あなたはリーフノードを削除し、tree = nullptrを設定しないでください。これにより、解放されたメモリへの参照がツリーに残されます。また、次のifの（今削除された）ノードを逆参照します。いずれかがクラッシュする可能性があります。