binary tree

[Micko]

I'm doing revision for the exam and need short revision of this:

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	int data;
	struct node* left;
	struct node* right;
}Node;


void Insert(Node**, int);
void PreOrder(Node*);
void InOrder(Node*);
void PostOrder(Node*);
void RemoveTree(Node**);

int main()
{
	Node*head=NULL;

	Insert(&head,5);
	Insert(&head,2);
	Insert(&head,7);

	

	RemoveTree(&head);
	PostOrder(head);
}

void Insert(Node** head,int data)
{
	if(!*head)
	{
		*head=malloc(sizeof(Node));
		(*head)->data=data;
		(*head)->left=NULL;
		(*head)->right=NULL;
		return;
	}
	if(data<=(*head)->data)
		Insert(&(*head)->left,data);
	else
		Insert(&(*head)->right,data);

}

void PreOrder(Node* head)
{
	if(!head)
		return;
	printf("%d ",head->data);
	PreOrder(head->left);
	PreOrder(head->right);
}

void InOrder(Node* head)
{
	if(!head)
		return;
	
	InOrder(head->left);
	printf("%d ",head->data);
	InOrder(head->right);
}

void PostOrder(Node* head)
{
	if(!head)
	{
		return;
	}
	
	PostOrder(head->left);
	PostOrder(head->right);
	printf("%d ",head->data);
}

void RemoveTree(Node** head)
{
	Node* current=*head;
	if(current)
	{
		RemoveTree(&current->left);
		RemoveTree(&current->right);
		free(current);
		/*current=NULL;*/
	}
	*head=NULL;
}

I think this is OK!
I only have doubts about Remove tree. If you can examine is there a memory leak?
And should I put that line under comment or not?

[Prelude]

>If you can examine is there a memory leak?
Write a simple pair of macros to see if you're calling a balanced number of allocations and releases. All they need to do is increment a counter and then call malloc or free. If you end up with 0 at the end then you can be reasonably sure that there aren't any pointers that weren't freed.

[okinrus]

Remove looks ok. The depth first search will go through all of the nodes of the tree and will make sure you delete the children before deleting the parent.

[Emmanuel Delaha]

I'm doing revision for the exam and need short revision of this:
<...>
I think this is OK!
I only have doubts about Remove tree. If you can examine is there a memory leak?
And should I put that line under comment or not?

All I can say, is that the code and its example have no memory leak.

[Micko]

Well it was a revision for the exam. I learn that couple months ago. I remeber when Prelude suggest me how to trace this in one of my old posts.
http://cboard.cprogramming.com/showt...ghlight=malloc
It is solution using global variables. I really would like to see solution with macros. Anyway pretprocessor is one of my
weakness

[Prelude]

>I really would like to see solution with macros.
Quick and dirty:

static unsigned long alloc_count = 0;
#define xmalloc(x) (++alloc_count, \
  printf("alloc line %d: balance -- %ld\n", __LINE__, alloc_count), \
  malloc(sizeof *(x)))
#define xnmalloc(x, n) (++alloc_count, \
  printf("alloc line %d: balance -- %ld\n", __LINE__, alloc_count), \
  malloc((n) * sizeof *(x)))
#define xfree(x) (alloc_count = x ? alloc_count - 1 : alloc_count, \
  printf("free line %d: balance -- %ld\n", __LINE__, alloc_count), \
  free(x))

xmalloc takes the pointer to be allocated memory to and allocates enough memory for an object of the type the pointer points to. xnmalloc takes does the same thing as xmalloc except it takes an extra argument to determine how much memory for N objects is allocated. xfree releases the memory. Note that all of the update the counter and report the status. xfree doesn't decrement the counter if passed a null pointer.

You can take this as far as you want. My data structures usually go through the first few revisions with something similar using a VERBOSE switch that I can turn off if the output gets to be too cluttered with status messages. I also use call tracing, something very rudimentary like this:

#if defined(VERBOSE)
#  define call_trace(msg) printf(msg)
#else
#  define call_trace(msg)
#endif

Then after every call to xmalloc, xnmalloc or xfree, I use call_trace to report where the call is made by passing a suitable message:

struct tree *
insert(
  struct tree *root,
  void        *obj
  )
{
  struct tree *p;
  ...
  p = xmalloc(p);
  call_trace("xmalloc in insert: p = xmalloc(p)");
  if (!p) {
    ...
  }
}

It's very simple, and surprisingly effective in the early stages of data structure verification.