Member Avatar for sajay

Hello
I'm coding an algorithm based on genetic programming with tree structures in C. I implemented tree structure using recursive structure pointers **The traditional way**

struct tree
{
int val;
tree *left;
tree *right;
};


tree a[10];
tree b[20];

void main()
{
generate (); // this generates me 10 random trees and places them in a

b[0] = a[0]; // copies val, left and right correspondingly

// though b[0].left and a[0].left are stored separately, both point to the same location
// if i change a[0].left->val , it correspondingly reflects when i access b[0].left->
// This is not intended for my application when i let crossover and mutation play over // my trees.
// So i must (something like) clone trees to have seperate copies.

And could not sort out a way to clone my trees (binary trees)
Any kind of help is appreciated.

  • 2 Contributors
  • 3 Replies
  • 207 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by sajay

Dani AI

Generated

The symptom here is a shallow copy: b[0] = a[0] duplicates the pointer fields, so both roots reference the same subtrees. For Genetic Programming you want a deep copy (every node duplicated) so offspring operations do not mutate parents. Also note the pitfall pointed out: sink = NULL; inside a function only changes the local pointer, it does not free memory or change the caller’s pointer.

A simple, robust pattern is to write a cloning function that returns a newly allocated root (caller never has to pre-allocate the sink). It naturally handles terminals because a NULL source returns NULL:

struct tree *clone_tree(const struct tree *src)
{
    if (src == NULL) return NULL;
    struct tree *n = malloc(sizeof *n);
    if (n == NULL) { perror("malloc"); return NULL; }
    n->val = src->val;
    n->left  = clone_tree(src->left);
    n->right = clone_tree(src->right);
    return n;
}

Always provide a matching destructor to avoid leaks:

void free_tree(struct tree *t)
{
    if (t == NULL) return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

Practical tips: store your population as an array of root pointers (e.g. struct tree *pop[N]) rather than an array of whole tree structs—that makes allocation and swapping clearer. Check malloc failures and test with Valgrind. If cloning every time becomes a bottleneck, consider an arena/node-pool allocator or copy-on-write/persistent-tree techniques, or move to C++ and use RAII/smart pointers for safer memory management. If you want, post your generate() routine and population layout and someone can point out the smallest change to integrate cloning safely.

Recommended Answers

All 3 Replies

Member Avatar for sajay

I tried and made up a function, but it is a bit messy.

void copy_tree(tree *sink, tree* source)
{
	if (source != NULL)
	{
		sink->val = source->val;
		sink->left = (tree*)malloc(sizeof(tree));
		sink->right = (tree*)malloc(sizeof(tree));
		copy_tree (sink->left, source->left);
		copy_tree (sink->right, source->right);
	}
	else
	{
		sink = NULL;
	}
}

but this function too has problems in terminating the terminals of the tree by assigning NULL to the left and right pointers of the terminal node.

Any kind of help and reviews are appreciated

:)

Member Avatar for Prabakar

First I don't understand the need to clone trees, having same data in two different places often cause problems than solving problems. Do you have a reason to do so?

sink = NULL;

Do you really expect this to free the memory you allocated? If so, you may have to go and read your c book again

May be you'll have to check before you recurs again

sink->val = source->val;
if(source->left){
    sink->left = malloc(sizeof(tree));
    copy_tree (sink->left, source->left);
}else{
    sink->left = NULL;
}
if(source->right){
    sink->right = malloc(sizeof(tree));
    copy_tree (sink->right, source->right);
}else{
    sink->right = NULL;
}

Please don't PM for answers

Edited by Prabakar because: n/a
Member Avatar for sajay

Thank you

I just came up with the same code

void copy_tree(tree *sink, tree* source)
{
	sink->val = source->val;
	if (source->left == NULL)
		sink->left = NULL;
	else
	{
		sink->left = (tree*)malloc(sizeof(tree));
		copy_tree (sink->left, source->left);
	}

	if (source->right == NULL)
		sink->right = NULL;
	else
	{
		sink->right = (tree*)malloc(sizeof(tree));
		copy_tree (sink->right, source->right);
	}
}

It is absolutely necessary for me to clone trees.
I don't want my genetic operators modify parents while they play on with offspring

I'm sorry with that sink = NULL;
I'm just a novice
:)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.