vendredi 2 octobre 2015

C++ segmentation fault binary trees using pointers

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