Traversing a tree inorder and post and preorder using non recursive technique:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define STACKSIZE 20
struct treenode
{
int data;
struct treenode *left;
struct treenode *right;
} *root=NULL;
// stack functions
int top=-1; struct treenode *stack[STACKSIZE];
void push(struct treenode *temp)
{
if(top<STACKSIZE)
{
top++;
stack[top]=temp;
}
else
printf("stack overflow");
}
int pop()
{
int i;
if(top==-1)
{
printf("stackunderflow");
}
else
i=stack[top--];
return i;
}
int isstackempty()
{
if(top==-1)
return 1;
else return 0;
}
//end of stackfunctions
struct treenode * buildtree()
{
struct treenode *temp1,*temp2,*temp3,*temp4,*temp5;
root=(struct treenode *)malloc(sizeof(struct treenode));
temp1=(struct treenode *)malloc(sizeof(struct treenode));
temp2=(struct treenode *)malloc(sizeof(struct treenode));
temp3=(struct treenode *)malloc(sizeof(struct treenode));
temp4=(struct treenode *)malloc(sizeof(struct treenode));
root->data=4;
root->left=temp1;
temp1->data=5;
root->right=temp2;
temp2->data=6;
temp1->left=temp3;
temp3->data=7;
temp3->left=temp3->right=NULL;
temp1->right=temp4;
temp4->data=8;
temp4->left=NULL;
temp4->right=NULL;
temp2->left=temp2->right=NULL;
printf("\n tree buildedsuccessfull");
return root;
}
void inorder(struct treenode *root)
{
struct treenode *temp;
temp=root;
while(1)
{
while(temp!=NULL)
{
push(temp);
temp=temp->left;
}
if(isstackempty()) return;
temp=pop();
printf("%d ",temp->data);
temp=temp->right;
}
}
void preorder(struct treenode *root)
{
struct treenode *temp;
temp=root;
while(1)
{
while(temp!=NULL)
{
printf("%d ",temp->data);
push(temp);
temp=temp->left;
}
if(isstackempty()) return;
temp=pop();
temp=temp->right;
}
}
void postorder(struct treenode *root)
{
struct treenode *temp,*q;
temp=root;
while(1)
{
while(temp!=NULL)
{
push(temp);
temp=temp->left;
}
if(isstackempty()) return;
temp=pop();
if(((int)temp)<0)
{
temp=((unsigned int)temp)*-1;
printf("%d ",temp->data);
temp=NULL;
}
else
{
q=temp;
temp=temp->right;
q=((unsigned int)q)*-1;
push(q);
}
}
}
//main
void main()
{
int k=1,j;
struct treenode *root;
while(k)
{
printf("\n enter 1 to build tree");
printf("\n enter 2 to print preorder");
printf("\n enter 3 to print inorder");
printf("\n enter 4 print postoreder");
scanf("%d",&k);
switch(k)
{
case 1:
root=buildtree();
break;
case 2:
preorder(root);
break;
case 3:
inorder(root);
break;
case 4:
postorder(root);
break;
}
}
}
No comments:
Post a Comment