The program contains all the operations that can be performed on the BST.
// Bst tree with full operations | |
#include <iostream> | |
using namespace std; | |
class bst { | |
struct Node { | |
double data; | |
Node *left, *right; | |
}; | |
struct stackd { | |
Node* data; | |
stackd* below; | |
}; | |
stackd* top; | |
Node* root; | |
public: | |
bst() | |
{ | |
top = NULL; | |
root = NULL; | |
} | |
Node* createLeaf(int x) | |
{ | |
Node* n = new Node; | |
n->data = x; | |
n->left = n->right = NULL; | |
} | |
void addLeaf(int x, Node* ptr) | |
{ | |
if (root == NULL) { | |
root = createLeaf(x); | |
} | |
else if (x > ptr->data) { | |
if (ptr->right != NULL) { | |
addLeaf(x, ptr->right); | |
} | |
else { | |
ptr->right = createLeaf(x); | |
} | |
} | |
else if (x < ptr->data) { | |
if (ptr->left != NULL) { | |
addLeaf(x, ptr->left); | |
} | |
else { | |
ptr->left = createLeaf(x); | |
} | |
} | |
else { | |
cout << "The element has been added already !-- Try New one !\n"; | |
} | |
} | |
void addnew(int x) | |
{ | |
addLeaf(x, root); | |
} | |
void displayInorder(Node* ptr) // Left Root Right | |
{ | |
if (root != NULL) { | |
if (ptr->left != NULL) { | |
displayInorder(ptr->left); | |
} | |
cout << ptr->data << " "; | |
if (ptr->right != NULL) { | |
displayInorder(ptr->right); | |
} | |
} | |
else { | |
cout << "The tree is empty ! Add one ?"; | |
} | |
} | |
void displayPreOrder(Node* ptr) // Root Left Right | |
{ | |
if (root == NULL) { | |
cout << "So the tree is Empty"; | |
} | |
else { | |
if (ptr != NULL) { | |
cout << ptr->data << " "; | |
if (ptr->right != NULL) { | |
push(ptr->right); | |
// cout<<"Push Display:\n";stackDisplay(); | |
} | |
if (ptr->left != NULL) { | |
displayPreOrder(ptr->left); | |
} | |
while (top != NULL) { | |
displayPreOrder(pop()); | |
// cout<<"Pop Display:\n";stackDisplay(); | |
} | |
} | |
} | |
} | |
void displayPostOrder(Node *ptr){ // Left Right Root | |
if(root==NULL){ | |
cout<<"There is no Tree Exists !\n"; | |
}else{ | |
if(ptr->left!=NULL){ | |
displayPostOrder(ptr->left); | |
} | |
if(ptr->right!=NULL){ | |
displayPostOrder(ptr->right); | |
} | |
cout<<ptr->data<< " "; | |
} | |
} | |
void push(Node* x) | |
{ | |
stackd* no = new stackd; | |
no->data = x; | |
no->below = NULL; | |
if (top == NULL) { | |
top = no; | |
} | |
else { | |
no->below = top; | |
top = no; | |
} | |
} | |
Node* pop() | |
{ | |
stackd *store = top, *del = top; | |
top = top->below; | |
delete del; | |
return store->data; | |
} | |
void stackDisplay(){ | |
stackd *dis = top; | |
while(dis!=NULL){ | |
cout<<"Stack Item:"<<dis->data->data<<endl; | |
dis = dis->below; | |
} | |
} | |
void DisplayIn_order_main() | |
{ | |
displayInorder(root); | |
} | |
void DisplayPre_order_main() | |
{ | |
displayPreOrder(root); | |
} | |
void DisplayPost_order_main(){ | |
displayPostOrder(root); | |
} | |
}; | |
int main() | |
{ | |
bst t; | |
double arr[11]={10,8,11,6,9,2,7,0,3,1,4}; | |
cout << "Welcome to BST \n"; | |
/* cout << "Initially You have to insert some element to perform the operation on the BST:"; | |
int e; | |
cin >> e; | |
double x; */ | |
for (int i = 0; i < 11; i++) { | |
// cin >> x; | |
t.addnew(arr[i]); | |
} | |
cout << "Displaying the tree in - INORDER TRAVERSAL\n"; | |
t.DisplayIn_order_main(); | |
again: | |
cout << "\nDo operations on BST"; | |
cout << "\n1.Add Leaf\n2.Display In-order\n3.Display Pre_order\n4.Display Post_Order\n5.Delete a Leaf"; | |
int choice; | |
cin >> choice; | |
switch (choice) { | |
case 1: | |
int x; | |
cin >> x; | |
t.addnew(x); | |
break; | |
case 2: | |
t.DisplayIn_order_main(); | |
break; | |
case 3: | |
t.DisplayPre_order_main(); | |
break; | |
case 4: | |
t.DisplayPost_order_main(); | |
break; | |
case 5: | |
cout<<"Enter the element you want to remove from the tree: "; | |
int xi ; | |
cin>>xi; | |
// t.DeleteLeaf(int xi); | |
default: | |
cout << "Wrong Character encountered try Again ! \n"; | |
goto again; | |
} | |
goto again; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment