이진 탐색 트리에서 두 자녀가있는 노드 삭제

Question

두 명의 자식이있는 노드를 삭제하려고합니다. 그러나, 내 함수는 트리에서 노드를 완전히 제거하지 않고 중복 된 상태로 남겨 둡니다.

void Remove(Node *&r, int idx) 
{ 
    if(Search(r, idx)) 
    { 
     if(idx < r->id)  Remove(r->left, idx); 
     else if(idx > r->id) Remove(r->right, idx); 
     else     DeleteNode(r); 

     //cout << "Account " << idx << " is now closed."; 
    } 
    else cout << "Account does not exist." << endl; 
} 

void DeleteNode(Node *&r) 
{ 
    Node *temp = r; 

    if(r->left == NULL && r->right != NULL) 
    { 
     r = temp->right; 
     delete temp; 
     temp = NULL; 
    } 
    else if(r->left != NULL && r->right == NULL) 
    { 
     r = temp->left; 
     delete temp; 
     temp = NULL; 
    } 
    else if(r->left == NULL && r->right == NULL) 
    { 
     r = NULL; 
     delete r; 
    } 
    else 
    { 
     // go to left of r and find largest value 
     temp = FindMax(r->left); 

     int tempID  = temp->id; 
     float tempBal  = temp->balance; 
     string tempString = temp->name; 

     DeleteNode(temp); 

     r->id = tempID; 
     r->balance = tempBal; 
     r->name = tempString; 
    } 
} 

Node* FindMax(Node *t) 
{ 
    while(t->right != NULL) 
    { 
     t = t->right; 
    } 
    return t; 
} 

은 가정하자 내가 가진이 나무 :

  33 
    22   44 
11  25 

이 22 삭제이 리드 : 당신이하는 것은 아닙니다 무엇

  33 
    22   44 
22  25 

Answer 1

temp = FindMax(r->left); 

을 여기

내 함수입니다 해야 할 것. DeleteNode(temp) 일 때 이전 노드는 여전히 트리에 있지만 temp은 덮어 씁니다. 부모의 right 회원을 덮어 쓰려고했다.