I have come up with my implementation of binary tree that ensures that all the fillable positions in a particular level are filled ( that is the number of nodes at level k must be 2^k before proceeding to the next level). Unfortunately I am getting segmentation fault.
#include <iostream>
#include <math.h>
#define ll long long int
using namespace std;
struct node
{
int value=0;
node* left=NULL;
node* right=NULL;
int height=0;
int numnodes();
node()
{
}
node(int val,node* l=NULL,node* r=NULL) : value(val),left(l),right(r)
{}
int getheight();
node* operator=(node* n)
{
this->value=n->value;
this->right=n->right;
this->left=n->left;
}
}*binrooter;
int node::numnodes()
{
if(this->left==NULL && this->right==NULL)
return 0;
return this->left->numnodes()+this->right->numnodes()+1;
}
int node::getheight()
{
return max(this->left->getheight(),this->right->getheight())+1;
}
node* insertbintree(node* binrooter,ll num)
{
if(binrooter==NULL)
return new node(num);
if(binrooter->value==num)
return NULL;
if(binrooter->left==NULL)
{
cout<<"Inserting left"<<endl;
binrooter->left=new node(num);
}
else
if(binrooter->right==NULL)
{
cout<<"Inserting right"<<endl;
binrooter->right=new node(num);
}
else
{
int k=binrooter->getheight();
int numchild=pow(2,k);
if(binrooter->numnodes()==numchild-1)
numchild=pow(2,k+1);
if(binrooter->left->numnodes()>numchild/2)
{
cout<<"Traversing right"<<endl;
binrooter->right=insertbintree(binrooter->right,num);
}
else
{
cout<<"Traversing left"<<endl;
binrooter->left=insertbintree(binrooter->left,num);
}
}
return binrooter;
}
void insertbintree(ll num)
{
binrooter=insertbintree(binrooter,num);
}
void print(node *root)
{
if(root!=NULL)
{
print(root->left);
cout<<root->value<<" ";
print(root->right);
}
}
int main()
{
ll num=0;
do
{
cout<<endl<<"Enter the element to be inserted or enter -1"<<endl;
cin>>num;
if(num==-1)
{
break;
}
insertbintree(num);
}
while(num!=-1);
cout<<"printing tree in sorted order"<<endl;
print(rooter);
}
The problem is that if I try to insert more than 3 nodes, I get segmentation fault. I kind of figured out that the error lies somewhere in using the getheight() to insert in leftsubtree or rightsubtree, but I can't exactly pinpoint the error
Aucun commentaire:
Enregistrer un commentaire