我在BST中的刪除功能不工作

Question

我需要創建一個刪除功能，所以我一直在網上看，但我無法修復它在我的程序中。 //中的defs.h

struct notesTree 
{ 
    int nProdID; 
    int nQuan; 
    int balance;   //will be used in AVL only, and be ignored in other cases. 
    notesTree* pLeftChild; 
    notesTree* pRightChild; 
}; 

//在storebin.cpp

void RemoveNode(notesTree* n, int item) 
{ 
    // Find the item 
    bool found = false; 
    notesTree* predecessor=NULL; 
    notesTree* current=n; 
    if(current==NULL) return; 
    while(current!=NULL) 
    { 
     if(current->nProdID==item) 
     { 
      predecessor = current; 
      found = true; 
      break; 
     } 
     else 
     { 
      predecessor = current; 
      if(item > (current->nProdID)) 
       current=current->pRightChild; 
      else 
       current=current->pLeftChild; 
     } 
    } 


    if(!found) 
    { 
     return; 
    } 
    // CASE 1: Removing a node with a single child 
    if((current->pLeftChild==NULL && current->pRightChild != NULL) || (current->pLeftChild != NULL && current->pRightChild==NULL)) 
    { 
     // Right Leaf Present, No Left Leaf 
     if(current->pLeftChild==NULL && current->pRightChild != NULL) 
     { 
      // If predecessor's left tree equals Node n 
      if(predecessor->pLeftChild==current) 
      { 
       // then predecessor's left tree becomes n's right tree 
       // and delete n 
       predecessor->pLeftChild=current->pRightChild; 
       delete current; 
       current=NULL; 
       cout<<item<<" has been removed from the Tree."<<endl; 
      } 
      // If predecessor's right tree equals Node n 
      else 
      { 
       // then predecessor's right tree becomes n's right tree 
       // and delete n 
       predecessor->pRightChild=current->pRightChild; 
       delete current; 
       current=NULL; 
       cout<<item<<" has been removed from the Tree."<<endl; 
      } 
     } 
     else // Left Leaf Present, No Right Leaf Present 
     { 
      if(predecessor->pLeftChild==current) 
      { 
       predecessor->pLeftChild=current->pLeftChild; 
       delete current; 
       current=NULL; 
       cout<<item<<" has been removed from the Tree."<<endl; 
      } 
      else 
      { 
       predecessor->pRightChild=current->pLeftChild; 
       delete current; 
       current=NULL; 
       cout<<item<<" has been removed from the Tree."<<endl; 
      } 
     } 
     return; 
    } 
    // CASE 2: Removing a Leaf Node 
    if(current->pLeftChild==NULL && current->pRightChild==NULL) 
    { 
     if(predecessor->pLeftChild==current) 
      predecessor->pLeftChild=NULL; 
     else 
      predecessor->pRightChild=NULL; 
     delete current; 
     cout<<item<<" has been removed from the Tree."<<endl; 
     return; 
    } 
    // CASE 3: Node has two children 
    // Replace Node with smallest value in right subtree 
    if(current->pLeftChild != NULL && current->pRightChild != NULL) 
    { 
     notesTree* check=current->pRightChild; 
     if((current->pLeftChild==NULL)&&(current->pRightChild==NULL)) 
     { 
      current=check; 
      delete check; 
      current->pRightChild==NULL; 
      cout<<item<<" has been removed from the Tree."<<endl; 
     } 
     else // Right child has children 
     { 
      // If the node's right child has a left child 
      // Move all the way down left to locate smallest element 
      if((current->pRightChild)->pLeftChild!=NULL) 
      { 
       notesTree* leftCurrent; 
       notesTree* leftCurrentPred; 
       leftCurrentPred=current->pRightChild; 
       leftCurrent=(current->pRightChild)->pLeftChild; 
       while(leftCurrent->pLeftChild != NULL) 
       { 
        leftCurrentPred=leftCurrent; 
        leftCurrent=leftCurrent->pLeftChild; 
       } 
       current->nProdID=leftCurrent->nProdID; 
       delete leftCurrent; 
       leftCurrentPred->pLeftChild==NULL; 
       cout<<item<<" has been removed from the Tree."<<endl; 
      } 
      else 
      { 
       notesTree* temp=current->pRightChild; 
       current->nProdID=temp->nProdID; 
       current->pRightChild=temp->pRightChild; 
       delete temp; 
       cout<<item<<" has been removed from the Tree."<<endl; 
      } 
     } 
     return; 
    } 
} 

我把它叫做

void doReserveEvent(notesTree* &root, int eventCode) 
{ 
    int tmpMSP = (eventCode % 10000)/10; 
    int tmpSoLuong = eventCode%10; 
    notesTree*pt; 
    pt=TimMSP(root,tmpMSP); 
    if(pt!=NULL) 
    { 
     pt->nQuan-=tmpSoLuong; 
     if(pt->nQuan<=0) 
     { 
      RemoveNode(root,tmpMSP); 
      return; 
     } 
    } 

    //o 
} 

當我調試它，它不能正常工作，並顯示根{nProdID = ??? nQuan = ???餘額= ??? ..}。如果（current == NULL）返回，是否行錯了？

Answer 1

在我看來就像一個問題是在這裏

while(current!=NULL) 
{ 
    if(current->nProdID==item) 
    { 
     predecessor = current; // <--- remove this line 
     found = true; 
     break; 

你寫它的方式，當你找到該項目的前身總是等於電流。我想，前任應該等於之前的值。