gpt4 book ai didi

c++ - 我在 BST 中的删除功能甚至不起作用

转载 作者:行者123 更新时间:2023-11-28 07:16:27 26 4
gpt4 key购买 nike

我需要创建一个删除函数,所以我一直在网上寻找,但我无法在我的程序中修复它。//在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
}

当我调试它时,它不起作用并显示 root{nProdID=??? nQuan=???余额=???..}。 if(current==NULL) return; 行错了吗?

最佳答案

在我看来这里有一个问题

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

当您找到该项目时,您编写它的前身的方式总是等于当前的。我想前任应该等于当前的 previous 值。

关于c++ - 我在 BST 中的删除功能甚至不起作用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20162073/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com