/*Write a program using object oriented programming using c++
to create a binary tree if inorder & preorder
or inorder & postorder, any two traversals are given*/
#include<iostream.h>
#include<conio.h>
#include<string.h>
#define MAX 20
class node
{
friend tree;
char ch;
node *left,*right;
node()
{
left=right=NULL;
}
};
class tree
{
node *root;
public:
tree();
void create1(char [],char []);
node * create11(char [],char []);
void create2(char [],char []);
node * create22(char [],char []);
void divide1(char [], char [], char [], char [], char [], char []);
void divide2(char [], char [], char [], char [], char [], char []);
void inorder();
void preorder();
void postorder();
void inorder(node *);
void preorder(node *);
void postorder(node *);
};//class tree
void tree::create1(char pre[],char in[])
{
root=create11(pre,in);
}
void tree::create2(char post[],char in[])
{
root=create22(post,in);
}
tree::tree()
{
root=NULL;
}
void tree::inorder()
{
inorder(root);
}
void tree::preorder()
{
preorder(root);
}
void tree::postorder()
{
postorder(root);
}
void tree::inorder(node *t)
{
if(t!=NULL)
{
inorder(t->left);
cout<<" "<<t->ch;
inorder(t->right);
}//if
}
void tree::preorder(node *t)
{
if(t!=NULL)
{
cout<<" "<<t->ch;
preorder(t->left);
preorder(t->right);
}//if
}
void tree::postorder(node *t)
{
if(t!=NULL)
{
postorder(t->left);
postorder(t->right);
cout<<" "<<t->ch;
}//if
}
node *tree::create11(char pre[], char in[])
{
char in1[MAX],in2[MAX],pre1[MAX],pre2[MAX];
int i,j,len;
node *tempnd;
// preorder sequence gives the root
len=strlen(pre);
if(len==0)
return NULL;
tempnd=new node;
tempnd->ch=pre[0];
// divide the preorder and inorder sequence for left and right subtrees
divide1(pre,in,pre1,pre2,in1,in2);
tempnd->left=create11(pre1,in1);
tempnd->right=create11(pre2,in2);
return (tempnd);
}//create11
void tree::divide1(char pre[], char in[], char pre1[], char pre2[], char in1[], char in2[])
{
int i,j,k,t,flag;
// left subtree, inorder
for(i=0;in[i]!=pre[0];i++)
{
in1[i]=in[i];
}
in1[i]=NULL;
i++; //leave the root
// right subtree, inorder
for(j=0;in[i]!=NULL;i++,j++)
{
in2[j]=in[i];
}
in2[j]=NULL;
// now divide the preorder sequence
for(i=0,j=0,k=1;pre[k]!=NULL;k++)
{
//Search for pre[k] in in1
for(t=0,flag=0;in1[t]!=NULL;t++)
{
if(in1[t]==pre[k])
{
pre1[i++]=pre[k]; // belongs to left subtree
flag=1;
break;
}//if
}//for
if(flag==0) // belongs to right subtree
{
pre2[j++]=pre[k];
}
}//outer for
pre1[i]=pre2[j]=NULL;
}//divide1
node *tree::create22(char post[], char in[])
{
char in1[MAX],in2[MAX],post1[MAX],post2[MAX];
int i,j,len;
node *tempnd;
// postorder sequence gives the root
len=strlen(post);
if(len==0)
return NULL;
tempnd=new node;
tempnd->ch=post[len-1];
// divide the postorder and inorder sequence for left and right subtrees
divide2(post,in,post1,post2,in1,in2);
tempnd->left=create22(post1,in1);
tempnd->right=create22(post2,in2);
return (tempnd);
}//create11
void tree::divide2(char post[], char in[], char post1[], char post2[], char in1[], char in2[])
{
int i,j,k,t,flag,len;
len=strlen(post);
// post[len-1] contains root
// so we can get left subtree, inorder
for(i=0;in[i]!=post[len-1];i++)
{
in1[i]=in[i];
}
in1[i]=NULL;
i++; //leave the root
// right subtree, inorder
for(j=0;in[i]!=NULL;i++,j++)
{
in2[j]=in[i];
}
in2[j]=NULL;
// now divide the postorder sequence
for(i=0,j=0,k=0;k<len-1;k++)
{
//Search for pre[k] in in1
for(t=0,flag=0;in1[t]!=NULL;t++)
{
if(in1[t]==post[k])
{
post1[i++]=post[k]; // belongs to left subtree
flag=1;
break;
}//if
}//for
if(flag==0) // belongs to right subtree
{
post2[j++]=post[k];
}
}//outer for
post1[i]=post2[j]=NULL;
}//divide1
int menu()
{
int choice;
cout<<"\n1.Inorder and Preorder\n2.Inorder and PostOrder\n3.exit\n\nChoice : ";
cin>>choice;
return choice;
}//menu
void main()
{
tree t;
char in[MAX],post[MAX],pre[MAX];
clrscr();
int choice;
while(1)
{
choice=menu();
switch(choice)
{
case 1: cout<<"enter preorder traversal\n";
cin>>pre;
cout<<"enter inorder traversal\n";
cin>>in;
t.create1(pre,in);
cout<<"\nPostorder traversal is\n";
t.postorder();
break;
case 2: cout<<"enter inorder traversal\n";
cin>>in;
cout<<"enter postorder traversal\n";
cin>>post;
t.create2(post,in);
cout<<"\nPreorder traversal is\n";
t.preorder();
break;
case 3: cout<<"\nProgram ending....";
getch();
return;
default:cout<<"\nWrong choice...";
}//switch
}//while
}//main
0 comments:
Post a Comment