October 22, 2015

Binary tree for the given postfix expression C program

binary tree in c, binary search tree in c, binary search tree program in c, data structures binary search tree, binary search tree algorithms, Binary tree postfix



Program to create a binary tree for the given postfix expression.

//Nilkanth Shirodkar

#include<stdio.h>
#include<stdlib.h>
struct Node
{
int info;
struct Node *left;
struct Node *right;
};
typedef struct stack
{
    long int data[200];
    int top;
}stack;

void init(stack *);
int pop(stack *);
void push(struct Node *,stack *); 
struct Node *insert_node(struct Node *,int);
void inorder(struct Node *);
void postorder(struct Node *);
void preorder(struct Node *);

int main(void)
{
  struct Node *root= NULL;
int choice, item,item2,count=0;

stack s;
    char x;
    //int op1,op2,val;
    init(&s);
    printf("Enter a postfix expression:\n");
//printf("root");
    while((x=getchar())!='\n')
    {
        if(isdigit(x)){
root=(struct Node*)malloc(sizeof(struct Node));
    root->info = x-48;
    root->left = NULL;
    root->right = NULL;
                push(root,&s);     //x-48 for removing the effect of ASCII
        }else
        {
root=(struct Node*)malloc(sizeof(struct Node));
    root->info = x;
    root->left = NULL;
    root->right = NULL;
    //return(root);
//root= insert_node(root,x);
           item=pop(&s);
item2=pop(&s);
root= insert_node(root,item2);
root= insert_node(root,item);
push(root,&s);
        }
    }
//pop(&s);
inorder(root);

}



void init(stack *s)
{
    s->top=-1;
}
void push(struct Node *root,stack *s)
{
    s->top=s->top+1;
    s->data[s->top]=root;
}

int pop(stack *s)
{
    long int x;
    x=s->data[s->top];
    s->top=s->top-1;
    return(x);
}

struct Node *insert_node(struct Node *root, int x)
{
  if(root->left == NULL)
     root->left = x;
  else
   {
     if(root->right == NULL)
root->right = x;
   }
   return(root);
 }


 void inorder(struct Node *root)
 {
    if(root != NULL)
   {
     inorder(root->left);
if(root->info==43){
        printf("+");
}else if(root->info==45){
        printf("-");
}else if(root->info==42){
       printf("*");
}else if(root->info==47){
         printf("/");
}else if(root->info==37){
          printf("%");
}else{
printf("%d",root->info);
}
     inorder(root->right);
   }
   return;
 }

 void postorder(struct Node *root)
 {
    if(root != NULL)
   {
     postorder(root->left);
     postorder(root->right);
     printf(" %d",root->info);
   }
   return;
 }

 void preorder(struct Node *root)
 {
    if(root != NULL)
   {
     printf(" %d",root->info);
     preorder(root->left);
     preorder(root->right);
   }
   return;
 }
No comments:
Write comments