hi,
I have been asked to implement a binary tree structure with the foll requirements
1) Generate 1000 integers from 100,000,001 to 100,001,000
2) Create a collection and add first 500 integers
3) Delete 400 integers from 101st to 500th.
4) Add the rest of 500 integers
5) Find all the odd numbers in the collection and delete all of them.
6) Your inordertraversal function writes all the items in the collection into a file named output3.txt as below.
100000002
100000004
100000006
....
i have written the code with 3 files which are as follows:

Code:
////////////////////////////////////////
main.c
/////////////////////////////////
#include <assert.h>
#include <string.h>
#include <math.h>
#include "coll_a.h" /* import the specification */ 

collection myCollection;
int max_items;

int private_print(void *item);
int ItemCmp(void *a, void *b);

int main()
{ 
FILE *f1;
int i,j=100000000;
int intData[1000];
f1=fopen("out3.txt","wt"); 

/* Generating 1000 integers from 100,000,001 to 100,001,000 */
for (i =0; i <1000; i++)
{
intData[i] = ++j;
} 
max_items = 1000;
j = 0;
myCollection = ConsCollection(max_items,ItemCmp);
printf("adding 500 items\n");
for (i = 0; i <500; i++) 
{
AddToCollection(myCollection, (void *)&intData[j ++]);
}
printf("deleting 400 items\n");
for (i = 0; i <400; i++)
{
DeleteFromCollection(myCollection, (void *)&intData[--j]);
}
printf("adding the rest of 500 items\n");
j+=400;
for (i = 0; i <500; i++) 
{
AddToCollection(myCollection, (void *)&intData[++j]);
}
for (i=0;i <100;i++)
{
if((intData[i]%2)!=0)
{DeleteFromCollection(myCollection, (void *)&intData[i]);
}
for (i=500;i<1000;i++)
{
if((intData[i]%2)!=0)
{DeleteFromCollection(myCollection, (void *)&intData[i]);
}
} 
InOrderTraversal(c,private_print);
}

int ItemCmp(void *a, void *b)
{long *d1,*d2;
*d1=(long *)a;
*d2=(long *)b;
if(*d1>*d2)
return -1; 
else if(*d1<*d2)
return 1;
else
return 0; 
}
int private_print(void *item)
{long *t;
*t=(long *)item;
if(t!=NULL)
{printf("%d",*t ); 
fprintf (f1, "\n%d",*t);
}
else
{
return 0;
}
}
Code:
///////////////////////////////////////////
/////////////////////////////////////////////////////////
coll_a.h
///////////////////////////////////////
/* Specification for collection */

typedef struct t_collection *collection;

collection ConsCollection( int max_items, 
int (*ItemCmp)(void *, void *) );
/* Construct a new collection
Pre-condition: max_items > 0
Post-condition: returns a pointer to an empty collection
*/

void AddToCollection( collection c, void *item );
/* Add an item to a collection
Pre-condition: (c is a collection created by a call to
ConsCollection) &&
(existing item count < max_items) &&
(item != NULL)
Post-condition: item has been added to c
*/

void DeleteFromCollection( collection c, void *item );
/* Delete an item from a collection
Pre-condition: (c is a collection created by a call to
ConsCollection) &&
(existing item count >= 1) &&
(item != NULL)
Post-condition: item has been deleted from c
*/

void *FindInCollection( collection c, void *key );
/* Find an item in a collection
Pre-condition: c is a collection created by a call to
ConsCollection
key != NULL
Post-condition: returns an item identified by key if one
exists, otherwise returns NULL
*/

void InOrderTraversal(collection c, int(*private_print)(void *item))
Code:
//////////////////////////////////////////////////////////////
coll_at.c
///////////////////////////////////////
#include <stdlib.h> /* calloc */
#include <stdio.h> /* NULL */
#include <assert.h> /* Needed for assertions */
#include "coll_a.h" /* import the specification */ 

struct t_node
{
void *item;
struct t_node *left;
struct t_node *right;
} node;

struct t_collection
{
/* Note that size is not needed any longer! */
int (*ItemCmp)( void *, void * ); 
struct t_node *node;
};

collection ConsCollection(int max_items,
int (*ItemCmp)(void *,void *))
/* Construct a data collection
Pre-condition: (max_items > 0) && (item_size > 0) 
Post-condition: returns a pointer to an empty
collection
*/
{
collection c;
/* Although redundant, this assertion should be
retained as it tests compliance with the formal 
specification */
assert( max_items > 0 );
c = (collection)calloc( 1, sizeof(struct t_collection) );
c->node = (struct t_node *)0; 
c->ItemCmp = ItemCmp;
return c;
}

static void AddToTree( struct t_node **t, struct t_node *data,
int (*ItemCmp)(void *, void *) )
{
struct t_node *base; 
base = *t;
/* If it's a null tree, just add it here */
if ( base == NULL )
{
*t = data;
return;
}
else
{
if ( ItemCmp( base->item, data ) < 0 )
{
AddToTree( &(base->left), data, ItemCmp );
}
else 
AddToTree( &(base->right), data, ItemCmp );
}
}

void AddToCollection( collection c, void *item )
/* Add an item to a collection
Pre-condition: (c is a collection created by a call to 
ConsCollection) &&
(existing item count < max_items) &&
(item != NULL) 
Post-condition: item has been added to c
*/
{
struct t_node *data, *node_p;
assert( c != NULL );
assert( item != NULL );
/* Allocate space for a node for the data item */ 
data = (struct t_node *)malloc(sizeof(struct t_node));
/* Attach the item to the node */
data->item = item;
data->left = data->right = (struct t_node *)0;
node_p = c->node; 
AddToTree( &node_p, data, c->ItemCmp );
c->node=node_p;
}



void DeleteFromTree( struct t_node **t, void *item )
{
struct t_node *temp, *prev, *succ;
prev=temp=*t; 
void *val;
*val=(void*)item;
//val=item;
if(*t==NULL)
printf("NO NODES TO BE DELETED");
else
{ 
while(temp->item!=val && temp!=NULL) //define val
{
prev=temp; 
if(temp->item >val)
temp=temp->left;
else 
temp=temp->right;
} 
if(temp==NULL)
{
printf("the value could not be found\n");
return; 
} 
if(temp->left!=NULL && temp->right!=NULL)
{ 
prev=temp;
succ=temp->right;
while(succ->left!=NULL) 
{
prev=succ;
succ=succ->left; 
}
temp->item=succ->item;
temp=succ; 
}
if(temp->left!=NULL && temp->right==NULL)
{ 
if(prev->left==temp)
prev->left=temp->left;
else
prev->right=temp->left;
} 
if(temp->left==NULL && temp->right!=NULL)
{
if(prev->left==temp) 
prev->left=temp->right;
else
prev->right=temp->right; 
}
if(temp->left==NULL && temp->right==NULL)
{ 
if(prev->left==temp)
prev->left=NULL;
else 
prev->right=NULL;
}
/* if(temp==*root) // define root
{
if(temp->left!=NULL)
*root=temp->left; 
else
*root=temp->right;
}*/
free(temp);
}


void DeleteFromCollection( collection c, void *item )
/* Delete an item from a collection
Pre-condition: (c is a collection created by a call to
ConsCollection) && 
(existing item count >= 1) &&
(item != NULL)
Post-condition: item has been deleted from c
*/
{
struct t_node *node;
assert( c != NULL );
/* The requirement that the collection has at least
one item is expressed a little differently */
assert( c->node != NULL ); 
assert( item != NULL);
/* Select node at head of list */
node = c->node;
DeleteFromTree( &node, item );
c->node=node;
}

void *FindInTree( struct t_node *t, void *key )
{
if(t==NULL)
return;
else if(t->item==key)
return t;
else if ( ItemCmp( t->item, key ) < 0 ) 
return FindInTree( (t->left), key );
else
return FindInTree( (t->right), key );
}





void *FindInCollection( collection c, void *key )
/* Find an item in a collection
Pre-condition: (c is a collection created by a call to
ConsCollection) &&
(key != NULL) 
Post-condition: returns an item identified by key if
one exists, otherwise returns NULL
*/
{
struct t_node *node;
assert( c != NULL ); 
assert( key != NULL );
/* Select node at head of list */
node = c->node;
return FindInTree( node, key );
}
}



void InOrderTreeTraversal(struct t_node *t, int(*private_print)(void *item))
{
if(t != NULL)
{
InOrderTreeTraversal(t->left,private_print);
private_print(t->item);
InOrderTreeTraversal(t->right, private_print);
}
}

void InOrderTraversal(collection c, int(*private_print)(void *item))
{
assert(c != NULL);
InOrderTreeTraversal(c->node,private_print);
}
////////////////////////////////
Here are the errors which I get on compiling.

ont> gcc -c main.c coll_at.c
main.c: In function `InOrderTraversal':
main.c:17: error: syntax error before '{' token
main.c:20: error: parameter `j' is initialized
main.c:22: error: syntax error before "f1"
coll_at.c: In function `InOrderTraversal':
coll_at.c:13: warning: structure defined inside parms
coll_at.c:20: warning: structure defined inside parms
coll_at.c:20: warning: empty declaration
coll_at.c:23: error: syntax error before ')' token
coll_at.c:92: error: syntax error before '*' token

Last edited by shabbir; 22Mar2007 at 21:47.. Reason: Code formating.