how to draw binary tree for the expression
Expression Tree
Expression tree is a binary tree in which each internal node corresponds to operator and each leaf node corresponds to operand so for example expression tree for 3 + ((5+9)*2) would be:
Inorder traversal of expression tree produces infix version of given postfix expression (same with preorder traversal it gives prefix expression)
Evaluating the expression represented by expression tree:
Let t be the expression tree If t is not null then If t.value is operand then Return t.value A = solve(t.left) B = solve(t.right) // calculate applies operator 't.value' // on A and B, and returns value Return calculate(A, B, t.value)
Construction of Expression Tree:
Now For constructing expression tree we use a stack. We loop through input expression and do following for every character.
1) If character is operand push that into stack
2) If character is operator pop two values from stack make them its child and push current node again.
At the end only element of stack will be root of expression tree.
Below is the implementation :
C/C++
#include<bits/stdc++.h>
using namespace std;
struct et
{
char value;
et* left, *right;
};
bool isOperator( char c)
{
if (c == '+' || c == '-' ||
c == '*' || c == '/' ||
c == '^' )
return true ;
return false ;
}
void inorder(et *t)
{
if (t)
{
inorder(t->left);
printf ( "%c " , t->value);
inorder(t->right);
}
}
et* newNode( int v)
{
et *temp = new et;
temp->left = temp->right = NULL;
temp->value = v;
return temp;
};
et* constructTree( char postfix[])
{
stack<et *> st;
et *t, *t1, *t2;
for ( int i=0; i< strlen (postfix); i++)
{
if (!isOperator(postfix[i]))
{
t = newNode(postfix[i]);
st.push(t);
}
else
{
t = newNode(postfix[i]);
t1 = st.top();
st.pop();
t2 = st.top();
st.pop();
t->right = t1;
t->left = t2;
st.push(t);
}
}
t = st.top();
st.pop();
return t;
}
int main()
{
char postfix[] = "ab+ef*g*-" ;
et* r = constructTree(postfix);
printf ( "infix expression is " );
inorder(r);
return 0;
}
Java
import java.util.Stack;
class Node {
char value;
Node left, right;
Node( char item) {
value = item;
left = right = null ;
}
}
class ExpressionTree {
boolean isOperator( char c) {
if (c == '+' || c == '-'
|| c == '*' || c == '/'
|| c == '^' ) {
return true ;
}
return false ;
}
void inorder(Node t) {
if (t != null ) {
inorder(t.left);
System.out.print(t.value + " " );
inorder(t.right);
}
}
Node constructTree( char postfix[]) {
Stack<Node> st = new Stack();
Node t, t1, t2;
for ( int i = 0 ; i < postfix.length; i++) {
if (!isOperator(postfix[i])) {
t = new Node(postfix[i]);
st.push(t);
} else
{
t = new Node(postfix[i]);
t1 = st.pop();
t2 = st.pop();
t.right = t1;
t.left = t2;
st.push(t);
}
}
t = st.peek();
st.pop();
return t;
}
public static void main(String args[]) {
ExpressionTree et = new ExpressionTree();
String postfix = "ab+ef*g*-" ;
char [] charArray = postfix.toCharArray();
Node root = et.constructTree(charArray);
System.out.println( "infix expression is" );
et.inorder(root);
}
}
Python
class Et:
def __init__( self , value):
self .value = value
self .left = None
self .right = None
def isOperator(c):
if (c = = '+' or c = = '-' or c = = '*'
or c = = '/' or c = = '^' ):
return True
else :
return False
def inorder(t):
if t is not None :
inorder(t.left)
print t.value,
inorder(t.right)
def constructTree(postfix):
stack = []
for char in postfix :
if not isOperator(char):
t = Et(char)
stack.append(t)
else :
t = Et(char)
t1 = stack.pop()
t2 = stack.pop()
t.right = t1
t.left = t2
stack.append(t)
t = stack.pop()
return t
postfix = "ab+ef*g*-"
r = constructTree(postfix)
print "Infix expression is"
inorder(r)
C#
using System;
using System.Collections;
public class Node
{
public char value;
public Node left, right;
public Node( char item)
{
value = item;
left = right = null ;
}
}
class ExpressionTree
{
Boolean isOperator( char c)
{
if (c == '+' || c == '-' || c == '*'
|| c == '/' || c == '^' )
{
return true ;
}
return false ;
}
void inorder(Node t)
{
if (t != null )
{
inorder(t.left);
Console.Write(t.value + " " );
inorder(t.right);
}
}
Node constructTree( char []postfix)
{
Stack st = new Stack();
Node t, t1, t2;
for ( int i = 0; i < postfix.Length; i++)
{
if (!isOperator(postfix[i]))
{
t = new Node(postfix[i]);
st.Push(t);
}
else
{
t = new Node(postfix[i]);
t1 = (Node)st.Pop();
t2 = (Node)st.Pop();
t.right = t1;
t.left = t2;
st.Push(t);
}
}
t = (Node)st.Peek();
st.Pop();
return t;
}
public static void Main(String []args)
{
ExpressionTree et = new ExpressionTree();
String postfix = "ab+ef*g*-" ;
char [] charArray = postfix.ToCharArray();
Node root = et.constructTree(charArray);
Console.WriteLine( "infix expression is" );
et.inorder(root);
}
}
Output:
infix expression is a + b - e * f * g
0 1
You Might Also Like
Subscribe to Our Newsletter
Source: https://tutorialspoint.dev/data-structure/binary-tree-data-structure/expression-tree
0 Response to "how to draw binary tree for the expression"
Post a Comment