// Helper Function for the Destructor
void binST::binST_Destroy(Node* n)
{
if(n->left != nullptr)
binST_Destroy(n->left);
if(n->right != nullptr)
binST_Destroy(n->right);
delete n;
n=nullptr;
}
// Helper Size Function
int binST::binST_Size(Node* n)
{
if(n=nullptr)
return 0;
elsereturn(binST_Size(n->left)+binST_Size(n->right)+1);
}
// Insert Function
void binST::binST_Insert(Node*& n, int item)
{
// If node is null, create a new node with input data
if(n==nullptr)
{
n=new Node(item);
}
else
{
// Check to see if data being inserted is < current node->data
if(item < (n->data))
// recursive call with left child node input node
binST_Insert((n->left), item);
// Check to see if data being inserted is > current node->data
elseif(item > (n->data))
{
// recursive call with left child node input node
binST_Insert((n->right), item);
}
else
// If item is a duplicate, output duplicate message
cout<<item<<" is a duplicate"<<endl;
}
}
// Erase Function (I'm almost positive that it has to be somewhere inside here)
void binST::binST_Erase(Node* n, int item)
{
// Find the item
bool found = false;
Node* predecessor=nullptr;
Node* current=n;
if(current==nullptr)
return;
while(current!=nullptr)
{
if(current->data==item)
{
found = true;
predecessor = current;
break;
}
else
{
predecessor = current;
if(item > (current->data))
current=current->right;
else
current=current->left;
}
}
if(!found)
{
cout<<item<<" not in Tree."<<endl;
return;
}
// CASE 1: Removing a node with a single child
if((current->left==nullptr && current->right != nullptr) || (current->left != nullptr && current->right==nullptr))
{
// Right Leaf Present, No Left Leaf
if(current->left==nullptr && current->right != nullptr)
{
// If predecessor's left tree equals Node n
if(predecessor->left==current)
{
// then predecessor's left tree becomes n's right tree
// and delete n
predecessor->left=current->right;
delete current;
current=nullptr;
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->right=current->right;
delete current;
current=nullptr;
cout<<item<<" has been removed from the Tree."<<endl;
}
}
else // Left Leaf Present, No Right Leaf Present
{
if(predecessor->left==current)
{
predecessor->left=current->left;
delete current;
current=nullptr;
cout<<item<<" has been removed from the Tree."<<endl;
}
else
{
predecessor->right=current->left;
delete current;
current=nullptr;
cout<<item<<" has been removed from the Tree."<<endl;
}
}
return;
}
// CASE 2: Removing a Leaf Node
if(current->left==nullptr && current->right==nullptr)
{
if(predecessor->left==current)
predecessor->left=nullptr;
else
predecessor->right=nullptr;
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->left != nullptr && current->right != nullptr)
{
Node* check=current->right;
if((current->left==nullptr)&&(current->right==nullptr))
{
current=check;
delete check;
current->right==nullptr;
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->right)->left!=nullptr)
{
Node* leftCurrent;
Node* leftCurrentPred;
leftCurrentPred=current->right;
leftCurrent=(current->right)->left;
while(leftCurrent->left != nullptr)
{
leftCurrentPred=leftCurrent;
leftCurrent=leftCurrent->left;
}
current->data=leftCurrent->data;
delete leftCurrent;
leftCurrentPred->left==nullptr;
cout<<item<<" has been removed from the Tree."<<endl;
}
else
{
Node* temp=current->right;
current->data=temp->data;
current->right=temp->right;
delete temp;
cout<<item<<" has been removed from the Tree."<<endl;
}
}
return;
}
}
If someone with a fresher pair of eyes could help me out with a little advice, then that would be greatly appreciated. Thank you!
