Expression Trees

 Expression Trees

AU: Dec.-18, Marks 15

Definition: An expression tree is a binary tree in which the operands are attached as leaf nodes and operators become the internal nodes.

For example -

From expression tree :

Inorder traversal: A+B*C(Left-Data-Right)

Preorder traversal: +A*BC(Data-Left-Right)

Postorder traversal: ABC*+ (Left-Right-Data)

If we traverse the above tree in inorder, preorder or postorder then we get infix, prefix or postfix expressions respectively.

Key Point: Inorder traversal of expression tree fives infix expression. The preorder traversal of expression tree gives prefix expression and post order traversal of expression tree gives postfix expression.

 

1. Creation of an Expression Tree

Consider a postfix expression, stored in array exp

Now we will read each symbol from left to right one character at a time. If we read an operand then we will make a node of it and push it onto the stack. If we read operator then pop two nodes from stack, the first popped node will be attached as right child to operator node and second popped node will be attached as a left child to operator node. For the above given expression let us build a tree.

Now as we read '+' pop two operands and attach them as follows -

Now push the node '+' onto the stack.

Next we read c and d. Hence stack will be -

Now we read '-'. So pop two nodes

Next we read '*'. Hence pop two nodes from the stack and attach them to * node.

As now we read '\0', pop the content of stack. The node which we will get is the root node of an expression tree.

Let us implement it

 

Ex. 5.5.1: Program for creating an expression tree and printing it using an inorder traversal.

Sol. :

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

#include <ctype.h>

 

#define size 20

 

typedef struct node

{

char data;

struct node *left;

struct node *right;

}btree;

/* stack stores the operand nodes of the tree*/

btree *stack[size];

int top;

 

void main()

{

btree *root;

char exp[80]; /* exp stores postfix expression */

btree *create(char exp[80]);

void display(btree *root);

clrscr();

printf("Enter the postfix expression\n");

scanf("%s",exp);

top = -1; /* Initialise the stack */

root create(exp);

printf("\n The Tree is created...\n");

printf("\n The inorder traversal of it is \n");

display(root);

getch();

}

btree* create(char exp[])

{

btree *temp;

int pos;

char ch;

void push(btree *);

btree *pop();

pos = 0;

ch = exp[pos];

while (ch!= '\0')

{

/* Create a new node */

temp -> left = temp -> right = NULL;

temp -> data = ch;

if (isalpha(ch)) /* is it a operand */

push (temp); /* push operand */

else if (ch=='+' || ch==''||ch=="*' || ch=='/')

{

/* it is operator, so pop two nodes from stack

set first node as right child and

set second as left child and push the

operator node on to the stack

*/

temp->right = pop();

temp ->left = pop();

push(temp);

}

else

printf("Invalid character in expression\n");

pos ++;

ch exp[pos]; /* Read next character */

}

temp = pop();

return(temp);

}

void push(btree *Node)

{

if (top+1 >= size)

printf("Error: Stack is Full\n");

top++;

stack[top] = Node;

}

btree* pop()

{

btree *Node;

if (top = = -1)

printf("Error: Stack is Empty\n");

Node = stack[top];

top--;

return(Node);

}

void display(btree *root)

{

btree *temp;

temp = root;

if (temp!= NULL)

{

display(temp->left);

printf("%c", temp->data);

display(temp->right);

}

}

Output

Enter the postfix expression

ab+cd-*

The Tree is created...

The inorder traversal of it is

a+b * c - d

 

Ex. 5.5.2: Show the binary tree with arithmetic expression A/B * C * D + E. Give the algorithm for inorder, preorder, postorder traversals and show the result of these traversals.

Sol. :

Algorithm for inorder, preorder and postorder Traversal - Refer section 5.4.

Inorder Traversal A/B*C*D+E

Preorder Traversal + * * / ABCDE

Postorder Traversal AB/C*D*E+

Review Question

1. What are expression trees. Write the procedure for constructing an expression tree.

AU: Dec.-18, Marks 15