Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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