for example we are given a binary tree like this
7
/ \
3 5
/ \ /
1 2 4
sum for 1st band is 1.
sum for 2nd band is 3
sum for 3rd band is (7+2+4)=13.
sum for 4th band is 5
.
here is the trick -
1.if we go left of any node we decrement band by 1 of current node.
2. if we to right child increment band by 1 of current node.
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct node{
int data;
node *left,*right;
};
std::vector<std::vector<int> > v;
struct que{
node *arr[100];
int top;
int rear;
int capacity;
int size;
};
void hashing(int a,int ver)
{
int index=ver%100;
v[index].push_back(a);
}
void printvert(node *temp,int ver)
{
hashing (temp->data,ver);
if(temp->left!=NULL)
printvert(temp->left,ver-1);
if(temp->right!=NULL)
printvert(temp->right,ver+1);
}
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);
}
}
int main()
{
ifstream fin;
int k;
v.resize(100);
fin.open("/home/pawan/Desktop/ds/input.txt");
if(!fin.is_open())
cout<<"file not opened\n";
node *t;
t=NULL;
int a,a1;
fin>>a;
a1=a;
int i=0;
while(a1!=-1)
{
create(t,a1);
fin>>a;
a1=a;
i++;
}
int m=i;
fin.close();
printvert(t,i/2);
cout<<"yaha tak";
for (i = 0; i < m; i++)
{
for(int j=0;j<v[i].size();j++)
{
// if(v[i][j]>0)
cout<<v[i][j]<<" ";
}
cout<<endl;
}
}
7
/ \
3 5
/ \ /
1 2 4
sum for 1st band is 1.
sum for 2nd band is 3
sum for 3rd band is (7+2+4)=13.
sum for 4th band is 5
.
here is the trick -
1.if we go left of any node we decrement band by 1 of current node.
2. if we to right child increment band by 1 of current node.
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct node{
int data;
node *left,*right;
};
std::vector<std::vector<int> > v;
struct que{
node *arr[100];
int top;
int rear;
int capacity;
int size;
};
void hashing(int a,int ver)
{
int index=ver%100;
v[index].push_back(a);
}
void printvert(node *temp,int ver)
{
hashing (temp->data,ver);
if(temp->left!=NULL)
printvert(temp->left,ver-1);
if(temp->right!=NULL)
printvert(temp->right,ver+1);
}
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);
}
}
int main()
{
ifstream fin;
int k;
v.resize(100);
fin.open("/home/pawan/Desktop/ds/input.txt");
if(!fin.is_open())
cout<<"file not opened\n";
node *t;
t=NULL;
int a,a1;
fin>>a;
a1=a;
int i=0;
while(a1!=-1)
{
create(t,a1);
fin>>a;
a1=a;
i++;
}
int m=i;
fin.close();
printvert(t,i/2);
cout<<"yaha tak";
for (i = 0; i < m; i++)
{
for(int j=0;j<v[i].size();j++)
{
// if(v[i][j]>0)
cout<<v[i][j]<<" ";
}
cout<<endl;
}
}
No comments:
Post a Comment