Expression Trees
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.
Creation of an Expression
Treesate
Consider
a postfix expression, stored in array expose sopol 5 Pms
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.
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. 4.7.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 = (btree
*)malloc(sizeof(btree));
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. 4.7.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 4.6.
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.