Expression of Tree Traversal

Expression of Tree Traversal

Defination of expresssion tree:-

Algebraic expressions such as a/b + (c-d) e

The terminal nodes (leaves) of an expression tree are the variables or constants in the expression (a, b, c, d, and e). The non-terminal nodes of an expression tree are the
operators (+, -, , and ). Notice that the parentheses which appear in Equation do not appear in the tree. Nevertheless, the tree representation has captured the intent of the
parentheses since the subtraction is lower in the tree than the multiplication.

                                                                              fig 1.1
                                       
Above tree is Expression of a/b+(c-d)e
In tree there are Three Types of Traversal

1 .Preorder Traversal(Prefix) :  To Traverse non Empty tree in Preoder.
a.Visit a root(Display the root).
b.Traverse left Subtree.
c.Traverse right subtree.
*Remember-DLR(D-DATA,L-LEFT,R-RIGHT)
  Example-
In  fig 1.1  preorder traversal is :-      + /  a  b *  - c d e

2.Inorder Traversal(Infix):
a. Traverse the left subtree.
b. Visit the root(Display the root).
c. Traverse the right subtree.
*Remember-LDR(D-DATA,L-LEFT,R-RIGHT)
Example-
In  fig 1.1  Inorder traversal is :-      a / b + c - d * e

3.Postorder Travrsal(Postfix):
a. Traverse the left subtree.
b. Traverse the right subtree.s
c. Visit the root(Display the root).
*Remember-LRD(D-DATA,L-LEFT,R-RIGHT)
Example-
In  fig 1.1  postorder traversal is :-       a b / c d - e * +


ALGORITHM:
          Define structure for Binary Tree (Information, Left Pointer & Right Pointer).

 Create Expression Tree:
          CreateTree() Root& Node pointer variable of type structure. Stack is an pointer array of type structure. String is character array which contains postfix expression. Top & I are variables of type integer.
Step 1: Top = -1 , I = 0;
 Step 2: Do Steps 3,4,5,6 While String[I] != NULL
Step 3: Create Node of type of structure
Step 4: Node->Data=String[I];
Step 5: If isalnum(String[I]) Then Stack[Top++] = Node; Else Node->Right = Stack [--Top ]; Node->Left = Stack[ --Top ]; Stack[ Top++ ] = Node;
Step 6: Increment I;
Step 7: Root = Stack[0];
Step 8: Return Root

Inorder Traversal Recursive : Tree is pointer of type structure. InorderR(Tree)
Step 1: If Tree != NULL 25
Step 2: InorderR( Tree->Left )
Step 3: Print Tree->Data
Step 4: InorderR( Tree->Right )

Postorder Traversal Recursive: Tree is pointer of type structure. PostorderR(Tree)
Step 1: If Tree != NULL
Step 2: PostorderR( Tree->Left )
Step 3: PostorderR( Tree->Right )
Step 4: Print Tree->Data

Preorder Traversal Recursive: Tree is pointer of type structure. PreorderR(Tree)
Step 1: If Tree != NULL
Step 2: Print Tree->Data
Step 3: PreorderR( Tree->Left )
Step 4: PreorderR( Tree->Right )

Program:-

#include<iostream>
#include<stdlib.h>
using namespace std;
#define MAX 15
int IsOperand(char ch)
{
if(ch>='A' && ch<='Z'||ch>='a' && ch<='z')
return 1;
else
return 0;
}
int IsOperator(char ch)
{
if(ch=='*' || ch=='/' || ch=='+' || ch=='-' || ch=='%'|| ch=='^'|| ch=='$')
return 1;
else
return 0;
}
class Expresiontree
{

struct exp
{
char data;
struct exp *lchild;
struct exp *rchild;
};
struct exp *root;
public:
Expresiontree();
void create(char *);

void inorder_r();
void inorder_r(exp*);

void inorder_nr();
void inorder_nr(exp *);

void preorder_r();
void preorder_r(exp *);

void preorder_nr();
void preorder_nr(exp *);

void postorder_r();
void postorder_r(exp *);

void postorder_nr();
void postorder_nr(exp *);

};
Expresiontree::Expresiontree()
{
root=NULL;
}
void Expresiontree::create(char *postfix)
{
exp *temp;
exp *stack[MAX];
char ch;
int top=-1;
int l;
for(l=0;postfix[l]!='\0';l++)
{
ch=postfix[l];
temp=new exp;
temp->data=ch;
temp->rchild=NULL;
temp->lchild=NULL;
if (IsOperand(ch))
stack[++top] = temp;
else

{
temp->rchild = stack [top-- ];
temp->lchild = stack[ top-- ];
stack[ ++top ] = temp;
}

}
root=stack[top--];

}


void Expresiontree::inorder_r()
{
inorder_r(root);
}
void Expresiontree::inorder_r(exp *r)
{
if(r)
{
inorder_r(r->lchild);
cout<<r->data<<"  ";
inorder_r(r->rchild);
}
}

void Expresiontree::inorder_nr()
{
inorder_nr(root);
}
void Expresiontree::inorder_nr(exp *root)
{
exp *curr=root;
exp *stack[MAX];
int top=-1;
while(1)
{
if(curr)
{
stack[++top]=curr;
curr=curr->lchild;
}
else
{
if(top!=-1)
{
curr=stack[top--];
cout<<curr->data;
curr=curr->rchild;
}
else
{
break;
}
}
}
}

void Expresiontree::preorder_r()
{
preorder_r(root);
}
void Expresiontree::preorder_r(exp *root)
{
if(root)
{
cout<<root->data;
preorder_r(root->lchild);
preorder_r(root->rchild);
}
}

void Expresiontree::preorder_nr()
{
preorder_nr(root);
}
void Expresiontree::preorder_nr(exp *root)
{
exp *stack[MAX],*curr=root;
int top=-1;
while(1)
{
if(curr)
{
cout<<curr->data;
stack[++top]=curr;
curr=curr->lchild;
}
else
{
if(top!=-1)
{
curr=stack[top--];
curr=curr->rchild;
}
else
{
break;
}
}
}
}

void Expresiontree::postorder_r()
{
postorder_r(root);
}
void Expresiontree::postorder_r(exp *root)
{
if(root)
{
postorder_r(root->lchild);
postorder_r(root->rchild);
cout<<root->data;
}
}

void Expresiontree::postorder_nr()
{
postorder_nr(root);
}
void Expresiontree::postorder_nr(exp *root)
{
exp *curr=root;
exp *stack[MAX];
int top=-1;
char flag[MAX],f;
while(1)
{
if(curr)
{
stack[++top]=curr;
flag[top]='L';
curr=curr->lchild;
}
else
{
if(top!=-1)
{
curr=stack[top];
f=flag[top];
top--;
if(f=='L')
{
stack[++top]=curr;
flag[top]='R';
curr=curr->rchild;
}
else
{
cout<<curr->data;
curr=NULL;
}
}
else
{
break;
}
}
}
}

int main()
{
char postfix[MAX];
int choice;
Expresiontree obj;
while(choice!=8)
{
cout<<"\nMENU\n";
cout<<"1.Create\n2.Inorder Recursive Traversal\n3.Inorder Non Recursive Traversal\n4.Preorder Recursive Traversal\n5.Preorder Non Recursive Traversal\n6.Postorder Recursive Traversal\n7.Postorder Non Recursive Traversal\n8.Exit";
cout<<"\nEnter choice:-\t";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the postfix expression:-";
cin>>postfix;
obj.create(postfix);
break;
case 2:
cout<<"\nInorder Recursive Traversal\n";
obj.inorder_r();
break;
case 3:
cout<<"\nInorder Non Recursive Traversal\n";
obj.inorder_nr();
break;
case 4:
cout<<"\nPreorder Recursive Traversal\n";
obj.preorder_r();
break;
case 5:
cout<<"\nPreorder Non Recursive Traversal\n";
obj.preorder_nr();
break;
case 6:
cout<<"\nPostorder Recursive Traversal\n";
obj.postorder_r();
break;
case 7:
cout<<"\nPostorder Non Recursive Traversal\n";
obj.postorder_nr();
break;
case 8: exit (0);
}
}

}