Hi all,
You guys have been so helpful in the past, I thought you might be able to help me again.
I've got a routine built up for building a binary tree- and that seems to be working so far, but I'm having difficulty with my binary tree destroying routines.
Here is the structure
Code:
typedef struct node
{
//sequence for this node
amino_acid_list *sequence;
// not currently used- in case sequence length changes
int sequence_length;
// distance (in amino acid substitutions)
int mutation_distance_from_parent;
int mutation_distance_to_left;
int mutation_distance_to_right;
// distance (absolute? not yet used)
int distance_from_parent;
int distance_to_left;
int distance_to_right;
// depth of this node
int depth;
// debugging
int data;
// pointers
struct node *parent_ptr;
struct node *left_ptr;
struct node *right_ptr;
} node;
And here is my type amino_acid_list
Code:
typedef enum amino_acid_list
{
a= 0, ala= 0, alanine= 0,
r= 1, arg= 1, arginine= 1,
n= 2, asn= 2, asparagine= 2,
d= 3, asp= 3, aspartic_acid= 3,
c= 4, cys= 4, cysteine= 4,
q= 5, gln= 5, glutamine= 5,
e= 6, glu= 6, glutamic_acid= 6,
g= 7, gly= 7, glycine= 7,
h= 8, his= 8, histidine= 8,
i= 9, lle= 9, isoleucine= 9,
l= 10, leu= 10, leucine= 10,
k= 11, lys= 11, lysine= 11,
m= 12, met= 12, methionine= 12,
f= 13, phe= 13, phenylalanine= 13,
p= 14, pro= 14, proline= 14,
s= 15, ser= 15, serine= 15,
t= 16, thr= 16, threonine= 16,
w= 17, trp= 17, tryptophan= 17,
y= 18, tyr= 18, tyrosine= 18,
v= 19, val= 19, valine= 19
} amino_acid_list;
Here is the bit of code that's not working properly
Code:
void destroy_tree(node *n)
{
if (n==NULL)
{
//printf("no tree- found\nend\n");
return;
}
// printf("destroying a tree\n");
if (n!=NULL)
{
printf("destroying left tree, called from depth %d\n", n->depth);
destroy_tree(n->left_ptr);
printf("destroying right tree, called from depth %d\n", n->depth);
destroy_tree(n->right_ptr);
printf("%d ", n->data);
free(n->sequence);
free(n);
}
}
The program crashes at free(n->sequence). If I comment out that line, other than having a big memory leak, the program works. If left as it is, the program crashes exactly at that line.
Note, when I print out the tree, my print_tree function correctly prints out the sequence stored at n-> sequence, suggest that I'm correctly allocating memory for sequence, and that I'm assigning it data correctly.
I don't understand what the problem is. I'm also going to post the functions I use to create the tree, in case I'm doing something kind of goofy in there, and it's creating a problem that I'm only picking up on, here.
Code:
node *build_tree(node *n, node* nprev, int depth, int maxdepth, amino_acid_list *a, int sequence_length, const float ........r, float **tpm, int dist, float random_param_one, float random_param_two)
// n is the base previous node, or NULL if we're starting the tree
// nprev is the parental node that this new node is derived from
// depth is the current depth of this node
// maxdepth is the maximum depth of the tree (normally 7, 8 or 9)
// a is the amino acid sequence being passed
// if it's NULL, then we will randomly create our own sequence, starting with a methionine
// otherwise, it will just be assigned to the base node
//
// sequence_length is the length of the amino acid sequence
{
// for debugging!
static int count= 0;
amino_acid_list *new_sequence;
if (depth >= maxdepth)
{
return NULL;
}
int i, num_mutations;
// only do this if no sequence is defined
if (a==NULL)
{
// for debugging
printf("only see this once\n");
a= calloc(sequence_length, sizeof(amino_acid_list));
a[0]= m;
// we need to make this starting sequence and then burn it in
for (i= 1; i < sequence_length; i++)
{
a[i]= genrand_real1()*19;
}
// burn in the base sequence
for (i= 0; i < 100000; i++)
{
num_mutations= i_number_mutations(dist, random_param_one, random_param_two);
mutate_sequence(a, sequence_length, num_mutations, ssr, tpm);
}
}
if (n==NULL && depth < maxdepth)
{
n= calloc(1, sizeof(node));
n->depth= depth;
n->sequence_length= sequence_length;
n->sequence= a;
n->parent_ptr= nprev;
count++;
n->data= count;
if (n->left_ptr == NULL)
{
new_sequence= make_child_sequence(n->sequence, ssr, tpm, sequence_length, dist, random_param_one, random_param_two);
n->left_ptr= build_tree(n->left_ptr, n, n->depth+1, maxdepth, n->sequence, sequence_length, ssr, tpm, dist, random_param_one, random_param_two);
}
if (n->right_ptr == NULL)
{
new_sequence= make_child_sequence(n->sequence, ssr, tpm, sequence_length, dist, random_param_one, random_param_two);
n->right_ptr= build_tree(n->right_ptr, n, n->depth+1, maxdepth, n->sequence, sequence_length, ssr, tpm, dist, random_param_one, random_param_two);
}
}
return n;
}
Code:
amino_acid_list *make_child_sequence(const amino_acid_list *parental, const float *site_substitution_rate, float **transition_matrix, int sequence_length, int dist, float random_param_one, float random_param_two)
{
// i don't have a random number deviate generator yet, so temporarily I will just assign num_mutations from dist
int num_mutations= i_number_mutations(dist, random_param_one, random_param_two);
int i;
if (parental == NULL)
{
printf("no starting sequence specified in make_child_sequence().\nexiting\n");
exit(-1);
}
if (site_substitution_rate == NULL)
{
printf("variable passed for site_substitution_rate in make_child_sequence() invalid\n");
printf("exiting\n");
exit(-1);
}
if (transition_matrix == NULL)
{
printf("variable passed for transition_matrix in make_child_sequence() invalid\n");
printf("exiting\n");
exit(-1);
}
if (sequence_length < 1)
{
printf("sequence length passed to make_child_sequence() is too small at %d\nexiting\n", sequence_length);
exit(-1);
}
// make a copy of the parental sequence
amino_acid_list *temporary_sequence; // copy_sequence(parental, sequence_length);
temporary_sequence= calloc(sequence_length, sizeof(amino_acid_list));
// we need to make this starting sequence and then burn it in
for (i= 0; i < sequence_length; i++)
{
temporary_sequence[i]= parental[i];
}
// mutate the parental sequence to create the child sequence
mutate_sequence(temporary_sequence, sequence_length, num_mutations, site_substitution_rate, transition_matrix);
// return the child sequence
return temporary_sequence;
}
Thanks,
Brad