This program is a binary search tree of string to store information of students with the following details such as id, name and CGPA. And using unique id of a student to search, delete and insert different data. But in deletion when a subtree is involved the tree gets separated, I don't know what I'm doing wrong.
#include <iostream>
using namespace std;
struct BstNode
{
string iD;
string name;
float cgpa;
BstNode *left;
BstNode *right;
};
BstNode *root;
BstNode *GetNewNode(string iD0, string n0, float cg0)
{
BstNode *NewNode = new BstNode();
NewNode->iD = iD0;
NewNode->name = n0;
NewNode->cgpa = cg0;
NewNode->left = NULL;
NewNode->right = NULL;
return NewNode;
}
void PreOrder(BstNode *root)
{
if (root == NULL)
{
return;
}
cout << "ID: " << root->iD << "\nNAME: " << root->name << "\nCGPA: " << root->cgpa << endl;
PreOrder(root->left);
PreOrder(root->right);
}
void InOrder(BstNode *root)
{
if (root == NULL)
{
return;
}
InOrder(root->left);
cout << "ID: " << root->iD << "\nNAME: " << root->name << "\nCGPA: " << root->cgpa << endl;
InOrder(root->right);
}
void PostOrder(BstNode *root)
{
if (root == NULL)
{
return;
}
PostOrder(root->left);
PostOrder(root->right);
cout << "ID: " << root->iD << "\nNAME: " << root->name << "\nCGPA: " << root->cgpa << endl;
cout << endl;
}
BstNode *Insert(BstNode *root, string iD2, string n2, float cg2)
{
if (root == NULL)
{
root = GetNewNode(iD2, n2, cg2);
}
else if (iD2 <= root->iD)
{
root->left = Insert(root->left, iD2, n2, cg2);
}
else
{
root->right = Insert(root->right, iD2, n2, cg2);
}
return root;
}
BstNode *Rectify(BstNode *root, string id1, string n, float cg)
{
root->iD = id1;
root->name = n;
root->cgpa = cg;
return root;
}
struct BstNode *FindMin(BstNode *root)
{
struct BstNode* current = root;
/* loop down to find the leftmost leaf */
while (current && current->left != NULL)
current = current->left;
return current;
}
BstNode *Delete(BstNode *root, string data)
{
if (root == NULL)
return root;
else
{
if (data < root->iD)
root->left = Delete(root->left, data);
else if (data > root->iD)
root->right = Delete(root->right, data);
else
{
if (root->left == NULL and root->right == NULL)
return NULL;
else if (root->left == NULL)
{
struct BstNode *temp = root->right;
delete(root);
return temp;
}
else if (root->right == NULL)
{
struct BstNode *temp = root->left;
delete(root);
return temp;
}
else
{
struct BstNode *temp = FindMin(root->right);
root->iD = temp->iD;
root->name = temp->name;
root->cgpa = temp->cgpa;
root->right = Delete(root->right, temp->iD);
}
}
return root;
}
}
BstNode *Search(BstNode * root, string iDs)
{
cout << "Finding " << endl;
if (root == NULL)
{
cout << "No such info!" << endl;
return root;
}
else if (root->iD == iDs)
{
cout << "Found 0 " << endl;
cout << "ID: " << root->iD << endl;
cout << "NAME: " << root->name << endl;
cout << "CGPA: " << root->cgpa << endl;
bool done = false;
while (!done)
{
cout << "Would you like to update this student's information? [y/n]\n";
string x;
cin >> x;
if (x == "y")
{
cout << "The following fields are updatable:\n";
cout << "1. Student ID\n";
cout << "2. Student Name\n";
cout << "3. Student CGPA\n";
cout << "4. Remove Student\n";
cout << "Enter your choice:\n";
bool done1 = false;
while (!done1)
{
int ch;
cin >> ch;
if (ch == 1)
{
cout << "Please enter new ID: \n";
string nwid;
cin >> nwid;
cout << "============================" << endl;
cout << "Updating \n";
cout << "============================" << endl;
root = Rectify(root, nwid, root->name, root->cgpa);
cout << "============================" << endl;
cout << "Updated Successfully! \n";
cout << "============================" << endl;
cout << "============================" << endl;
cout << root->iD << endl;
cout << root->name << endl;
cout << root->cgpa << endl;
cout << "============================" << endl;
done1 = true;
}
else if (ch == 2)
{
cout << "Please enter new name: \n";
string nwname;
cin >> nwname;
cout << "============================" << endl;
cout << "Updating \n";
cout << "============================" << endl;
root = Rectify(root, root->iD, nwname, root->cgpa);
cout << "============================" << endl;
cout << "Updated Successfully! \n";
cout << "============================" << endl;
cout << "============================" << endl;
cout << root->iD << endl;
cout << root->name << endl;
cout << root->cgpa << endl;
cout << "============================" << endl;
done1 = true;
}
else if (ch == 3)
{
cout << "Please enter new CGPA: \n";
float nwcg;
cin >> nwcg;
cout << "============================" << endl;
cout << "Updating \n";
cout << "============================" << endl;
root = Rectify(root, root->iD, root->name, nwcg);
cout << "============================" << endl;
cout << "Updated Successfully! \n";
cout << "============================" << endl;
cout << "============================" << endl;
cout << root->iD << endl;
cout << root->name << endl;
cout << root->cgpa << endl;
cout << "============================" << endl;
done1 = true;
}
else if (ch == 4)
{
cout << "Removing\n";
root = Delete(root, root->iD);
cout << "Removed!\n";
return root;
done1 = true;
}
else
{
cout << "Wrong input try again! \n";
}
}
done = true;
}
else if (x == "n")
{
done = true;
}
else
{
cout << "Wrong input try again! \n";
}
}
return root;
}
else if (iDs <= root->iD)
{
return Search(root->left, iDs);
}
else
{
return Search(root->right, iDs);
}
}
int main()
{
root = NULL;
root = Insert(root, "21-44631-1", "Rafiul", 3.75);
root = Insert(root, "21-44531-1", "Haque", 4.0);
root = Insert(root, "21-44431-1", "Rafsun", 3.78);
root = Insert(root, "21-44331-1", "Rafi", 3.5);
root = Insert(root, "21-44231-1", "ABC", 4.0);
root = Insert(root, "21-44611-1", "AC", 4.0);
cout << "Please enter the ID you want to search: ";
string s;
cin >> s;
cout << endl;
Search(root, s);
cout << "Reading tree in preorder : \n";
PreOrder(root);
cout<<"============================"<< endl;
cout << "\nReading tree in inorder : \n";
InOrder(root);
cout<<"============================"<< endl;
cout << "\nReading tree in postorder : \n";
PostOrder(root);
cout << "============================" << endl;
}
