Sunday, July 26, 2015

Foldable binary tree

Consider the below trees:
(a) and (b) can be folded.
(c) and (d) cannot be folded.

(a)
       10
     /    \
    7      15
     \    /
      9  11

(b)
        10
       /  \
      7    15
     /      \
    9       11

(c)
        10
       /  \
      7   15
     /    /
    5   11

(d)

         10
       /   \
      7     15
    /  \    /
   9   10  12

#include <iostream>
#include <fstream>

using namespace std;
int sum[100];
struct node
{
int data;
node *left,*right;
};

void create(node *&t,int a)
{

if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a>t->data)
{
create(t->right,a);
}
else
{
create(t->left,a);
}
}
bool foldable(node *t1,node *t2)
{
if(t1==NULL&&t2==NULL)
return true;
else if(t1&&t2){
return (foldable(t1->left,t2->right)&&foldable(t1->right,t2->left));
}
return false;
}

int main()
{
for(int i=0;i<100;i++)
{
sum[i]=0;
}
ifstream fin;
int k;
fin.open("/home/pawan/Desktop/ds/input.txt");
if(!fin.is_open())

cout<<"file not opened\n";
node *t;
t=NULL;
int a,a1;
cin>>a;

while(a!=-1)
{
create(t,a);
cin>>a;

}
fin.close();
//cout<<"OLA";
print(t);
if(foldable(t->left,t->right))
cout<<"foldable\n";
else
cout<<"NOT foldable\n";


return 0;
}

No comments:

Post a Comment

Contributors

Translate