0
#include<stdio.h>
#include<conio.h>
#define MAX 30
typedef struct ETREE
{
struct ETREE *lc;
char data;
struct ETREE *rc;
}etree;
typedef struct STACK
{ etree *ST[MAX];
int top;
}stack;
void initialize_stack(stack *sp)
{
sp->top = -1;
}
int isstackempty(int top)
{
if(top MAX - 1)
return(1);
else
return(0);
}
void push(stack *sp,etree *x)
{
if(!isstackfull(sp->top))
{
sp->top = sp->top + 1;
sp->ST[sp->top] = x;
}
else
printf("\n\nStack full!!");
}
etree *pop(stack *sp)
{
etree *x;
if(!isstackempty(sp->top))
{
x = sp->ST[sp->top];
sp->top = sp->top - 1;
return(x);
}
else
return(NULL);
}
etree *getnode(char d)
{
etree *node;
node = (etree *)malloc(sizeof(etree));
node->lc = NULL;
node->data = d;
node->rc = NULL;
return(node);
}
etree *construct_etree_from_postfix_exp(char pos[])
{
int i;
stack s;
etree *root = NULL,*node;
initialize_stack(&s);
for(i=0;pos[i] != '\0';i++)
{
node = getnode(pos[i]);
if(isalpha(pos[i]))
{
push(&s,node);
}
else //operator
{
node->rc = pop(&s);
node->lc = pop(&s);
push(&s,node);
}
}
root = pop(&s);
return(root);
}
void inorder(etree *temp)
{
if(temp!= NULL)
{
inorder(temp->lc);
printf("%c",temp->data);
inorder(temp->rc);
}
}
void preorder(etree *temp)
{
if(temp!= NULL)
{
printf("%c",temp->data);
preorder(temp->lc);
preorder(temp->rc);
}
}
void postorder(etree *temp)
{
if(temp!= NULL)
{
postorder(temp->lc);
postorder(temp->rc);
printf("%c",temp->data);
}
}
void inorder_nonrec(etree *root)
{
stack s;
etree *temp;
temp = root;
initialize_stack(&s);
while(temp!=NULL s.top!= -1)
{
while(temp!=NULL)
{
push(&s,temp);
temp = temp->lc;
}
temp = pop(&s);
printf("%c",temp->data);
temp = temp->rc;
}
}
void preorder_nonrec(etree *root)
{
stack s;
etree *temp;
temp = root;
initialize_stack(&s);
while(temp!=NULL s.top!= -1)
{
while(temp!=NULL)
{
printf("%c",temp->data);
push(&s,temp);
temp = temp->lc;
}
temp = pop(&s);
temp = temp->rc;
}
}
void postorder_nonrec(etree *root)
{
stack s;
etree *temp;
int i,k=0;
char A[30];
temp = root;
initialize_stack(&s);
while(temp!=NULL s.top!= -1)
{
while(temp!=NULL)
{
A[k++] = temp->data;
push(&s,temp);
temp = temp->rc;
}
temp = pop(&s);
temp = temp->lc;
}
for(i=k-1;i>=0;i--)
{
printf("%c",A[i]);
}
}
void main()
{
char pos[30];
etree *root = NULL;
int ch;
do
{
clrscr();
printf("\n Choice 1: Create Etree from postfix expression ");
printf("\n Choice 2: Recursive inorder,preorder & postorder traversal");
printf("\n Choice 3: Nonrecursive inorder,preorder & postorder traversal");
printf("\n Choice 4: exit ");
printf("\n Enter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\n\nEnter the postfix expression : ");
scanf("%s",pos);
root = construct_etree_from_postfix_exp(pos);
printf("\n\nExpression tree created successfully !!");
break;
case 2:
printf("\n Inorder traversal is : ");
inorder(root);
printf("\n preorder traversal is : ");
preorder(root);
printf("\n postorder traversal is : ");
postorder(root);
getch();
break;
case 3:
printf("\n Inorder traversal (nonrecursive) : ");
inorder_nonrec(root);
printf("\n Preorder traversal (nonrecursive) : ");
preorder_nonrec(root);
printf("\n Postorder traversal (nonrecursive) : ");
postorder_nonrec(root);
getch();
break;
case 4: printf("\n \t**End of program** \n \t\tThank you\n");
break;
default:printf("\n invalid choice try again!!!!");
}
getch();
}while(ch!=4);
}
Written by: Fabianski Benjamin
What else can I help you with?
Why recursive solution is better for tree traversal?
Because a tree is a recursive data-structure. It's easier to write (and easier to understand) a recursive program for handling it.
What is the time complexity of tree traversal?
The time complexity of tree traversal is O(n), where n is the number of nodes in the tree.
What is traverse technique used in chain survey?
1. pre-order b-tree traversal. 2. in-order b-tree traversal. 3. post-order b-tree traversal
C program which accepts in order and preorder traversal outputs of a binary tree as input and prints the corresponding binary tree?
any body can help on this ?
What is the time complexity of binary tree traversal?
The time complexity of binary tree traversal is O(n), where n is the number of nodes in the tree.
What is the time complexity of inorder traversal in a binary tree?
The time complexity of inorder traversal in a binary tree is O(n), where n is the number of nodes in the tree.
Which of the following traversal is used for printing the keys of binary search tree in ascending order?
In order traversal is used.
What is the time complexity of tree traversal algorithms?
The time complexity of tree traversal algorithms is typically O(n), where n is the number of nodes in the tree. This means that the time taken to traverse a tree is directly proportional to the number of nodes in the tree.
Inorder traversal program in c plus plus?
In-order traversal relates to non-empty binary trees which can be traversed in one of three ways: pre-order, in-order and post-order. The current node is always regarded as being the root of the traversal, and all operations occur recursively upon that root. Pre-order: 1. Visit the root. 2. Traverse the left sub-tree. 3. Traverse the right sub-tree. In-order: 1. Traverse the left sub-tree. 2. Visit the root. 3. Traverse the right sub-tree. Post-order: 1. Traverse the left sub-tree. 2. Traverse the right sub-tree. 3. Visit the root.
What is the purpose of performing a binary search tree inorder traversal?
Performing a binary search tree inorder traversal helps to visit all nodes in the tree in ascending order, making it easier to search for specific values or perform operations like sorting and printing the elements in a sorted order.
How do you generate a parse tree from an expression using C program?
c code for top down parser
How does n-ary tree traversal work and what are the different strategies for traversing an n-ary tree efficiently?
N-ary tree traversal involves visiting each node in an n-ary tree in a specific order. The different strategies for efficiently traversing an n-ary tree include: Preorder traversal: Visit the current node first, then recursively visit each child node in order. Postorder traversal: Recursively visit each child node first, then visit the current node. Level order traversal: Visit nodes level by level, starting from the root and moving down each level before moving to the next level. These strategies help efficiently navigate through the nodes of an n-ary tree while ensuring that each node is visited exactly once.
