simple tree data struct implementation (beginner)

[sathyashrayan]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct tree
{
int data;
struct tree *left,*right;
};

void init(struct tree *node)
{
node = malloc(sizeof node);
if(!node)
{
printf("mem error\n");
exit(EXIT_FAILURE);
}
}

struct tree *assign(int data,struct tree *node)
{
struct tree *temp;
memmove(temp,node,sizeof node);
init(temp);
temp->data = data;
if(data < temp->data)
{
temp = temp->left;
temp->data = data;
}
else if(data > temp->data)
{
temp = temp->right;
temp->data = data;
}
else
temp->right = temp->left = NULL;
memmove(node,temp,sizeof node);
return node;
}

int print_tree(struct tree *node)
{
printf("%d\n",node->data);
while(node != NULL)
{
struct tree *temp;
memmove(temp,node,sizeof node);
temp = temp -> right;
print_tree(temp);
temp = temp-> left;
memmove(node,temp,sizeof node);
}
return 0;
}

int main(void)
{
struct tree *node;
node = assign(1 , node);
node = assign(2 , node);
node = assign(8 , node);
print_tree(node);
return 0;
}

This little, ugly code does not work as expected. I am getting a memory
overflow error. What could be the problem? Help.


--
"combination is the heart of chess"

A.Alekhine

Mail to:
sathyashrayan AT gmail DOT com

 

[bjrnove]

int print_tree(struct tree *node)
{
printf("%d\n",node->data);
while(node != NULL)
{
struct tree *temp;

memmove(temp,node,sizeof node);

There is at least one good reason it crashes. You cannot move data into
a "junk" pointer. Anyway, why do you need to move it? I haven't looked
at your code too closely, but I think removing the above line should
solve your problem.

 

[Richard Bos]

void init(struct tree *node)
{
node = malloc(sizeof node);

struct tree *assign(int data,struct tree *node)
{
struct tree *temp;
memmove(temp,node,sizeof node);
init(temp);

int print_tree(struct tree *node)
{
printf("%d\n",node->data);
while(node != NULL)
{
struct tree *temp;
memmove(temp,node,sizeof node);
temp = temp -> right;
print_tree(temp);
temp = temp-> left;
memmove(node,temp,sizeof node);
}

This little, ugly code does not work as expected. I am getting a memory
overflow error.

No wonder. You write through your pointer before you even try to
allocate memory for it; and even when you do, you do so in a way that
doesn't work. Read <http://www.eskimo.com/~scs/C-faq/q4.8.html>; and
then allocate memory _before_ you write to it.
(BTW, IMO "init" is not the right name for that function. All it does is
allocate memory; it does not initialise anything. Ditto for "assign",
which creates a whole new node, and doesn't just assign values.)
Also, when you get this to work, you're going to have fun with your
printing function. In particular, you're going to have fun watching it
spin merrily in its hamster-wheel, printing nothing.

Richard

 

[Martin Ambuhl]

sathyashrayan wrote:
[...]

struct tree *assign(int data,struct tree *node)
{
struct tree *temp;
memmove(temp,node,sizeof node); [...]
This little, ugly code does not work as expected. I am getting a memory
overflow error. What could be the problem? Help.

Among other things, temp is a wild pointer and there is no reason to
think that you code won't explode as soon as it hits that memmove.

 

[CBFalconer]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct tree
{
int data;
struct tree *left,*right;
};

void init(struct tree *node)
{
node = malloc(sizeof node);
if(!node)
{
printf("mem error\n");
exit(EXIT_FAILURE);
}
}

I read no further than here. The only function of init is to
either abort the program, or to create a memory leak. Think about
it.

 

[john_bode]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct tree
{
int data;
struct tree *left,*right;
};

void init(struct tree *node)
{
node = malloc(sizeof node);
if(!node)
{
printf("mem error\n");
exit(EXIT_FAILURE);
}
}

First problem: you're allocating the wrong amount of memory. You're
only allocating enough to hold an object of type struct tree*, not type
struct tree (type of node == struct tree*, type of *node == struct
tree). You need to dereference node in the sizeof operation to get the
right size.

Second problem: the assignment to node won't be reflected in the
calling function. Remember that to write to a parameter, you need to
pass a pointer to that type. If you want to write to a pointer, you
have to pass a pointer to a pointer, like so:

void init(struct tree **node)
{
*node = malloc(sizeof **node);
...
}
....

init(&temp);

Third problem: you aren't initializing the contents of the node after
you allocate it. The left and right members don't point anywhere
meaningful; they're just random bit strings that may or may not resolve
to valid addresses. If you *know* the left and right members will
*never* be read before they are assigned, it's not a problem. However,
it's usually good practice to explicitly initialize pointers to NULL.
That way you have a realiable test to see if they point anywhere
meaningful or not.

void init(struct tree **node)
{
*node = malloc(sizeof **node);
if (!*node)
{
/* handle memory allocation error */
}
(*node)->left = (*node)->right = NULL;
}

My personal preference is to write allocators as functions returning
the type of object being allocated, instead of passing the object to an
initializer function. Instead of void init(struct tree **node), I'd
use

struct tree *new_node(void)
{
struct tree *tmp = malloc(sizeof *tmp);
if (!tmp)
{
/* log memory allocation error */
return NULL;
}
tmp->left = tmp->right = NULL;
tmp->data = 0; // or some other initial value
return tmp;
}

I also write a corresponding deallocator function:

void destroy_node(struct tree **node)
{
if (*node)
{
free(*node);
*node = NULL;
}
}

struct tree *assign(int data,struct tree *node)
{
struct tree *temp;
memmove(temp,node,sizeof node);

Fourth problem (and the cause of your error): temp doesn't yet point
anywhere meaningful; you haven't attached a valid memory location to it
yet. You need to init temp before attempting to copy to it. Move the
init() call before this call.

There are other logic problems, but I have to run, and this should get
you past the initial memory errors.

 

[Old Wolf]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct tree
{
int data;
struct tree *left,*right;
};

void init(struct tree *node)
{
node = malloc(sizeof node);

node = malloc(sizeof *node)

if(!node)
{
printf("mem error\n");
exit(EXIT_FAILURE);
}
}

You never use the value of node so you have leaked memory.
Also you never use the value of 'node' that you passed in.
Try this (or the other posted solution):

struct tree *init(void)
{
struct tree *node = malloc(sizeof *node);
if (!node) {...........}
return node;
}

struct tree *assign(int data,struct tree *node)
{
struct tree *temp;
memmove(temp,node,sizeof node);
init(temp);

struct tree *temp;
temp = init();
memmove(temp, node, sizeof *temp);

temp->data = data;
if(data < temp->data)
{
temp = temp->left;

Here you leak the memory that you allocated with the call to init().

temp->data = data;
}
else if(data > temp->data)
{
temp = temp->right;

Same again.

temp->data = data;
}
else
temp->right = temp->left = NULL;
memmove(node,temp,sizeof node);

memmove(node, temp, sizeof *node);

return node;
}

int print_tree(struct tree *node)
{
printf("%d\n",node->data);
while(node != NULL)
{
struct tree *temp;
memmove(temp,node,sizeof node);

memmove(temp, node, sizeof *node);

temp = temp -> right;
print_tree(temp);
temp = temp-> left;
memmove(node,temp,sizeof node);

memmove(node, temp, sizeof *node);

}
return 0;
}

Your function is called "print_tree". I would have thought it
would print the tree (and not modify it). But what it actually
does is to print the top node, then print its right node (recursively),
then replace the top node with the left node.

This mangles the whole tree, and only prints part of it.

int main(void)
{
struct tree *node;
node = assign(1 , node);

You pass the uninitialized pointer to the function. The assign
function goes on to copy data out of this pointer.
I can't suggest a fix as I really have no idea what you are
trying to accomplish here.

node = assign(2 , node);
node = assign(8 , node);
print_tree(node);
return 0;
}

This little, ugly code does not work as expected.

It would help us to fix your code, if you wrote what you were
expecting to see.