inorder traversal in c++

SOURCE CODE :

//programed by Paras Wadher
MCA
Nagpur university

//program for inorder traversal
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<math.h>
#include<ctype.h>
class inorder
{
public:

int stack[50],rightc[50],n,leftc[50],i,j,c,ptr;
int top;
char data[50],array[50];

inorder();
void traverse();
void getdata();
void repeat();
void display();

};
inorder::inorder()
{
top=0;
stack[top]=-2;
ptr=0;
}
void inorder::getdata()
{
cout<<“Enter the no. of nodes:”;
cin>>n;
for(i=0;i<n;i++)
{
array[i]=’\0′;
leftc[i]=0;
rightc[i]=0;
}
cout<<“Enter the root:”;
cin>>array[c];
c++;
while(c<(n-1))
{
while(leftc[j]==-1)
{
j++;
if(leftc[j]!=-1)
continue;
}
cout<<“Enter the left child:”;
cin>>array[c];
if(array[c]==’x’)
{
leftc[j]=-1;
rightc[c]=-1;
leftc[c]=-1;
array[c]=’ ‘;
}
else
{
leftc[j]=c;
}
c++;
while(rightc[j]==-1)
{
j++;
if(rightc[j]!=-1)
continue;
}
cout<<“Enter the right child:”;
cin>>array[c];
if(array[c]==’x’)
{
rightc[j]=-1;
rightc[c]=-1;
leftc[j]=-1;
array[c]=’ ‘;
}
else
{
rightc[j]=c;
}
c++;
j++;
}
for(i=0;i<n;i++)
{
if(leftc[i]==0||rightc[i]==0)
{
leftc[i]=-1,rightc[i]=-1;
}
}
}
void inorder::repeat()
{
while(ptr!=-1)
{
top++;
stack[top]=ptr;
ptr=leftc[ptr];
}
ptr=stack[top];
top–;
}
void inorder::traverse()
{
j=0;
repeat();
while(ptr!=-2)
{
data[j]=array[ptr];
j++;
if(rightc[ptr]!=-1)
{
ptr=rightc[ptr];
repeat();
}
else
{
ptr=stack[top];
top–;
}
}
}
void inorder::display()
{
for(int k=0;k<j;k++)
{
cout<<” “<<data[k];
}
}
main()
{
clrscr();
inorder t;
t.getdata();
t.traverse();
t.repeat();
t.display();
getch();
}

………………OUTPUT……………………………………….
Enter the no. of nodes:7
Enter the root:a
Enter the left child:b
Enter the right child:c
Enter the left child:d
Enter the right child:e
Enter the left child:x
Enter the right child:f
d b e a c f

Leave a Reply

Your email address will not be published. Required fields are marked *