내 이진 검색 트리에서 논리 오류를 수정하는 방법?

Question

그래서 나는 work.It에 내 오래된 C + + 이진 검색 트리 프로그램을 얻으려고 노력하고 컴파일하고 실행하지만 내가 기대하는 결과를 얻을하지 않습니다. 순서대로 c, d, a, b를 삽입하고 c를 제거하려고하면 내 제거 함수는 후속 연산에서 찾을 if 조건을 건너 뜁니다. 조건문을 건너 뛰면 왜 그 2 개가 더 나옵니까?

또한 gcc를 사용하여 컴파일됩니다. getRightPtr는 null을 반환 할 수 있습니다 -

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){ 

이 성공 결코이 라인은 모든 노드에서 올바른 포인터를 설정하지 것입니다. 디버거에서 트리의 상태를 조사한 후에 디버거에서 상태를 검사했거나 삽입 기능을 통해 단계적으로 살펴 본 경우 아마 이걸 보았을 것입니다. 문제는 다음과 같습니다 노드가 트리에없는 경우

가

• 당신의 찾기 기능이 null 반환하지 않습니다, 당신의 삽입 기능이 기대하는 반면 그 것이다
하여 삽입 기능은 트리 곳에서 위치를 찾을 필요가
• 이 노드는 찾기 기능을 수정하거나 자체적으로해야합니다. 그런 다음 새 노드를 만들고 부모 노드에서 왼쪽 또는 오른쪽에 참조를 추가합니다.
• 삽입 기능이 선으로 표시됩니다. 첫 번째 삽입 된 노드에 번호 : 두 번 한 번 : 자리 표시자를 덮어 쓰고 한 번 삽입 할 때 한 번 (자리 표시자를 사용하는 대신 여기 NUM이되도록 root을 초기화했을 것입니다.) ll 대신 첫 번째 노드를 만들 때 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