I am trying to solve the Josephus permutation using a binary search tree. I implemented the functions os_select and os_delete from Cormen, and I have the following problem:
typedef struct node
{
int key;
struct node *left;
struct node *right;
int size; //dimensiunea subarborelui cu radacina in key
} node;
void josephus(int n, int m)
{
node *root=build_tree(v,0,n-1); //this is tested, works perfectly
int k,j=1;
for(k=n;k>=1;k--)
{
j=((j+m-2)%k)+1;
node *x=os_select(root,j);
printf("%d ",x->key);
decSize(x,j);
os_delete(root,x->key);
}
//afisare_in_preordine(root,0);
}
When I run the program, I get a segmentation fault inside the os_select function:
node *os_select(node *x,int i)
{
int r=x->left->size+1; //i get the segmentation fault here...
if (i==r)
{
return x;
}
else
{
if(i<r)
{
return os_select(x->left,i);
}
else
{
return os_select(x->right,i-r);
}
}
}
If you need anymore pieces of code that I should add, please let me know.
Aucun commentaire:
Enregistrer un commentaire