爲什麼在這種情況下，Treenode I嘗試刪除不會被刪除？

Question

我寫了一個函數來刪除一個BST的值等於給定鍵的節點，我試了一個簡單的例子[5,3,6]，並刪除了鍵= 3。但是當我運行這個代碼時，3沒有被刪除。此代碼的輸出： root = 5 left = 3 right = 6 爲什麼？謝謝！

struct TreeNode { 
    int val; 
    TreeNode *left; 
    TreeNode *right; 
    TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
}; 

// delete key in the tree 
TreeNode* deleteNode(TreeNode* root, int key) { 
    TreeNode* cur = root; 
    // find the node to delete 
    while(cur) { 
     if(cur->val == key) break; 
     if(cur->val > key) cur = cur->left; 
     else cur = cur->right; 
    } 
    if(!cur) return root; 
    // I want to delete the node of val 3 here 
    // here cur == root->left, I though when I do cur = 0, root->left will also be set to 0 
    if(!cur->left && !cur->right) { 
     assert(cur == root->left); 
     delete cur; 
     cur = 0; 
    } 
    if(root) cout << "root = " << root->val << endl; 
    // but root->left is not nullptr when I ran this, and 3 still exists 
    if(root->left) cout << "left = " << root->left->val << endl; 
    if(root->right) cout << "right = " << root->right->val << endl; 
    return root; 
} 

int main() { 
    TreeNode* root = new TreeNode(5); 
    TreeNode* l = new TreeNode(3); 
    TreeNode* r = new TreeNode(6); 
    root->left = l; 
    root->right = r; 
    deleteNode(root, 3); 
} 

Answer 1

root->left是不是一個空指針，因爲你永遠不將其設置爲NULL。您將cur設置爲NULL。因此，您繼續取消引用已刪除的指針，這是未定義的行爲。在你的情況下，以前爲左節點分配的內存保持不變，並且在查詢時仍然存在。

Answer 2

問題是你有一個懸掛指針。您需要在「父」節點中將left設置爲NULL。同樣，如果刪除右側的節點，則需要將父節點的right指針設置爲NULL。