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
  • 187 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by sajay
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.