C Program for Binary Search Tree with Preorder, Inorder and Postorder traversals

#include<stdio.h>

#include<string.h>

#define size 20

void streverse(char*);

int push(int x);

int pop();

int evalprefix();

int eval(int,int,char);

struct stack

{

int b[size];

int top;

}s;

int main()

{

s.top=-1;

int y;

char ch;

y=evalprefix();

printf("Evalution of prefix expression is %d",y);

return 0;

}

int evalprefix()

{

char a[size];

char *x;

printf("Enter prefix expression:\t");

     scanf("%s",a);

    streverse(a);

int i=0,op1,op2,r,y;

char ch;

while((ch=a[i])!='\0')

{

if((ch>='0')&&(ch<='9'))

 push(ch-'0');

else{

op1=pop();

op2=pop();

r=eval(op1,op2,ch);

push(r);

}

i++;

}

y=pop();

return y;

}

int eval(int a,int b,char c)

{

     switch(c)

{

case '+':return(a+b);

case '-':return(a-b);

case '*':return(a*b);

case '/':return(a/b);

}

}

int push(int x)

{

s.top++;

s.b[s.top]=x;

return(s.b[s.top]);

}

int pop()

{

return(s.b[s.top--]); 

}

void streverse(char* str) 

{ 

    int len = strlen(str);

    char a[len]; 

    int i;

    for ( i = 0; i < len; i++) { 

        a[i] = str[len - 1 - i]; 

    }; 

    for ( i = 0; i < len; i++) { 

        str[i] = a[i]; 

    }

}

#include<stdio.h>

#include<stdlib.h>

typedef struct tree

{

int info;

struct tree* left;

struct tree* right;

}node;

node* create (node*); 

void insert (node*, node*);

node* search (node*);

void display (node*);

node* del (node*, int);

node* preorder (node*);

node* inorder (node*);

node* postorder (node*);

node* create (node* root)

{

int no,ele,i;

node* n=NULL;

printf("\nNumber of entries:\t");

scanf("%d", &no);

for(i=0; i<no; i++)

{

printf("\n-------INSERT-------");

printf("\nEnter data:\t");

scanf("%d", &ele);

n=(node*)malloc(sizeof(node));

n->info = ele;

n->left=NULL; 

n->right=NULL;

if(root==NULL)

{

printf("\nIt's the first element of the tree.");

root=n;

}

else

{

insert(n, root);

}

}

printf("\n\nCREATED"); 

return root;

}

void insert (node* nw, node* root)

{

node *p;

node *q;

p=root; q=root;

while(q!=NULL)

{

p=q;

if(nw->info>q->info)

q=q->right;

else

q=q->left;

}

if(p->info > nw->info)

{

p->left = nw;

}

else

{

p->right = nw;

}

printf("\nInserted");

}

void display (node* root)

{

node *disp;

printf("\nDisplay Function.");

if(root!=NULL)

{

printf("\nLEFT:\t");

for(disp=root->left; disp!=NULL ; disp=disp->left)

printf(" %d ", disp->info);

printf("\nROOT:\t %d",root->info);

printf("\nRIGHT:\t");

for(disp=root->right; disp!=NULL ; disp=disp->right)

printf(" %d ", disp->info);

}

else

return;

printf("\n\n");

}

node* search(node* root)

{

node *q;

int ele;

q=root;

printf("Enter value to be searched:\t");

scanf("%d", &ele);

while((q!=NULL)&&(q->info!=ele))

{

if(q->info>ele)

q=q->left;

else

q=q->right;

}

printf("\nSearch Complete");

if(q==NULL) 

{

printf("\n%d doesn't exist in the tree.", ele);

}

else 

{

printf("\n%d found",q->info);

}

return q;

}

node* del(node* root, int ele)

{

node *temp, *r;

    if (root == NULL) return root;

    if (ele < root->info)

        root->left = del(root->left, ele);

    else if (ele > root->info)

        root->right = del(root->right, ele);

    else

    {

        if (root->left == NULL)

        {

            temp = root->right;

            free(root);

            return temp;

        }

        else if (root->right == NULL)

        {

            temp = root->left;

            free(root);

            return temp;

        }

  r=root->right;

  while(r->left!=NULL)

  r=r->left;

        temp = r;

        root->info = temp->info;

        root->right = del(root->right, temp->info);

    }

    return root;

}

node* preorder (node* root)

{

node* q;

q=root;

if(q!=NULL)

{

printf("  |  %d  |  ", q->info);

q->left = preorder(q->left);

q->right = preorder(q->right);

}

return q;

}

node* inorder (node* q)

{

if(q!=NULL)

{

q->left=inorder(q->left);

printf("  |  %d  |  ", q->info);

q->right=inorder(q->right);

}

return q;

}  

node* postorder (node* q)

{

if(q!=NULL)

{

q->left=postorder(q->left);

q->right=postorder(q->right);

printf("  |  %d  |  ", q->info);

}

return q;

}  

void main()

{

node *root=NULL, *key;

int choice, val, check=0;

while(1)

{

printf("\n\n\n1. Create\n2. Display\n3. Search\n4. Delete a node.\n5. Preorder Traversal\n6. Inorder Traversal\n7. Postorder Traversal.\n8. Exit program.\n\nEnter your choice:\t");

scanf("%d", &choice);

switch(choice)

{

case 1: root=create(root); check=1; break;

case 2: if(check) display(root); else printf("\nNo data stored yet, first create the tree."); break;

case 3: key = search(root); break;

case 4: printf("Enter value to be deleted:\t"); scanf("%d", &val); root = del(root, val); printf("\nDeleted"); break;

case 5: preorder(root); break;

case 6: root=inorder(root); break;

case 7: root=postorder(root); break;

        case 8: if(root==NULL) printf("\nExiting with empty tree\n\n"); else { root->right=NULL; root->left=NULL; free(root); printf("\nFREED ROOT\n\n");} exit(0);

default: printf("\n\nHey!! Choose an option from the choices mentioned!!\n And stop testing my program!!");

}

}

}