Saturday 26 July 2014

In Order Traversal in Binary Search Tree without Recursion and Stack

//The code is not optimized because I wanted it to be easily understandable by  //beginners too. 

#include<stdio.h>
#include<malloc.h>
struct Node 
{
int num;
struct Node *left, *right;
};
struct Node *start=NULL;
void addNode(int num)                 //To add nodes in the tree.
{
struct Node *t,*j;
t=(struct Node *)malloc(sizeof(struct Node));
t->num=num;
t->left=NULL;
t->right=NULL;
if(start==NULL) start=t;
else
{
j=start;
while(1)
{
if(t->num<j->num)
{
if(j->left==NULL)
{
j->left=t;
break;
}
else j=j->left;
}
else
{
if(j->right==NULL)
{
j->right=t;
break;
}
else
{
j=j->right;
}
}
}
}
}

void traverseInOrder(struct Node *t)  // Function for Traversal
{
struct Node *p2;
t=start;
while(t!=NULL)
{
if(t->left==NULL)
{
printf("%d\n",t->num);
t=t->right;
}
else
{
p2=t->left;
while(p2->right!=NULL && p2->right!=t)
{
p2=p2->right;
}
if(p2->right==NULL)
{
p2->right=t;
t=t->left;
}
else
{
p2->right=NULL;
printf("%d\n",t->num);
t=t->right;
}
}
}
}

void main()
{
int ch,num;
while(1)
{
printf("\n1.Add a number \n2.In order traversal \n3.Exit\t");
scanf("%d",&ch);
if(ch==1)
{
printf("Enter a number to add: ");
scanf("%d",&num);
addNode(num);
}
if(ch==2) traverseInOrder(start);
if(ch==3) break;
}
}


No comments:

Post a Comment