C Program for Construction of Expression Tree using Postfix

/* CONSTRUCTION OF EXPRESSION TREE USING POSTFIX */

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<malloc.h>

struct node
{
 struct node *right,*left,*prev;
 char data;
}*cur,*par,*root=NULL;

void preorder(struct node *);
void postorder(struct node *);
void inorder(struct node *);

void main()
{
  char a[100];
  int len,i;
  struct node *new_node;
  clrscr();

  printf("Enter Postfix Expression\n");
  gets(a);
  len=strlen(a);
  for(i=len-1 ; i>=0 ; i--)
  {
   new_node=(struct node *)malloc(sizeof(struct node));
   new_node->data=a[i];
   new_node->left=new_node->right=new_node->prev=NULL;
   if(root==NULL)
   {
     root=new_node;
     cur=par=root;
   }
   else
   {
    if(a[i]=='+' ||a[i]=='-' ||a[i]=='*'||a[i]=='/')
    {
     if(par->right==NULL)
     {
      cur=new_node;
      par->right=cur;
      cur->prev=par;
      par=cur;
     }
     else if(par->left==NULL)
     {
      cur=new_node;
      par->left=cur;
      cur->prev=par;
      par=cur;
     }
    else
    {
     while(par->left!=NULL)
     {
      par=par->prev;
     }
     cur=new_node;
     par->left=cur;
     cur->prev=par;
     par=cur;
    }
   }
   else
   {
    if(par->right==NULL)
    {
     cur=new_node;
     par->right=cur;
     cur->prev=par;
    }
    else if(par->left==NULL)
    {
     cur=new_node;
     par->left=cur;
     cur->prev=par;
    }
    else
    {
     while(par->left!=NULL)
     {
      par=par->prev;
     }
     cur=new_node;
     par->left=cur;
     cur->prev=par;
    }
   }
  }
 }
 printf("\nInorder Traversal: \n");
 inorder(root);
 printf("\n\nPreorder Traversal: \n");
 preorder(root);
 printf("\n\nPostorder Traversal: \n");
 postorder(root);
 getch();
}

//-------INORDER-------
void inorder(struct node *root)
{
 if(root!=NULL)
 {
  inorder(root->left);
  printf("%c\t",root->data);
  inorder(root->right);
 }
}

//-------PREORDER-------
void preorder(struct node *root)
{
 if(root!=NULL)
 {
  printf("%c\t",root->data);
  preorder(root->left);
  preorder(root->right);
 }
}

//-------POSTORDER-------
void postorder(struct node *root)
{
 if(root!=NULL)
 {
  postorder(root->left);
  postorder(root->right);
  printf("%c\t",root->data);
 }
}

/* OUTPUT

Enter Postfix Expression
AB+CD-*

Inorder Traversal:
A       +       B       *       C       -       D

Preorder Traversal:
*       +       A       B       -       C       D

Postorder Traversal:
A       B       +       C       D       -       *
*/