Implement Binary Search Tree (BST)using linked list. Make sure you provide following methods within class;
1. Constructor : initialize pointer(s)
2. Destructor : delete all nodes
3. Insert_Node : insert new node
4. Remove : remove a node
5. Find : find/search a node
6. Get_minimum : return minimum number in the BST
7. Get_maximum : return maximum number in the BST
8. Count_elements: return total number of elements in the BST
#include<iostream>
using namespace std;
struct node
{
int data;
node *left;
node *right;
}*root;
class BS_TREE
{
public:
int count;
public:
BS_TREE ();
~BS_TREE();
void Insert_Node (int);
node *Delete_Node (node *, int);
void Find_Node (int) ;
int Maximum_Node (void);
int Minimum_Node (void);
int Count_NODE (void);
bool Isempty (void);
void Display_Inorder (node *);
void Display_Preorder (node *);
void Display_Postorder(node *);
node *Triversal_For_Min_Node(node *);
};
BS_TREE::BS_TREE()
{
root = NULL;
count = 0 ;
}
BS_TREE::~BS_TREE()
{
if (root != NULL)
{
delete(root->left) ;
delete(root->right);
delete root ;
}
}
void BS_TREE::Insert_Node(int val)
{
node *newnode;
newnode = new node ;
newnode->data = val ;
newnode->left = NULL ;
newnode->right = NULL;
if (Isempty())
{
root = newnode;
cout << "\nRoot = " << root->data << endl;
count++;
}
else
{
node *temp = root;
while (true)
{
if (val < temp->data)
{
if (temp->left == NULL)
{
temp->left = newnode;
cout << "\nLeft Root = " << temp->left->data << endl;
count++;
return;
}
else
{
temp = temp->left;
}
}
else
{
if (temp->right == NULL)
{
temp->right = newnode;
cout << "\nRight Root = " << temp->right->data << endl;
count++;
return;
}
else
{
temp = temp->right;
}
}
}
}
}
node *BS_TREE::Triversal_For_Min_Node(node *root)
{
node * temp = root;
while (temp->left != NULL)
{
temp = temp->left;
}
return temp;
}
node *BS_TREE::Delete_Node(node * root, int num)
{
if (root == NULL)
{
return root;
}
if (num < root->data)
{
root->left = Delete_Node(root->left, num);
}
else if (num > root->data)
{
root->right = Delete_Node(root->right, num);
}
else
{
if (root->left == NULL)
{
node *temp = root->right;
delete(root) ;
count--;
return temp;
}
else if (root->right == NULL)
{
node *temp = root->left;
delete(root) ;
count--;
return temp;
}
node* temp = Triversal_For_Min_Node(root->right);
root->data = temp->data;
root->right= Delete_Node(root->right, temp->data);
}
return root;
}
void BS_TREE::Find_Node(int num)
{
if (!root)
{
cout << "BST is Empty " << endl;
}
else if (num == root->data)
{
cout << "Values is Found = " << root->data << endl;
}
else
{
node *temp = root;
while (true)
{
if (num < temp->data)
{
if (temp->left->data == num)
{
cout << "Values is Found = " << temp->left->data << endl;
return;
}
else
{
temp = temp->left;
}
}
else
{
if (temp->right->data == num)
{
cout << "Values is Found = " << temp->right->data << endl;
return;
}
else
{
temp = temp->right;
}
}
}
cout << "Values is Not Found " << endl;
return;
}
}
int BS_TREE::Maximum_Node(void)
{
struct node *temp;
temp = root;
while (temp->right != NULL)
{
temp = temp->right;
}
return(temp->data);
}
int BS_TREE::Minimum_Node(void)
{
struct node *temp;
temp = root;
while (temp->left != NULL)
{
temp = temp->left;
}
return(temp->data);
}
int BS_TREE::Count_NODE(void)
{
return (count);
}
bool BS_TREE::Isempty(void)
{
return (root == NULL);
}
void BS_TREE::Display_Inorder(node *root)
{
if (root == NULL)
{
return;
}
Display_Inorder(root->left) ;
cout << root->data << " " ;
Display_Inorder(root->right);
}
void BS_TREE::Display_Preorder(node *root)
{
if (root == NULL)
{
return;
}
cout << root->data << " " ;
Display_Preorder(root->left) ;
Display_Preorder(root->right);
}
void BS_TREE::Display_Postorder(node *root)
{
if (root == NULL)
{
return;
}
Display_Postorder(root->left) ;
Display_Postorder(root->right);
cout << root->data << " " ;
}
int main()
{
BS_TREE bst;
int num, choice;
while (true)
{
cout << " \t\t\t\t\t\tOPERATIONS ON BIARY SEARCH TREE " << endl;
cout << "****************************************";
cout << "****************************************";
cout << "****************************************" << endl;
cout << "->1...INSERT NODE " << endl;
cout << "->2...DELETE NODE " << endl;
cout << "->3...FIND NODE " << endl;
cout << "->4...TOTAL NUMBER OF NODE IN BST " << endl;
cout << "->5...FIND MAXIMUM VALUE" << endl;
cout << "->6...FIND MINIMUM VALUE" << endl;
cout << "->7...PRE-ORDER TRAVERSAL" << endl;
cout << "->8...IN-ORDER TRAVERSAL" << endl;
cout << "->9...POST-ORDER TRAVERSAL" << endl;
cout << "->10...CHECK BST IS EMPTY OR NOT" << endl;
cout << "->11...CLEAR SCREEN" << endl;
cout << "->12...QUIT" << endl;
cout << "\nENTER YOUR CHOICE : ";
cin >> choice;
switch (choice)
{
case 1:
system("cls");
bst.Display_Preorder(root);
cout << "\nENTER NUMBER TO INSERTED IN BS-TREE : ";
cin >> num;
bst.Insert_Node(num);
break;
case 2:
system("cls");
bst.Display_Preorder(root);
cout << "\nENTER NUMBER TO DELETED IN BS-TREE : ";
cin >> num;
root = bst.Delete_Node(root, num);
break;
case 3:
system("cls");
bst.Display_Preorder(root);
cout << "\nENTER NUMBER TO FIND IN BS-TREE : ";
cin >> num;
bst.Find_Node(num);
break;
case 4:
system("cls");
cout << endl;
cout << "TOTAL NUMBER OF NODES IN THE BST = " << bst.Count_NODE();;
break;
case 5:
system("cls");
bst.Display_Preorder(root);
cout << "MAXIMUM VALUE IS = " << bst.Maximum_Node();
break;
case 6:
system("cls");
bst.Display_Preorder(root);
cout << "MINIMUM VALUE IS = " << bst.Minimum_Node();
break;
case 7:
system("cls");
cout << endl;
cout << "\nPRE-ORDER TRAVERSAL ACCORDING TO -> Root -> Left -> Right" << endl;
cout << endl;
bst.Display_Preorder(root);
break;
case 8:
system("cls");
cout << endl;
cout << "\nIN-ORDER TRAVERSAL ACCORDING TO -> Left -> Root -> Right" << endl;
cout << endl;
bst.Display_Inorder(root);
break;
case 9:
system("cls");
cout << endl;
cout << "\nPOST-ORDER TRAVERSAL ACCORDING TO -> Left -> Right -> Root" << endl;
cout << endl;
bst.Display_Postorder(root);
break;
case 10:
system("cls");
if (bst.Isempty())
{
cout << "BST IS EMPTY...." << endl;
}
else
{
cout << "BST NOT EMPTY.." << endl;
}
break;
case 11:
system("cls");
break;
case 12:
exit(1);
default:
cout << "\nWRONG CHOICE" << endl;
}
}
return 0;
}
.png)
