이 경우 왜 삭제하려고하는 Treenode가 삭제되지 않습니까?

Question

BST에서 값이 주어진 노드와 동일한 노드를 삭제하는 함수를 작성한 후 간단한 예제 [5,3,6]를 시도하고 키를 삭제합니다. 그러나이 코드를 실행하면 3이 삭제되지 않습니다. .이 코드의 출력 : 루트 = 5 왼쪽 = 3 오른쪽 = 6 왜? 감사! 당신이 null로 설정되어 있지 않기 때문에

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가 널 포인터가 아니다. cur을 NULL로 설정합니다. 따라서, 정의되지 않은 동작 인 삭제 된 포인터를 역 참조로 이동합니다. 귀하의 경우, 왼쪽 노드에 대해 이전에 할당 된 메모리는 변경되지 않고 쿼리 할 때 여전히 나타납니다.

Answer 2

문제는 매달린 포인터가 있다는 것입니다. "부모"노드에서 left을 NULL으로 설정해야합니다. 마찬가지로 오른쪽의 노드를 삭제하는 경우 부모의 right 포인터를 NULL 포인터로 설정해야합니다.