[Solved] Implementation of expression tree and traversals with C

Tree and Traversals: Get the input postfix expression and construct an expression tree.

Traverse the constructed Expression tree by Inorder, Preorder and Postorder methods.

 [Note:- Each character corresponds to a number or an operator. Use only single digit numbers.]

Create a structure
struct tree
{
    char data;
    struct tree *left;
    struct tree *right;
};

Function specifications:
struct tree * newnode(char b)
void push(struct tree * temp)
struct tree * pop()
void inorder(struct tree * t)
void preorder(struct tree * t)
void postorder(struct tree * t)
 

Input Format:

Input a string in the form of postfix expression.

Output Format:

Print the output got while traversing the expression tree by Inorder, Preorder and Postorder traversal methods.
 

Sample Input and Output:

Enter the postfix expression:

23*45/56+-*

Inorder Traversal

2 * 3 * 4 / 5 – 5 + 6

Preorder Traversal

* * 2 3 – / 4 5 + 5 6

Postorder Traversal

2 3 * 4 5 / 5 6 + – *

Function Definitions:

void push (struct tree *temp)

void inorder (struct tree *t)

void preorder (struct tree *t)

void postorder (struct tree *t)

Solution

#include<stdio.h>
#include<stdlib.h>


struct tree
{
char data;
struct tree *left;
struct tree *right;
};

struct tree *stack[30];
int top=-1;

struct tree * newnode(char b);
void push(struct tree * temp);
struct tree * pop();
void inorder(struct tree * t);
void preorder(struct tree * t);
void postorder(struct tree * t);

int main()
{
char a[30];
struct tree * temp;
int i;
printf("Enter the postfix expression:\n");
scanf("%s",a);
for(i=0;a[i]!='\0';i++)
{
if(a[i]=='*' || a[i]=='/' || a[i]=='+' || a[i]=='-')
{
temp=newnode(a[i]);
temp->right=pop();
temp->left=pop();
push(temp);
}
else
{
temp=newnode(a[i]);
push(temp);
}
}
printf("Inorder Traversal");
inorder(temp);
  printf("\n");
printf("Preorder Traversal");
preorder(temp);
    printf("\n");
printf("Postorder Traversal");
postorder(temp);
return 0;
}


struct tree * newnode(char b){
    struct tree* nn = (struct tree*)malloc(sizeof(struct tree));
    nn->data = b;
    nn->left = nn->right = NULL;
    return nn;
}
void push(struct tree * temp){
    stack[++top] = temp;
}

struct tree * pop(){
    return stack[top--];
}

void inorder(struct tree * t){
    if(t){
        inorder(t->left);
        printf(" %c",t->data);
        inorder(t->right);
    }
}


void preorder(struct tree * t){
    if(t){
        printf(" %c",t->data);
        preorder(t->left);
        preorder(t->right);
    }
}

void postorder(struct tree * t){
    if(t){
        
        postorder(t->left);
        postorder(t->right);
        printf(" %c",t->data);
    }
}

Happy Learning – If you require any further information, feel free to contact me.