Thread: Binary Tree

I coded a binary tree with basic functions: insert, display, search and clear. The clear() function isn't working properly. I want to delete all the nodes. So I modified the display function:

Code:

// header files

struct tree
{
	int dat;
	struct tree *left, *right;
} *root, *temp;

void display(struct tree *n)
{
	if(n->left) display(n->left);
	printf("%d\n", n->dat);
	if(n->right) display(n->right);
}

// Other functions

void clear(struct tree *n)
{
	if(n->left) clear(n->left);
	free(n);
	if(n->right) clear(n->right);
	n->left = NULL;
	n->right = NULL;
}

I remove the nodes in sort order (small -> big numbers). After I cleared the tree, I display() the tree again. It prints 1 rubbish number. Though the n->right and n->left should be NULL. I know the clear() function is wrong, but I don't know how to clear the tree properly.

That's because your "top" (root) node is not set to NULL - so when you traverse the tree, it finds one node.

Code:

void clear(struct tree *n)
{
	if(n->left) clear(n->left);
	free(n);
	if(n->right) clear(n->right);
	n->left = NULL;
	n->right = NULL;
}

Also, the code is "broken" in the fact that you use the data pointed to by n after it's been freed - which is bad, since there is absolutely no guarantee that it's going to contain valid data. Try using a macro like this:

Code:

#define free(x) do { memset(x, 0xD4, sizeof(*x)); free(x); } while(0)

EDIT: Corrected te order of memset arguments.

and it will crash when you do the above. If your code was multithreaded, there's no guarantee that another thread will not "grab" the memory you just freed and use it for other purposes, before you have deleted the rest of the tree - particularly if the tree as thousands of entries.

You need to free it LAST, after you have traversed the nodes below this point.

You probably want to pass in a pointer to pointer to tree, so that you can update the actual pointer to NULL - and then you don't have to set the left/right pointers to NULL separately, which makes the code a bit simpler.

--
Mats

Is this solution good too?

Code:

void delNodes(struct tree *n)
{
	if(n->left) delNodes(n->left);
	n->left = NULL;
	n->right = NULL;
	free(n);
	if(n->right) delNodes(n->right);
	
}

void clear(struct tree *n)
{
	delNodes(n);
	temp->left = temp->right = NULL;
	free(temp);
	root->left = root->right = NULL;
	free(root);
	root = temp = NULL;
}

You probably want to pass in a pointer to pointer to tree, so that you can update the actual pointer to NULL - and then you don't have to set the left/right pointers to NULL separately, which makes the code a bit simpler.

I don't know what you mean with this? Pointer to a pointer, so

Code:

struct tree **tempPtr = &n;

But how do I set the right and left pointers to NULL with **tempPtr?

Code:

void delNodes(struct tree *n)
{
	if(n->left) delNodes(n->left);
	n->left = NULL;
	n->right = NULL;
	free(n);
	if(n->right) delNodes(n->right);
	
}

Still uses n->something after free and n->right is now NULL when you go to delete it - so it will not delete it.

I don't think you need to split the function [although it's a viable solution], but rather just pass in struct tree **n and do "*n = NULL" just after free(*n); Before you do any of that, of course, delete (recursively) your left and right tree nodes.

Add the macro I posted in the previous post, and you will definitely see if you use after free.

--
Mats

Using the macro I see the error now, but when I use your solution (instead of splitting the task into two functions) I get a segfault. I don't get this segfault when I split the task into two functions.

Code:

void delNodes(struct tree **n)
{
	if((*n)->left) delNodes((*n)->left);
	
	if((*n)->right) delNodes((*n)->right);
	
	(*n)->left = NULL;
	(*n)->right = NULL;
	free(*n);
	*n = NULL;
	printf("free\n");
}

And I don't understand why I can't just use struct tree *n instead of struct tree **n in this function?

> delNodes((*n)->left);
Do you get any warnings?

It would seem to me to be
delNodes( &((*n)->left) );
given the new prototype of the function.

Code:

	if((*n)->left) delNodes(&(*n)->left);
	
	if((*n)->right) delNodes(&(*n)->right);

I don't think you are compiling your code with Warnings enabled in the compiler. That would spot the above problem.

If you want to simplify your code, you couold use something like this:

Code:

void delNodes(struct tree **pn)
{
   struct tree *n = *pn;

   if (n->right) delNodes(&n->right);
   ...  // More code goes here. 
   free(n);
   *pn = NULL;
}

You only need the double pointer to be able to set the "incoming" pointer to NULL.

--
Mats

Oh I see now . One last question about this: Why does the following 'delNodes' function segfault? Is it because you make *n NULL and use it afterwards (instead of making *n NULL and using **n)?

Code:

void delNodes(struct tree *n)
{
	if(n->left) delNodes(n->left);
	
	if(n->right) delNodes(n->right);
	
	n->left = NULL;
	n->right = NULL;
	free(n);
	n = NULL;
	printf("free\n");
}

EDIT: oh, you were faster, (I was thinking and trying very long). Thanks for the help!

No, it is because you are passing in the wrong address &(*n)->right is not the same value as (*n)->right, so you are trying to look at "->right" on something that isn't a pointer to pointer to a tree - which will be the wrong memory location and thus seg-fault.

Use -Wall on the compiler, and it will tell you when you pass the wrong type of pointer - C as a language is quite flexible with what pointers mean and point to, but enabling warnings will give you a warning when the compiler thinks "this doesn't look quite like I expected". [99% of the time, the compiler is right, and in the case where it isn't, you probably should use a cast - but it's more likely that you made a mistake].

--
Mats

I already use -Wall. When I use

Code:

void delNodes(struct tree *n)
{
	if(n->left) delNodes(n->left);
	
	if(n->right) delNodes(n->right);
	
	n->left = NULL;
	n->right = NULL;
	free(n);
	n = NULL;
	printf("free\n");
}

it doesn't give any warnings... though it segfaults...

delNodes segfaults, or the display code segfaults?

I don't see anything that would make it segfault, but root will still point to something bad when delNodes is finished - whcih is why you need to pass a pointer to pointer.

--
Mats

display() segfaults. When I set root = NULL after delNodes() it doesn't segfault anymore. So the pointer to pointer solution is more efficient. Thanks again .

But when delNodes() returns a struct tree * and it always returns NULL, and when I return NULL to the root pointer in the main function, the problem is solved.

Here's what's wrong with it:
There should only be one if-statement, and it should only be checking n.
setting n->left or n->right to NULL is a waste of time.
It should be taking a pointer-pointer, or returning a pointer.