如何解決我的二叉搜索樹中的邏輯錯誤？

Question

所以我一直在試圖讓我的舊C++二進制搜索樹程序工作。它編譯和運行，但我沒有得到我期望的結果。如果我按順序插入c，d，a，b並嘗試刪除c，那麼我的remove函數會跳過if順序中的後續順序。爲什麼這兩個條件被跳過了？

也是使用gcc編譯的。

Node::Node(string nodeItem, 
      int nodeLine){ 
    item=nodeItem; 
    vector<int> tempVector; 
    tempVector.push_back(nodeLine); 
    lines=tempVector; 
    leftPtr = NULL; 
    rightPtr = NULL; 
} 


// recursive method for finding node containing the word 
Node* BST::find(string data, Node *curr) { 

    if(curr==NULL) { 
     cout << data << " is not in the tree" << endl; 
     return curr; 

    } 
    if(curr->getItem().compare("theplaceholder")==0){ 
     return curr; 
    } 
    string tempItem = curr->getItem(); 
    //this if statement is if I am inserting a word that is already in the tree 
    // or if I am removing the word from the tree 
    if(data.compare(tempItem)==0){ 
     return curr; 
    } 
    else if(data.compare(tempItem)<0){ 
     return find(data,curr->getLeftPtr()); 
    } 
    else{ 
     return find(data, curr->getRightPtr()); 
    } 

} 


void BST::insert(string data, int fromLine) { 
    Node *curr; 


    curr=find(data, root); 


    if(curr!=NULL && curr->getItem().compare("theplaceholder")==0){ 

     curr->setData(data); 

     curr->addLines(fromLine); 
    } 


    if(curr==NULL){ 

     // I want to point to a nonNull node. 
     // I am making a new node and having curr point to that instead of NULL 
     //then I set it to 



     curr=new Node(data, fromLine); 


     cout <<curr->getItem() << endl; 

     vector<int> foundLines=curr->getNodeLines(); 
     //cout<< "The word " <<curr->getItem() << " can be found in lines "; 
     if(foundLines.empty()) 
      cout << "foundLines is empty"; 
     int size=foundLines.size(); 
     for(int count=0; count<size; count++){ 

      //cout << foundLines[count] << ", "; 
     } 

    } 

    if(curr->getItem()==data){ 
     curr->addLines(fromLine); 
    } 
} 
// remove method I am trying to check for in order successors to swap with the deleted node. 
void BST::remove(string data) { 
    Node *curr=root; 


    Node *temp=find(data, curr); 
    if(temp==NULL){ 
     cout << " nothing to remove" << endl; 
    } 
    else if(temp->getRightPtr()!=NULL){ 

     curr=temp->getRightPtr(); 
     cout << curr->getItem() << endl; 
     while(curr->getLeftPtr()!=NULL){ 
      curr=curr->getLeftPtr(); 
      cout << curr->getItem() << endl; 
     } 
     temp->setData(curr->getItem()); 

     temp->setLines(curr->getNodeLines()); 
     delete curr; 
     curr=NULL; 
    } 
    else if(temp->getLeftPtr()!=NULL){ 
     cout <<"if !temp->getLeftPtr" << endl; 
     curr=temp->getLeftPtr(); 
     cout << curr->getItem() << endl; 
     while(curr->getRightPtr()!=NULL){ 
      curr=curr->getRightPtr(); 
      cout << curr->getItem() << endl; 
     } 
     temp->setData(curr->getItem()); 

     temp->setLines(curr->getNodeLines()); 
     delete curr; 
     curr=NULL; 
    } 
    else{ 
     cout <<"else delete temp" << endl; 
     delete temp; 
     temp=NULL; 

    } 

} 

Answer 1

原因此行

else if(temp->getRightPtr()!=NULL){ 

從來沒有成功的情況下，你從來沒有設置正確的指針的任何節點上 - getRightPtr只能返回null。如果你在構建它之後在調試器中檢查了你的樹的狀態，或者如果你通過了插入函數，你可能已經看到了這一點。這些問題是：

• 如果節點是不是在樹中的查找功能沒有返回null，而你插入功能預計它將
• 您插入功能需要定位在樹枝上，位置這個節點應該是 - 或者通過修復find函數或者自己，然後創建一個新節點並且根據需要在左側或右側從父節點添加一個引用
• 您的插入函數出現在行編號到第一次插入的節點兩次：一次覆蓋佔位符，一次在插入末尾（而不是在這裏使用佔位符，我可能已經初始化爲root爲nu當創建第一個節點時，設置root = curr）
• 當從左手分支中提升最高節點時，您的remove函數需要做更多的工作;它需要
  • 正確地清理該節點從它以前的母公司 - 此刻你刪除的對象，而是獨自離開
  • 任何懸擺指針促進該節點的任何孩子你將它拿以前的插槽前

即

 D          C       
    /\         /\ 
    A E remove 'D'      A E 
    \  => 'C' is highest on left  \ 
     C   but need to move B to C  B 
    /
    B