Archived

This topic is now archived and is closed to further replies.

Dr Chi

How do I make a BST of records in C?

Recommended Posts

I know how to make a Binary Search Tree in C but how do I make a BST of records in C? I already have part of the answer already, it''s just the typedef and struct bits that I can''t work out. It is supposed to be a BST full of student records with some details like login name, mark, and student number. the records should be ordered based on student number This is what I have already:
  #include <stdio.h>
#include <stdlib.h>

#define TAB 5
#define LOGIN_ASIZE 7

typedef int Data;
typedef struct studrec Studrec;
typedef struct treenode Tnode;
typedef struct Data Studrec;


struct studrec {
	int  studnum;
    char login[LOGIN_ASIZE];
    int  mark;
} ;



struct treenode {
	Tnode *t1;
	Data data;
	Tnode *t2;
};

void free_treemem ( Tnode *tptr );
Tnode *build_bstrecs(void);
Tnode *make_tnode( Data val );
Tnode *bst_insert_rec_r ( Tnode *root, Tnode *newn );
int inorder( Tnode *node1, Tnode *node2 );
int get_data( Studrec *record );
void print_tree ( Tnode *tptr );
void pretty_print_tree( Tnode *tptr, int spaces );


int main(void)
{
	Tnode *root;

	root = build_bstree();
	print_tree( root );
	printf ("\n");
	pretty_print_tree( root, TAB );

	free_treemem( root );	
	
	return 0;
}

Tnode *build_bstrecs(void)
{
	Data record;
	Tnode *root = NULL, *newn;

	while ( get_data (&record) ) {
		newn = make_tnode( record );
		root = bst_insert_rec_r( root, record );
	}

	return root;
}

Tnode *make_tnode( Data val )
{
	Tnode *newn;

	newn = malloc( sizeof(Tnode) );
	if ( newn == NULL )	{
		fprintf( stderr, "Failure: Memory not allocated for data item: %d.\n", val);
		exit(EXIT_FAILURE);
	}

	newn->t1 = NULL;
	newn->data = val;
	newn->t2 = NULL;

	return newn;
}

Tnode *bst_insert_rec_r ( Tnode *root, Tnode *newn )
{
	if (root == NULL)
		root = newn;
	else if ( inorder( newn, root ) )
		root->t1 = bst_inesrt_rec_r( root->t1, newn );
	else
		root->t2 = bst_inesrt_rec_r( root->t2, newn );

	return root;

/*	Tnode *curr = root, *prev = NULL;

	while ( curr != NULL ) {
		prev = curr;
		if ( newn->data < curr->data )
			curr = curr->t1;
		else 
			curr = curr->t2;
	}

	if ( prev == NULL )
		root = newn;
	else if ( newn->data < prev->data )
		prev->t1 = newn;
	else
		prev->t2 = newn;

	return root; */
}

int inorder( Tnode *node1, Tnode *node2 )
{
	return ( node1->data->studnum < node2->data->studnum );
}


int get_data( Studrec *record )
{
    return  scanf( "%d %s %d %d",
                    &record->studnum,
                     record->login,
                    &record->marks[0],
                    &record->marks[1] )
            == 4 ;
}

void print_tree ( Tnode *tptr ) 
{
	if ( tptr != NULL )	{
		print_tree ( tptr->t1 );
		printf( "%5d", tptr->data );
		print_tree( tptr->t2 );
	}

	return;
}

void free_treemem ( Tnode *tptr )
{
	if (tptr != NULL) {
		free_treemem( tptr->t1 );
		free_treemem( tptr->t2 );
		free( tptr );
	}

	return;
}

void pretty_print_tree( Tnode *tptr, int spaces )
{
	if ( tptr != NULL )	{
		pretty_print_tree ( tptr->t2, spaces + TAB );
		printf( "%*d\n", spaces, tptr->data );
		pretty_print_tree( tptr->t1, spaces + TAB );
	}
	else
		printf( "%*c\n", spaces, ''*'' );

	return;
}  
any ideas?

Share this post


Link to post
Share on other sites
In brief: Use one of the members of the data structure as a key value. Provide a secondary function to do the comparison (ala qsort). Keep the data in place and move the pointers around instead to allow for building trees based on comparing different structure members.

Share this post


Link to post
Share on other sites
//I am still confused.... I will try to simplify my question
//a bit. thanks for helping anyway

typedef struct studrec Studrec;

struct studrec
{
char[size] login;
int studnum;
int mark;
}

//this is a record of a student. it contains login name,
//student number, and the student''s mark (grade).

typedef struct treenode Tnode;

struct treenode
{
Tnode t1;
?????;
Tnode t2;
}

/* This is a Binary Search Tree Structure. ????? represents my question. what do I put here if I want to make a Binary Search Tree of studrecs which are ordered by student number (studnum)? */

Share this post


Link to post
Share on other sites
quote:
Original post by Dr Chi
typedef struct studrec Studrec;
struct studrec
{
char[size] login;
int studnum;
int mark;
}

//this is a record of a student. it contains login name,
//student number, and the student''s mark (grade).

typedef struct treenode Tnode;

struct treenode
{
Tnode t1;
?????;
Tnode t2;
}
/* This is a Binary Search Tree Structure. ????? represents my question. what do I put here if I want to make a Binary Search Tree of studrecs which are ordered by student number (studnum)? */


How about a pointer to the data structure?

struct treenode
{
Tnode t1;
Studrec *pData;
Tnode t2;
}

and then use the studnum member as the value to sort on in the appropriate place.

Tnode *pA, Tnode *pB

pA->pData->studnum > pB->pData->studnum





Share this post


Link to post
Share on other sites