Thread: Difficulty with destroying elements in a tree

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    40

    Difficulty with destroying elements in a tree

    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

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You don't appear to bother setting n->sequence, 99% of the time (only when N was originally NULL).

  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    40
    Quote Originally Posted by tabstop View Post
    You don't appear to bother setting n->sequence, 99% of the time (only when N was originally NULL).
    I'll take a look at that, but it should be NULL all the time, because that's when I'm adding something to the end of the tree- but maybe my logic is wrong there.

    Thanks,
    Brad

  4. #4
    Registered User
    Join Date
    Mar 2010
    Posts
    40
    Nevermind, I think I see the problem. I'm only ever adding sequences to the terminal nodes, the non-terminal nodes are instantiated, but none of the internal nodes ever have sequences assigned to them.

    Thanks tabstop.

  5. #5
    Registered User
    Join Date
    Mar 2010
    Posts
    40
    I was about to post another question here about a memory leak problem that I still had, that I couldn't track down. As I posted the code, and wrote a description of the problems I was having, and the test cases, I was immediately able to see where the memory leak was, and solve it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM