- 19th Oct 2022
- 12:10 pm
This C++ program that implements a Binary Search Tree (BST) with various operations such as insertion, deletion, searching, and traversals. The program also reads commands from a file to perform these operations on the BST.
The program uses a struct called tree to define the nodes of the BST, where each node contains an integer data value and pointers to the left and right children. The BST itself is managed by the BST class, which provides methods for inserting nodes, deleting nodes, searching for nodes, and performing different types of tree traversals (preorder, inorder, and postorder).
The main function reads commands from a file specified as a command-line argument and interprets these commands to perform operations on the BST. The commands are represented by integers, and based on the command code, the corresponding operation is executed using the methods provided by the BST class.
C++ Assignment Solution - BST Command
#include
#include
#include
#include
#include
#include
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"< }
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 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;
}
C++ Programming Homework Helper - Programming Solution Analysis
Here's a summary of the available commands and their meanings:
- Command -1: Delete an element from the BST.
- Command 0: Exit the program.
- Command 1: Insert an element into the BST.
- Command 2: Search for an element in the BST.
- Command 3: Perform a preorder traversal of the BST.
- Command 4: Perform an inorder traversal of the BST.
- Command 5: Perform a postorder traversal of the BST.
- Command 7: Count the number of nodes in the BST.
- Command 8: Find the height of the BST.
The main function reads the command file line by line, extracts the command code and value, and then calls the corresponding method of the BST class to perform the operation.
It seems like you've implemented a functional and complete BST program with command-line argument support. To test the program, you need to create a command file with the commands you want to execute on the BST, with each command on a separate line.
Please let me know if you have any specific questions or if there's anything else you would like to know about the program!
