c++ - 如何修复我的二叉搜索树中的逻辑错误？

Question

所以我一直在尝试让我的一个旧的 c++ 二叉搜索树程序工作。它编译并运行但我没有得到我期望的结果。如果我按顺序插入 c、d、a、b 并尝试删除 c，我的删除函数将跳过按顺序查找后继者的 if 条件。为什么那些 else 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，而您的插入函数期望它会返回 null
• 您的插入函数需要定位该节点在树中的位置 - 通过修复查找函数或自行定位，然后创建一个新节点并从父节点添加对它的引用，在左侧或右侧视情况而定
• 您的插入函数两次显示第一个插入节点的行号:一次是在您覆盖占位符时，一次是在插入结束时(而不是在这里使用占位符，我可能已经初始化了 root 为空，而是在创建第一个节点时设置 root = curr)
• 从左侧分支提升最高节点时，您的删除函数需要做更多的工作；它需要
  • 正确地从它的前一个父节点中清除该节点 - 在您删除该对象但保留任何悬空指针的那一刻
  • 在移动该节点以占用其先前位置之前提升该节点的所有子节点

即

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