I need a delete node function for a binary search tree written in c++. The progr
ID: 3672090 • Letter: I
Question
I need a delete node function for a binary search tree written in c++. The program will take in commands through a file. Everything is already written except the delete node function.
#include<iostream>
#include<cstdlib>
#include<fstream>
using namespace std;
class bst
{
private:
struct node
{
int key;
node* left;
node* right;
};
node* root;
node* addLeafPrivate(int key, node* ptr);
void printInOrderPrivate(node* ptr);
void printPostOrderPrivate(node* ptr);
void printPreOrderPrivate(node* ptr);
void searchKeyPrivate(int key,node* ptr);
void findMinPrivate(node* ptr);
void findMaxPrivate(node* ptr);
public:
bst();
node* createLeaf(int key);
void addLeaf(int key);
void printInOrder();
void printPostOrder();
void printPreOrder();
void searchKey(int key);
void findMin();
void findMax();
};
bst::bst()
{
root = NULL;
}
bst::node* bst::createLeaf(int key)
{
node* n = new node;
n->key = key;
n->left = NULL;
n->right = NULL;
return n;
}
void bst::addLeaf(int key)
{
root = addLeafPrivate(key, root);
}
bst::node* bst::addLeafPrivate(int key, node* ptr)
{
if(ptr == NULL)
{
return createLeaf(key);
}
else if(key < ptr->key)
{
addLeafPrivate(key, ptr->left);
ptr->left = addLeafPrivate(key, ptr->left);
}
else if(key > ptr->key)
{
addLeafPrivate(key, ptr->right);
ptr->right = addLeafPrivate(key, ptr->right);
}
return ptr;
}
void bst::printInOrder()
{
printInOrderPrivate(root);
}
void bst::printPostOrder()
{
printPostOrderPrivate(root);
}
void bst::printPreOrder()
{
printPreOrderPrivate(root);
}
void bst::searchKey(int key)
{
searchKeyPrivate(key, root);
}
void bst::findMin()
{
findMinPrivate(root);
}
void bst::findMax()
{
findMaxPrivate(root);
}
void bst::printInOrderPrivate(node* ptr)
{
if(ptr != NULL)
{
printInOrderPrivate(ptr->left);
cout << ptr->key << " ";
printInOrderPrivate(ptr->right);
}
else
{
}
}
void bst::printPostOrderPrivate(node* ptr)
{
if(ptr == NULL)
return;
{
printPostOrderPrivate(ptr->left);
printPostOrderPrivate(ptr->right);
cout << ptr->key << " ";
}
}
void bst::printPreOrderPrivate(node* ptr)
{
if(ptr != NULL)
{
cout << ptr->key << " ";
printPreOrderPrivate(ptr->left);
printPreOrderPrivate(ptr->right);
}
else
{
}
}
void bst::searchKeyPrivate(int key, node* ptr)
{
if(ptr != NULL)
{
if (key == ptr->key)
{
cout << "We found " << key << endl;
}
else if(key < ptr->key)
{
searchKeyPrivate(key, ptr->left);
}
else if(key > ptr->key)
{
searchKeyPrivate(key, ptr->right);
}
}
else
{
cout << "We could not find your number" << endl;
}
}
void bst::findMinPrivate(node* ptr)
{
while(ptr->left != NULL)
{
ptr = ptr->left;
}
cout << "Min Value is: " << ptr->key;
}
void bst::findMaxPrivate(node* ptr)
{
while(ptr->right != NULL)
{
ptr = ptr->right;
}
cout << "Max value is: " << ptr->key;
}
int main()
{
ifstream file("cmd.txt");
int cmd, op;
bst bt;
while (file >> cmd)
{
switch (cmd)
{
case 1:
file >> op;
bt.addLeaf(op);
break;
case 2:
cout << "Inorder: ";
bt.printInOrder();
cout << endl;
break;
case 3:
cout << "Postorder: ";
bt.printPostOrder();
cout << endl;
break;
case 4:
cout << "Preorder: ";
bt.printPreOrder();
cout << endl;
break;
case 5:
file >> op;
bt.searchKey(op);
break;
case 8:
bt.findMin();
cout << endl;
break;
case 9:
bt.findMax();
cout << endl;
break;
}
}
return 0;
}
Explanation / Answer
Please find the required function below : /* deletes a node from the binary search tree */ void delete ( struct btreenode **root, int num ) { int found ; struct btreenode *parent, *x, *xsucc ; /* if tree is empty */ if ( *root == NULL ) { printf ( " Tree is empty" ) ; return ; } parent = x = NULL ; /* call to search function to find the node to be deleted */ search ( root, num, &parent, &x, &found ) ; /* if the node to deleted is not found */ if ( found == FALSE ) { printf ( " Data to be deleted, not found" ) ; return ; } /* if the node to be deleted has two children */ if ( x -> left != NULL && x -> right != NULL ) { parent = x ; xsucc = x -> right ; while ( xsucc -> left != NULL ) { parent = xsucc ; xsucc = xsucc -> left ; } x -> key = xsucc -> key ; x = xsucc ; } /* if the node to be deleted has no child */ if ( x -> left == NULL && x -> right == NULL ) { if ( parent -> right == x ) parent -> right = NULL ; else parent -> left = NULL ; free ( x ) ; return ; } /* if the node to be deleted has only rightchild */ if ( x -> left == NULL && x -> right != NULL ) { if ( parent -> left == x ) parent -> left = x -> right ; else parent -> right = x -> right ; free ( x ) ; return ; } /* if the node to be deleted has only left child */ if ( x -> left != NULL && x -> right == NULL ) { if ( parent -> left == x ) parent -> left = x -> left ; else parent -> right = x -> left ; free ( x ) ; return ; } }
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.