1

所以我一直在尝试让我的一个旧的 c++ 二叉搜索树程序工作。它编译并运行，但我没有得到我期望的结果。如果我按该顺序插入 c、d、a、b 并尝试删除 c，我的删除函数会跳过在顺序后继中找到的 if 条件。如果跳过条件，为什么还有其他 2 个？

它也是使用 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;

    }

}
4

1 回答 1

0

这条线的原因

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

永远不会成功是您从未在任何节点上设置正确的指针 - getRightPtr 只能返回 null。如果您在构建树后在调试器中检查了树的状态，或者您单步执行了插入函数，您可能已经看到了这一点。问题是：

  • 如果节点不在树中，您的 find 函数不会返回 null ，而您的 insert 函数期望它会
  • 您的插入函数需要在树中找到该节点应位于的位置 - 通过修复 find 函数或自己，然后创建一个新节点并从左侧或右侧的父节点添加对它的引用适当的一面
  • 您的插入函数将第一个插入的节点的行号显示两次：一次是覆盖占位符时，一次是在插入结束时（而不是在这里使用占位符，我可能已经初始化root为 null 而是设置 root = curr创建第一个节点时）
  • 从左侧分支提升最高节点时，您的删除功能需要做更多的工作；它需要
    • 从它的前一个父节点中正确清理该节点 - 此时您删除对象但不理会任何悬空指针
    • 在移动该节点以占用其上一个插槽之前提升该节点的任何子节点

IE

      D                                       C                           
     / \                                     / \
    A   E  remove 'D'                       A   E
     \       => 'C' is highest on left       \
      C         but need to move B to C       B
     /
    B
于 2012-07-16T14:48:40.237 回答