在二叉搜索树中删除有两个孩子的节点

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