在二叉搜索樹中刪除有兩個孩子的節點

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成員。