#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
int rthread;
struct node *left,*right;
}NODE,*NODEPTR;
NODEPTR getnode()
{
NODEPTR temp;
temp=(NODEPTR)malloc(sizeof(NODE));
temp->left=NULL;
temp->rthread=1;
return temp;
}
NODEPTR insucc(NODEPTR s)//to find the inorder successor
{
NODEPTR p=s->right;
if(s->rthread==0)
while(p->left!=NULL)
p=p->left;
return p;
}
void inorder(NODEPTR h)//function to traverse in in-order
{
NODEPTR t=h;
while(1)
{
t=insucc(t);
if(t==h)
return;
printf("%d\n",t->data);
}
}
NODEPTR create(NODEPTR head)
{
NODEPTR y,t,q[100];
int f=0,r=0,v;
y=getnode();
q[r++]=y;
printf("Enter the root:");
scanf("%d",&y->data);
y->right=head;
head->right=y;
head->rthread=0;
while(f!=r)
{
t=q[f++];
printf("\nEnter the left child(%d) :",t->data);
do
{
printf("Left child should be smaller\n");
scanf("%d",&v);
if(v==-1)break;
}while(v>t->data);
if(v!=-1)
{
y=getnode();
q[r++]=y;
t->left=y;
y->right=t;
y->data=v;
}
printf("Enter the right child(%d) :",t->data);
do
{
printf("Right child should be greater\n");
scanf("%d",&v);
if(v==-1)break;
}while(v<t->data);
if(v!=-1)
{
y=getnode();
y->right=t->right;
t->right=y;
y->data=v;
t->rthread=0;
q[r++]=y;
}
}
return head;
}
int main()
{
NODEPTR head;
head=getnode();
head=create(head);
printf("Inorder traversal : \n");
inorder(head);
}
PS : A very long, inefficient code.. Try to understand at your own risk!
No comments:
Post a Comment