Breaking News
Loading...

Binary Tree Traversal Using Recursive and Non Recursive Function in C


#include<stdio.h>
#include<conio.h>
#include<alloc.h>

typedef struct bint
{
int data,flag;
struct bint *left,*right;
}node;

node * create(node *r,int d)
{
if(r == NULL)
{
r = (node *)malloc(sizeof(node));
r->data = d;
r->left = r->right = NULL;
}
else
{
if(r->data <= d)
r->right = create(r->right,d);
else
r->left = create(r->left,d);
}
return r;
}




void inorder(node *r)
{
if(r != NULL)
{
inorder(r->left);
printf("%d\t",r->data);
inorder(r->right);
}
}

void non_in(node *r)
{
int top=0;
node *s[20],*pt=r;
s[0]=NULL;
while(pt != NULL)
{
s[++top] = pt;
pt = pt->left;
}
pt = s[top--];
while(pt != NULL)
{
printf("%d\t",pt->data);
if(pt->right != NULL)
{
pt = pt->right;
while(pt != NULL)
{
s[++top] = pt;
pt = pt->left;
}
}
pt = s[top--];
}
}



void preorder(node *r)
{
if(r != NULL)
{
printf("%d\t",r->data);
preorder(r->left);
preorder(r->right);
}
}

void non_pre(node *r)
{
int top=0;
node *s[20],*pt=r;
s[0]=NULL;
while(pt != NULL)
{
printf("%d\t",pt->data);
if(pt->right != NULL)
s[++top] = pt->right;
if(pt->left != NULL)
pt = pt->left;
else
pt = s[top--];
}
}

void postorder(node *r)
{
if(r != NULL)
{
postorder(r->left);
postorder(r->right);
printf("%d\t",r->data);
}
}

void non_post(node *root)
{
node *stack[100];
int top=-1;
node *temp=root;
while(temp!=NULL)
{
while(temp!= NULL)
{
top++;
stack[top] = temp;
temp = temp->left;
}
label:temp =stack[top];
top--;
if(temp->flag==1)
{
printf("%d\t",temp->data);
break;
}
else
{
temp->flag=1;
top++;
stack[top] = temp;
temp=temp->right;
}
}
if(top>=0)
goto label;
}



void main()
{
 int d;
 char ch = 'Y';
 node *head = NULL;
 clrscr();
 while(toupper(ch) == 'Y')
 {
  printf("\n Enter the item to insert");
  scanf("%d",&d);
  head = create(head,d);
  printf("\n Do you want to continue(y/n)");
  fflush(stdin);
  ch = getchar();
 }
 printf("\ninorder recursive\n");
 inorder(head);
 printf("\ninorder non recursive\n");
 non_in(head);

 printf("\n\n");
 printf("\npostorder rrecursive\n");
 postorder(head);
 printf("\npostorder non recursive\n");
 non_post(head);

 printf("\n\n");
 printf("\npreorder recursive\n");
 preorder(head);
 printf("\npreorder non recursive\n");
 non_pre(head);
 getch();

}









Any problem in program please comment .......

7 comments:

  1. Call to undefined function 'toupper'.... :(

    ReplyDelete
    Replies
    1. ' toupper(arg) ' is a library functions in c ....

      Delete
  2. sir when i am compling it.It is showing that flag doesnt belong to flag in postorder.Thank yoy sir

    ReplyDelete
    Replies
    1. Sorry ,flag dosent belong to node in postorder function.Thank you sir

      Delete
  3. hello can you give explanation of it...

    ReplyDelete
  4. toupper should have a prototype,what to do......

    ReplyDelete

 
Toggle Footer