Friday, March 14, 2014

COMPARE 2 TREES in C++

Comparing two tree means check each and every node of tree on each level that it is equal or not.
for two similar trees parent as well as both child node should be equal.
the code for comparing two trees is given below.


first tree           and second tree
we copare node 'a' with 'x' and its child subtrees with 'others child subtree.







#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
struct btree                                     //defined the node structure
{
btree *lchild;
char data;
btree *rchild;
};
btree* bcreate(btree *t,char k);
void printsort(btree *t,char b[15]);
int l=0,m=0;
int main()
{
btree *p=NULL,*q=NULL;
char d,a[15],b[15],c[15];
int n,i;
cout<<"tree data\n";
cin>>d;
p=bcreate(p,d);
printsort(p,a);
a[l]='\0';
n=l;
l=0;
cout<<"tree data\n";
cin>>d;
q=bcreate(q,d);
printsort(q,b);
b[l]='\0';
for(i=0;i<l; i++)
{
c[i]=b[l-1-i];
}
c[l]='\0';
if(!strcmp(a,b))
cout<<"similar";
else if(!strcmp(a,c))
cout<<"mirror";
else
cout<<"nonsimilar";
return 0;
}
btree* bcreate(btree* t,char k)                     //to get input from user
{

                                             btree *s=NULL,*r=NULL;char c1,c2;
if(t==NULL && k!='.')                        //k='.' used  here for stop making nodes in tree
{
t=new(btree);
t->data=k;
t->rchild=NULL; t->lchild=NULL;
cout<<"enter left and right child of "<<k<<endl;
cin>>c1>>c2;
t->lchild=bcreate(s,c1);                     //recursive call for create child
t->rchild=bcreate(r,c2);
}
return t;
}
void printsort(btree *t,char b[15])                       // f\print the tree content in sorted order  nodes                                                                                              // (left child,parent ,right child) and store in character array
{                                                                          
if(t!=NULL)
if(t->lchild==NULL && t->rchild==NULL)
b[l++]=t->data;
else
{
printsort(t->lchild,b);
b[l++]=t->data;
printsort(t->rchild,b);
}
}

No comments:

Post a Comment

Contributors

Translate