
- 20th Oct 2022
- 00:40 am
#include<iostream>
#include<vector>
#include<fstream>
#include<sstream>
#include<string>
#include<algorithm>
using namespace std;
int n = 1;
struct tree
{
int data;
struct tree *leftchild;
struct tree *rightchild;
}*root;
class BST
{
public:
BST()
{
root = NULL;
}
void insert(tree * t, tree * newnode)
{
if (root == NULL)
{
root = new tree;
root->data = newnode->data;
root->leftchild = NULL;
root->rightchild = NULL;
cout << "Root Node is Added" << endl;
return;
}
if (t->data == newnode->data)
{
cout << "Element already in the tree" << endl;
return;
}
if (t->data > newnode->data)
{
if (t->leftchild != NULL)
{
insert(t->leftchild, newnode);
}
else
{
t->leftchild = newnode;
(t->leftchild)->leftchild = NULL;
(t->leftchild)->rightchild = NULL;
cout << "Node Added To Left" << endl;
return;
}
}
else
{
if (t->rightchild != NULL)
{
insert(t->rightchild, newnode);
}
else
{
t->rightchild = newnode;
(t->rightchild)->leftchild = NULL;
(t->rightchild)->rightchild = NULL;
cout << "Node Added To Right" << endl;
return;
}
}
}
void find(int key, tree **parent, tree **location)
{
tree *ptr, *ptrsave;
if (root == NULL)
{
*location = NULL;
*parent = NULL;
return;
}
if (key == root->data)
{
*location = root;
*parent = NULL;
return;
}
if (key < root->data)
ptr = root->leftchild;
else
ptr = root->rightchild;
ptrsave = root;
while (ptr != NULL)
{
if (key == ptr->data)
{
*location = ptr;
*parent = ptrsave;
return;
}
ptrsave = ptr;
if (key < ptr->data)
ptr = ptr->leftchild;
else
ptr = ptr->rightchild;
}
*location = NULL;
*parent = ptrsave;
}
void deleteElement(int item)
{
tree *parent, *location;
if (root == NULL)
{
cout << "Tree empty" << endl;
return;
}
find(item, &parent, &location);
if (location == NULL)
{
cout << "Item not present in tree" << endl;
return;
}
else
{
cout << "Item Deleted"<<endl;
}
if (location->leftchild == NULL && location->rightchild == NULL)
{
if (parent == NULL)
{
root = NULL;
}
else
{
if (location == parent->leftchild)
parent->leftchild = NULL;
else
parent->rightchild = NULL;
}
}
if (location->leftchild != NULL && location->rightchild == NULL)
{
tree *child;
if (location->leftchild != NULL)
child = location->leftchild;
else
child = location->rightchild;
if (parent == NULL)
{
root = child;
}
else
{
if (location == parent->leftchild)
parent->leftchild = child;
else
parent->rightchild = child;
}
}
if (location->leftchild == NULL && location->rightchild != NULL)
{
tree *child;
if (location->leftchild != NULL)
child = location->leftchild;
else
child = location->rightchild;
if (parent == NULL)
{
root = child;
}
else
{
if (location == parent->leftchild)
parent->leftchild = child;
else
parent->rightchild = child;
}
}
if (location->leftchild != NULL && location->rightchild != NULL)
{
tree *ptr, *ptrsave, *suc, *parsuc;
ptrsave = location;
ptr = location->rightchild;
while (ptr->leftchild != NULL)
{
ptrsave = ptr;
ptr = ptr->leftchild;
}
suc = ptr;
parsuc = ptrsave;
if (suc->leftchild == NULL && suc->rightchild == NULL)
{
if (parsuc == NULL)
{
root = NULL;
}
else
{
if (suc == parsuc->leftchild)
parsuc->leftchild = NULL;
else
parsuc->rightchild = NULL;
}
}
else
{
tree *child2;
if (suc->leftchild != NULL)
child2 = suc->leftchild;
else
child2 = suc->rightchild;
if (parsuc == NULL)
{
root = child2;
}
else
{
if (suc == parsuc->leftchild)
parsuc->leftchild = child2;
else
parsuc->rightchild = child2;
}
}
if (parsuc == NULL)
{
root = suc;
}
else
{
if (suc == parsuc->leftchild)
parsuc->leftchild = suc;
else
parsuc->rightchild = suc;
}
suc->leftchild = suc->leftchild;
suc->rightchild = suc->rightchild;
}
free(location);
}
tree* searchElement(tree* temp, int key)
{
if ((temp == NULL) || (temp->data == key))
{
return temp;
}
if (temp->data < key)
{
return searchElement(temp->rightchild, key);
}
return searchElement(temp->leftchild, key);
}
void preorder(tree *t)
{
if (root == NULL)
{
cout << "Tree is empty" << endl;
return;
}
if (t != NULL)
{
cout << t->data << " ";
preorder(t->leftchild);
preorder(t->rightchild);
}
}
void inorder(tree *node)
{
if (root == NULL)
{
cout << "Tree is empty" << endl;
return;
}
if (node != NULL)
{
inorder(node->leftchild);
cout << node->data << " ";
inorder(node->rightchild);
}
}
void postorder(tree * node)
{
if (root == NULL)
{
cout << "Tree is empty" << endl;
return;
}
if (node != NULL)
{
postorder(node->leftchild);
postorder(node->rightchild);
cout << node->data << " ";
}
}
int countNodes(tree *temp)
{
if (temp == NULL)
return 0;
if (temp->leftchild != NULL)
{
n = n + 1;
n = countNodes(temp->leftchild);
}
if (temp->rightchild != NULL)
{
n = n + 1;
n = countNodes(temp->rightchild);
}
return n;
}
int findHeight(tree * temp)
{
if (temp == NULL)
{
return 0;
}
else
{
int lb = findHeight(temp->leftchild);
int rb = findHeight(temp->rightchild);
return max(lb, rb) + 1;
}
}
};
int main(int argc, char *argv[])
{
fstream fin;
tree* temp;
BST bstobj;
temp = new tree;
if (argc != 2)
{
cout << "ERROR: no BST CMD file " << endl;
return 2;
}
fin.open(argv[1], ios::in);
if (!fin.is_open())
{
cout << "ERROR: file " << argv[1] << " could not be opened" << endl;
return 3;
}
vector<string> row;
string line;
cout << "\n";
while (getline(fin, line))
{
string cmd = "", value = "";
int flag1 = 0, flag2 = 0;
for (int i = 0; i < line.length(); i++)
{
if (line[i] == ':')
{
flag1 += 1;
continue;
}
if (flag1 == 0)
{
cmd += line[i];
}
else
{
value += line[i];
}
}
int convertedCmd = 0;
stringstream t1(cmd);
t1>>convertedCmd;
int convertedValue=0;
stringstream t2(value);
t2>>convertedValue;
switch (convertedCmd)
{
case -1:
cout << "\n\nDelete " << convertedValue << " :\n";
bstobj.deleteElement(convertedValue);
break;
case 0:
exit(0);
break;
case 1:
cout << "\nInsert " << convertedValue << "in tree : \n";
temp = new tree;
temp->data = convertedValue;
bstobj.insert(root, temp);
break;
case 2:
cout << endl;
cout << "\nSearch " << convertedValue<<" : \n";
temp = bstobj.searchElement(root, convertedValue);
if (temp == NULL)
{
cout << convertedValue << " NOT FOUND";
}
else
{
cout << convertedValue << " Found";
}
break;
case 3:
cout << "\nPreorder\n";
bstobj.preorder(root);
break;
case 4:
cout << "\nInorder\n";
bstobj.inorder(root);
break;
case 5:
cout << "\nPostOrder\n";
bstobj.postorder(root);
break;
case 7:
cout << "\nNodes is : " << bstobj.countNodes(root);
n=1;
break;
case 8:
cout << "\nHeight is : " << bstobj.findHeight(root);
break;
default:
break;
}
}
fin.close();
return 0;
}